Matemàtica discreta (MATD)

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.

Coneixements

1. Conèixer els principis bàsics d'enumeració: principi d'identitat, d'addició del producte, del colomar i d'inclusió-exclusió. Conèixer els principals nombres combinatoris: binomials, multinomials, de Catalan, de desarranjaments, etc.
2. Conèixer les funcions generadores ordinàries i exponencials associades a una successió. Conèixer les recurrències lineals.
3. Conèixer l'estructura de graf com a model matemàtic i les diferents formes de donar un graf. Conèixer els diferents recorreguts que es poden definir en un graf, i els conceptes de connexió i connectivitat associats. Conèixer les caracteritzacions del grafs eulerians. Conèixer la definició de graf hamiltonià, i la dificultat associada per reconèixer un graf hamiltonià.
4. Conèixer els grafs que són arbres. Conèixer algorismes per trobar arbres generadors d'un graf connex amb pesos i sense pesos. Conèixer el nombre d'arbres generadors d'un graf.
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 la unicitat.

Habilitats

1. Saber aplicar els principis bàsics d'enumeració. Saber reconèixer quin tipus d'estructures compten cada tipus de nombre combinatori.
2. Saber descomposar un funció racional en fraccions simples. Saber operar amb funcions generadores. Saber plantejar problemes d'enumeració en termes de recurrències. Saber traduir recurrències a funcions generadores.
   Saber resoldre recurrències.
   
3. Saber modelar problemes en termes de grafs. Saber aplicar els algorismes per obtenir un circuit eulerià i un recorregut eulerià. Saber aplicar a exemples senzills algunes condcions suficients de hamiltoneitat. Saber formar la matriu d'adjacència d'un graf i traduir propietats elementals d'un graf a propietats de la seva matriu d'adjacència.
4. Saber aplicar els algorismes d'obtenció d'arbres generadors d'un graf. Saber aplicar els algorismes d'obtenció d'arbres generadors de cost mínim. Saber calcular el nombre d'arbres generadors d'un graf.
5. Saber operar a Z_p amb p primer, en particular saber calcular inversos.
   Saber operar amb polinomis amb coeficients a Z_p. Saber les propietats de les arrels. Saber construir cossos finits. Saber operar en un cos finit.
   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. Capacitat per aplicar les tècniques per construir demostracions lògico-matemàtiques.
3. 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. Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.

Les classes de teoria responen a l'esquema clàssic de classe magistral, avantualment ajudada per l'ús de retroprojector o demostració computacional.

Les classes de problemes són participatives, amb explicació per part dels estudiants de problemes encarregats prèviament i de discussió col.lectiva de problemes prèviament marcats.

L'avaluació és contínua preferentment i es basa en les proves següents:

P1: examen de la part inicial del temari,
P2: examen de la part intermitja del temari,
P3: examen de la part final del temari.

La nota final es calcula com segueix:
Nota = 0.2*P1+0.4*P2+0.4*P3, (P1,P2,P3 són notes sobre 10).

Qui no segueixi l'avaluació contínua o vulgui renunciar-hi haurà de realitzar un examen del temari complet, i la nota corresponent serà la que li quedarà com a nota final. En aquest cas, l'estudiant haurà de comunicar al coordinador que renúncia a l'avaluació contínua, com a molt tard, l'últim dia de classes del quadrimestre i pels canals que es publicaran al Racó.

• 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.

• 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 Matemática discreta y sus aplicaciones, McGraw Hill, 2004.

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 saber calcular determinants.

Saber els continguts de l'assignatura AL.