Assignatura/matèria en el conjunt del pla d'estudis (màx. 4000 caràcters)
La Matemàtica Discreta estudia els anomenats objectes discrets, els quals estan
formats per un nombre finit o numerable d'elements. En matemàtiques, el terme
discret, en contraposició a continu, significa que està constituït per elements “ben separats entre si”. Entre els objectes discrets hi trobem els nombres enters i les
estructures algebraiques discretes, tractades en l'assignatura d'Àlgebra, així com
els objectes combinatoris i els grafs, els quals us presentarem en aquesta assignatura de Matemàtica Discreta. Cal dir que hi ha molts altres temes de
Matemàtica Discreta com, per exemple, els codis, la criptografia i les màquines d'estats finits, els quals apareixen en d'altres matèries del grau d'Enginyeria Informàtica. El motiu de la seva inclusió en aquests estudis rau en les moltes aplicacions que tenen en la Informàtica, ja que precisament els ordinadors guarden i manipulen la informació de manera discreta (“mitjançant seqüències de zeros i uns”). El programa que us presentem consta d'un apropament a la Teoria de Grafs i d'una introducció a la Combinatòria Enumerativa.
L'assignatura s'impartirà al llarg del 1er. quatrimestre amb quatre hores a la setmana: començant amb la part de Teoria de Grafs i continuant amb la part de Combinatòria Enumerativa.
Requisits per cursar-la
Prerequisits
Corequisits
Professorat
Nom
Correu
Horari de consulta
Crèdits teòrics
Crèdits pràctics
Nacho Lopez Lorenzo
nlopez@matematica.udl.cat
10.8
Competències
Competències estratègiques de la Universitat de Lleida
Competències específiques de la titulació
Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
Objectius
Utilitza la representació d'un graf més adient en cada problema.
Reconeix quines situacions poden modelitzar-se mitjançant grafs.
Determina si dos grafs d'ordre petit són isomorfs entre si.
Distingeix entre les dues estratègies bàsiques de cerca (per fondària prioritària i per amplada prioritària) i aplica la més adient en cada cas.
Determina si un graf és connex i, en cas afirmatiu, analitza el seu grau de connectivitat.
Calcula els paràmetres mètrics bàsics d'un graf: distàncies, excentricitats, radi i diàmetre.
Aplica l'algorisme de Dijkstra per calcular distàncies i camins mínims en un graf ponderat.
Identifica quines situacions corresponen a la cerca d'un recorregut eulerià i quines altres a un recorregut hamiltonià.
Demostra si un graf és eulerià i, en cas afirmatiu, troba un circuit eulerià del mateix.
Analitza el caràcter hamiltonià d'un graf.
Identifica els arbres i enumera les seves propietats bàsiques.
Representa, mitjançant un arbre binari, l'esquema de cerca dicotòmica i la construcció d' un codi binari lliure de prefixos.
Reconeix en quines situacions es requereix l'acoloriment (òptim) d'un graf.
Avalúa l'eficiència dels diferents algorismes bàsics sobre grafs.
Coneix els principis elementals d'enumeració combinatòrica.
Competències transversals de la titulació
Capacitat per a l'abstracció i el raonament crític, lògic i matemàtic.
Capacitat de resolució de problemes i elaboració i defensa d'arguments dins de la seva àrea d'estudis.
Objectius
Reconeix quines situacions poden modelitzar-se mitjançant grafs.
Continguts
Continguts de la matèria
I. APROPAMENT A LA TEORIA DE GRAFS
1. Grafs: conceptes bàsics.
1.0Els grafs com a models matemàtics: exemples històrics i aplicacionsactuals.
1.1Definició de graf.
1.2Grau d'un vèrtex. Lema de les encaixades de mans.
1.3Representació d'un graf.
1.4Isomorfisme de grafs.
1.5Exemples importants de grafs.
1.6Operacions amb grafs.
2. Connexió i distàncies.
2.1 Recorreguts en un graf.
2.2 Grafs connexos: definició ipropietats.
2.3Test de connexió basat en l'estratègia DFS.
2.4Distàncies en un graf: excentricitat d'un vèrtex i diàmetre.
2.5 Algorismes per al còmput de distàncies: BFS, Dijkstra.
3. Grafs eulerians i grafs hamiltonians.
3.1Grafs eulerians: definició i caracterització.
3.2Construcció d'un circuit eulerià: algorisme de Hierholzer.
3.3Grafs hamiltonians: definició, condicions necessàries i condicionssuficients.
4. Arbres.
4.1Definició i propietats bàsiques.
4.2Arbres generadors: definició i estratègies de construcció.
4.3Arbre generador de pes mínim: algorisme de Kruskal.
4.4Arbres amb arrel. Arbres m-aris. Aplicacions.
4.5Els codis de Huffman.
5. Breu introducció a d'altres temes sobregrafs.
5.1Planaritat.
5.2Coloració.
II. INTRODUCCIÓ A LA COMBINATÒRIA ENUMERATIVA
6. Principis i objectes combinatoris bàsics.
6.0Introducció.
6.1Principis bàsics d'enumeració.
6.2Seleccions ordenades: permutacions.
6.3Seleccions no ordenades: combinacions.
6.4Coeficients binomials.
6.5Principi d'inclusió-exclusió.
Bibliografia
Bibliografia recomanada
Material relatiu a la part de Combinatòria:
Gimbert, J., Moreno R., Valls M., Notes sobre Combinatòria, Quadern EUP núm. 36, 2002.
Material relatiu a la part de Grafs:
Gimbert, J., Moreno, R., Ribó, J.M., Valls, M., Apropament a la Teoria de Grafs i als seus Algorismes, Edicions de la UdL, 1998.
Recull d'exàmens:
Gimbert, J., López, N., Moreno, R., Valls, M., Recull d'Exàmens de Matemàtica
Bibliografia bàsica
LLIBRES DE TEORIA (amb enunciats de problemes)
Anderson, I., Introducción a la Combinatoria. Vicens Vives, 1993.
Brunat, J.M., Combinatòria i Teoria de Grafs. Edicions UPC, 1996.
Gimbert, J., Moreno, R., Ribó, J.M., Valls, M., Apropament a la Teoria de Grafs i als seus Algorismes. Edicions de la UdL, 1998.
Gimbert, J., Moreno R., Valls M., Notes sobre Combinatòria. Quadern EUP núm. 36, 2002.
LLIBRES DE PROBLEMES RESOLTS
Bijedić, N., Gimbert J., Miret J.M., Valls M., Elements of Discrete Mathematical Structures for Computer Science, Univerzitetska knjiga Mostar and Edicions de la UdL, 2007.
García, F., Hernández, G., Nevot, A., Problemas resueltos de Matemática Discreta. Thomson, 2003.