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.

Obligatoris: cap

Recomanats: Iniciació a la programació.

Part I: INTRODUCCIÓ A L'ANÀLISI COMBINATÒRIA (total: 6h.)

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 (total: 34 h.)

1.- Introducció als grafs (10 hores)

• Definicions bàsiques. 
• Com es guarda un graf en memòria.
• Recorregut d'un graf.
• Connexió i componenets.
• Planaritat.

2.- Camins mínims (5 hores)

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

3.- Arbres (5 hores)

• Conceptes generals.
• Arbre generat. Generació de tots els arbres d'un graf.
• Arbres generats de cost mínim d'un graf.

4.- Xarxes de transport (8 hores)

• Definicions bàsiques.
• Flux màxim en una xarxa.
• Variacions del problema del flux màxim.
• Construcció d'un graf amb els graus fixats.
• Minimització del cost per a un flux fixat.

5.- Camins i Circuits eulerians. Circuits hamiltonians (6 hores)

• Caracterització dels camins i dels circuits eulerians.
• Obtenció d'un circuit eulerià.
• El problema del carter xinès.
• Caracterització dels camins i dels circuits hamiltonians.
• Obtenció de camins hamiltonians.

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.

Classes de teoria i problemes: 3 hores setmanals

Pràctiques: 1 hora setmanal

Examen de teoria i problemes: 80%

Examen de pràctiques: 20%

L'examen de pràctiques és únic i serveix tant per a la convocatòria ordinària com per l'extraordinària.