|
Objectius
|
Programa provisional
|
|
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.
Aquests són sens dubte els temes de més importància en anàlisis d'algorismes, complexitat, i, en
general, a la informàtica teòrica. |
|
|
|
|
Prerrequisits
|
|
|
Obligatoris: cap
Recomanats: Àlgebra. Inicicació a la programació. |
|
|
|
|
Contingut (Programa)
|
|
|
Part I: INTRODUCCIÓ A L'ANÀLISI COMBINATÒRIA (total: 6 h.)
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. Temporalització: 10 h.)
1.1 Definicions bàsiques.
1.2 Com es guarda un graf en memòria.
1.3 Recorregut d'un graf.
1.4 Connexió i componenets.
1.5 Planaritat.
2.- Camins mínims.(Temporalització: 5 h.)
2.1 Algorisme de Dijkstra.
2.2 Algorisme de Ford.
2.3 Algorisme de Floyd.
3.- Arbres. (Temporalització: 5 h.)
3.1 Conceptes generals.
3.2 Arbre generat. Generació de tots els arbres d'un graf.
3.3 Arbres generats de cost mínim d'un graf.
4.- Xarxes de transport (Temporalització: 8 h.)
4.1 Definicions bàsiques.
4.2 Flux màxim en una xarxa.
4.3 Variacions del problema del flux màxim.
4.4 Construcció d'un graf amb els graus fixats.
4.5 Minimització del cost per a un flux fixat.
5.- Camins i Circuits eulerians. Circuits hamiltonians. (Temporalització: 6 h.)
5.1 Caracterització dels camins i dels circuits eulerians.
5.2 Obtenció d'un circuit eulerià.
5.3 El problema del carter xinès.
5.4 Caracterització dels camins i dels circuits hamiltonians.
5.5 Obtenció de camins hamiltonians.
5.6 El problema del viatjant (TSP). |
|
|
|
|
Bibliografia
|
|
|
Bibliografia bàsica a utilitzar durant el curs.
- BASART, J.M.: "Grafs. Fonaments i algorismes" Manuals UAB, núm. 13
- ANDERSON, I.: "Introducción a la combinatoria" Ed. Vicens Vives.
- GRIMALDI, R.P.: "Matemáticas discreta y combinatoria" Ed. Addison-Wesley Iberoamericana.
- STEBEN SKIENA: "Implementing Discrete Mathematics" Addison-Wesley.
Altra bibliografia:
- 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.
- NEMHAUSER, G.L.; WOLSEY, L.A.: "Integer and Combinatorial Optimization" Ed. John Wiley & Sons,1988.
- BAZARAA, M.S.; JARUIS, J.J.: "Programación lineal y Flujo en redes" Ed. Limusa
|
|
|
|
|
Mètodes docents
|
|
|
Classes de teoria i problemes: 3 hores setmanals
Pràctiques: 1 hora setmanal |
|
|
|
|
|
|
Informació addicional
|
|
|
|
12 sessions de pràctiques amb el paquet MAPLE per solucionar problemes amb la teoria de grafs, de les quals les 3 primeres són sobre combinatòria, les 2 següents sobre introducció al MAPLE, les 6 següents sobre grafs i finalment la pràctica 12 correspondrà a l'examen. |
|
|
|
|
|
La bibliografia a la biblioteca