Matemàtiques III ( M3 )

Professors

Responsable:	Josep Maria Brunat Blay (josep.m.brunatupc.edu).
Altres:	(Informació no introduïda)

Objectius Generals

L'objectiu general de l'assignatura és posar a l'abast de l'estudiant un conjunt
de conceptes i tècniques propis de la matemàtica discreta i de l'àlgebra que, per la seva ubiquïtat en el món de les tecnologies noves, són part de la formació bàsica de tot enginyer en informàtica.

Objectius Específics

Coneixements

1. Conéixer els principis bàsics d'enumeració: pricipi d'identitat, del producte, del colomar i d'inclusió-exclusió. Conéixer l'àlgebra de les funcions generadores.
   Cóneixer expressar recurrències en termes de funcions generadores.
2. Conéixer l'estructura de graf i digraf com a model matemàtic i les diferents formes de donar un graf. Conéixer la caracterització dels grafs representables planarment.
   Conéixer les caracteritzacions dels arbres i l'obtenció d'arbres generadors de cost mínim.
   
3. Conéixer les caracteritzacions del graf eulerians i saber obtenir un circuit eulerià quan n'hi ha. Conéixer el problema dels cicles hamiltonians i les dificultats associades. Conéixer l'estructura algebraica dels cicles d'un graf.
4. Conéixer els conceptes de flux, connectivitat i aparellament i els teoremes essencials: teorema del flux màxim-tall mínim, teoremes de Menger i teorema de Hall.
5. Conéixer l'estructura de cos de Z_p (els enters mòdul un primer p) i la d'anell de polinomis amb coeficients a Z_p. Saber què és un polinomi irreductible i conéixer el teorema de factorització única. Saber construir cossos finits i conéixer l'existència i unicitat.

Habilitats

1. Saber aplicar els principis bàsics d'enumeració.Saber operar amb funcions generadores. Saber plantejar problemes d'enumeració en termes de recurrències. Saber resoldre recurrències emprant funcions generadores.
2. Saber modelar problemes en termes de grafs i digrafs. Saber emprar les relacions que lliguen els paràmetres d'un graf planari per deduir valors d'uns paràmetres en funció dels valors dels altres.
   Saber calcular el nombre d'arbres generadors d'un graf connex. Saber aplicar els algorismes de recerca en profunditat i en amplada per obtenir arbres generadors. Saber aplicar els algorismes de Prim i de Kruskal per obtenir arbres generadors de cost mínim.
3. Saber aplicar els algorismes per obtenir un circuit eulerià i un recorregut eulerià. Saber aplicar a exemples senzills algunes condcions suficients de hamiltoneitat. Saber operar amb cicles.
4. Saber aplicar l'algorisme de Ford i Fulkerson per obtenir un flux màxim.
   Saber aplicar els teoremes de Menger i de Hall en situacions simples.
5. Saber operar a Z_p amb p primer, en particular saber calcular inversos.
   Saber operar amb polinomis amb coeficients a Z_p. Saber construir cossos finits.
   Saber operar en cossos finits emprant la forma polinòmica dels seus elements i emprant logaritmes discrets. Saber operar amb polinomis amb coeficients en un cos finit.

Competències

1. Capacitat per al raonament crític i lògico-matemàtic
2. (1) Capacitat per aplicar les tècniques per construir demostracions lògico-matemàtiques.
3. (1) Capacitat per transformar enunciats informals a enunciats formals, i a l'inrevés.
4. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
5. (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.

Continguts

Hores estimades de:

Metodologia docent

Les classes de teoria responen a l'esquema clàssic de classe magistral, avantualment ajudada per l'ús de retroprojector.
Les classes de problemes seran participatives, amb explicació per part dels estudiants de problemes encarregats prèviament
i de discussió col.lectiva d'altres problemes.
Les (poques) classes de laboratori tindran un format estàndard i estaran acumulades en una setmana cap al final del quadrimestre.

Mètode d'avaluació

1) Un examen parcial que inclou els quatre primers objectius especifics (coneixements i habiltats).
Pes: 20%

2) Un examen de problemes que inclou els objectius del 3 al 6 ambdós inclosos (habilitats).
Pes: 20%

3) Un examen final que inclou tots els objectius (coneixements i habilitats).
Pes: 60% o 100%

4) La qualificació de l'assignatura serà la major entre (a) la ponderada entre els tres exàmens comptant el final el 60% i (b) la del final comptat al 100%.

Bibliografía bàsica

• Francesc Comelles, Josep Fàbrega, Anna Sànchez, Oriol Serra. Matemàtica Discreta, Edicions UPC, 1994.
• Norman L. Biggs Matemàtica Discreta, Vicens-Vives, 1994.
• Ralph P. Grimaldi Matemáticas Discreta y Combinatoria, Addison Wesley Iberoamericana, 1997.

Bibliografía complementària

• Josep M. Brunat Combinatòria i teoria de grafs, Edicions UPC, 1997.
• Joan Trias Matemàtica Discreta. Problemes resolts., Edicions UPC, 2001.
• Jiri Matousek, Jaroslav Nesetril Invitation to Discrete Mathematics, Clarendon Press, Oxford., 1998.
• Kenneth H. Rosen Discrete Mathematics and its Applications, McGraw Hill, 2003.

Enllaços web

Capacitats prèvies

Conéixer les operacions i relacions amb conjunts: reunió, intersecció, diferència, producte cartesià, inclusió.
Conéixer els diferents tipus d'aplicacions.
Saber comptar combinacions i permutacions amb i sense repetició.
Conéixer les propietats elementals dels nombres binomials, i saber calcular-los.

Saber calcular el mcd de nombres enters i els coeficients de la identitat de Bezout mitjançant l'algorisme d'Euclides.

Saber calcular productes de matrius i determinants. Conéixer l'estructura d'espai vectorial.

L'assignatura Matemàtiques I hauria de ser prerequisit.