La matemàtica discreta integra un conjunt de branques diverses de la matemàtica que tenen totes elles relació amb la modelització de fenòmens discrets i l'estudi de les estructures finites i discretes, i que estan jugant un paper d'importància creixent a la informàtica i a ciències de la computació en general. Aquest curs vol ésser una introducció a una part dels coneixements matemàtics bàsics i importants per a l'estudi de la informàtica. Essencialment la Matemàtica Discreta s'estructura a l'entorn de dos grans temes, que entenem que han de constituir el nucli de l'assignatura.
I - Introducció a la combinatòria enumerativa.
II - Teoria de Grafs.

És necessari tenir els coneixements mínims de Matemàtiques a nivell de batxillerat, a destacar l’àlgebra de matrius i càlcul de determinants. També és recomenable tenir uns coneixements mínims sobre programació.

Part I: INTRODUCCIÓ A L'ANÀLISI COMBINATÒRIA

1. Problemes de l'anàlisi combinatòria.
2. Permutacions amb i sense repetició.
3. Combinatòries amb i sense repetició.
4. Els coeficients binomials: significat i algunes propietats.
5. Principi d'inclusió-exclusió.

Part II: TEORIA DE GRAFS

1.- Introducció als grafs

• Definicions bàsiques. 
• Estructura de dades d'un graf.
• Recorregut d'un graf.
• Connexió i components.
• Planaritat i coloració.

2.- Camins mínims

• Algorisme de Dijkstra.
• Algorisme de Ford.
• Algorisme de Floyd.

3.- Arbres

• Conceptes generals.  
• Arbres generats de cost mínim d'un graf.
• Algorisme de Kruskal i algorisme de Prim.

4.- Grafs eulerians i hamiltonians

• Caracterització dels camins i dels circuits eulerians.
• Obtenció d'un circuit eulerià. Algorisme de Hierholzer.
• Problema del carter xinès. Algorisme d'Edmonds.
• Caracterització dels camins i dels circuits hamiltonians.
• Obtenció de camins hamiltonians. Mètode de les multiplicacions llatines i algorisme de Roberts i Flores.
• Problema del viatjant de comerç.

La bibliografia a la biblioteca

Bibliografia bàsica a utilitzar durant el curs.

- BASART, J.M.: "Grafs. Fonaments i algorismes" Manuals UAB, nº 13.

 - ANDERSON, I.: "Introducción a la combinatoria" Ed. Vicens Vives.

- GRIMALDI, R.P.: "Matemáticas discreta y combinatoria" Ed. Addison-Wesley Iberoamericana.

- GARCÍA MERAYO, F.: "Matemática discreta" Ed. Thomson

Altra bibliografia:

- GARCÍA MERAYO, F. i altres: "Problemas resueltos de Matemática discreta" Ed. Thomson

- MARARAY, F.: "Graph Theory" Ed. Addison-Wesley.

- WILSON, J.R.: "Introducción a la teoría de grafos" Ed. Alianza.

- WAYNE, L. WINSTON: "Mathematical Programming. Applications and Algorithms" Ed. Duxbury Press.

L’assignatura consta de classes teòriques, classes de problemes i classes pràctiques a l’aula informàtica.

La durada de les classes de teoria i problemes és de 3 hores setmanals. A les classes teòriques el professor dóna els coneixements necessaris perquè l’alumne pugui fer un seguiment de l’assignatura i resoldre els problemes que se li proposen. A les classes de problemes es posen en comú els problemes que els alumnes s’han trobat al intentar resoldre els problemes proposats

Les pràctiques es realitzen en sessions de dues hores cada 15 dies i en l'última sessió es realitza l'examen. Les classes pràctiques tenen lloc a l’aula informàtica i s'utilitza el programa MAPLE.

L'avaluació de l'assignatura consta de tres parts:

1.- Un examen tipus test que es realitzarà a mig quadrimestre i que té una puntuació d'un 20% de la nota.

2.- Un examen de pràctiques que es realitzarà al final del quadrimestre abans de l'acabament de les classes i que tindrà una puntuació d'un 20% de la nota.

3.- Un examen final (primera i segona convocatòria) que tindrà una puntuació d'un 60% de la nota.

L'examen test i el de pràctiques són únics i la puntuació obtinguda serveix tant per a la convocatòria ordinària com per l'extraordinària. La nota de l'examen final haurà de ser superior o igual a 3 sobre 10 per poder fer mitjana amb les altres dues notes.