Anar al contingut (clic a Intro)
UdG Home UdG Home
UdG 30 anys
Tancar
Menú

Estudia a la UdG

Dades generals

Curs acadèmic:
2011
Descripció:
Matemàtica discreta
Crèdits:
6
Idioma principal de les classes:
Català
S’utilitza oralment la llengua anglesa en l'assignatura:
Gens (0%)
S’utilitzen documents en llengua anglesa:
Poc (25%)

Grups

Grup A

Durada:
Semestral, 2n semestre
Professorat:

Grup B

Durada:
Semestral, 2n semestre
Professorat:

Competències

  • Ser capaç d'analitzar, dissenyar i implementar un algorisme i la seva estructura de dades.
  • Aplicar eines i coneixements matemàtics
  • Ser capaç d'analitzar i sintetitzar problemes.
  • Ser capaç d'organitzar i planificar
  • Comunicar-se adequadament tant de forma oral com escrita.
  • Resolució de problemes i anàlisi crítica de resultats
  • Raonament crític

Altres Competències

  • Identificar i resoldre problemes de combinatòria.
  • Utilitzar els grafs per a modelar estructures finites i discretes.
  • Dissenyar, implementar i aplicar algorismes de teoria de grafs.

Continguts

1. INTRODUCCIÓ A L'ANÀLISI COMBINATÒRIA

          1.1. Problemes de l'anàlisi combinatòria.

          1.2. Permutacions amb i sense repetició.

          1.3. Combinatòries amb i sense repetició.

          1.4. Els coeficients binomials: significat i algunes propietats.

          1.5. Principi d'inclusió-exclusió.

2. INTRODUCCIÓ ALS GRAFS

          2.1. Generalitats.

          2.2. Grafs.

                    2.2.1. Definicions.

                    2.2.2. Propietats.

                    2.2.3. Tipus especials de grafs.

                    2.2.4. Isomorfisme de grafs.

                    2.2.5. Subestructures de grafs.

                    2.2.6. Seqüència de graus d'un grafs.

          2.3. Variants de grafs.

                    2.3.1. Grafs dirigits.

                    2.3.2. Multigrafs.

                    2.3.3. Grafs ponderats.

          2.4. Connexió i components.

          2.5. Grafs plans.

          2.6. Coloració d'un graf.

          2.7. Emmagatzematge d'un graf en memòria.

                    2.7.1. Matriu d'adjacència.

                    2.7.2. Llistes d'adjacència

3. RECORREGUTS I CAMINS MÍNIMS

          3.1. Recorregut d'un graf.

                    3.1.1. Recorregut en profunditat.

                    3.1.2. Recorregut en amplada.

          3.2. Camins mínims.

                    3.2.1. Algorisme de Dijkstra.

                    3.2.2. Algorisme de Ford.

                    3.2.3. Algorisme de Floyd.

4. ARBRES GENERADORS

          4.1. Conceptes generals.

          4.2. Arbres generadors minimals.

                    4.2.1. Algorisme de Kruskal.

                    4.2.2. Algorisme de Prim.

5. GRAFS EULERIANS I HAMILTONIANS

          5.1. Caracterització dels camins i dels circuits eulerians.

          5.2. Algorisme de Hierholzer.

          5.3. Problema del carter xinès. Algorisme d'Edmonds.

          5.4. Caracterització dels camins i dels circuits hamiltonians.

          5.5. Algorisme de Roberts i Flores.

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Total
Prova d'avaluació 5,00 16,00 21,00
Sessió expositiva 0 93,00 93,00
Sessió pràctica 0 20,00 20,00
Total 5,00 129,00 134

Bibliografia

  • Basart i Muñoz, Josep M (1994). Grafs, : fonaments i algorismes. Bellaterra: Publicacions de la Universitat Autònoma de Barcelona.
  • García Merayo, Félix (2001). Matemática discreta. Madrid: Paraninfo.
  • García Merayo, Félix, Nevot Luna, Antonio, Hernández Peñalver, Gregorio (2003). Problemas resueltos de matemática discreta. Madrid: International Thomson.
  • Grimaldi, Ralph P (1989). Matemáticas, : discreta y combinatoria: introducción y aplicaciones. Argentina [etc.]: Addison-Wesley Iberoamericana.
  • Trias Pairó, Joan (2001). Matemàtica discreta : problemes resolts. Barcelona: Edicions UPC.

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Tema 1 Es realitzarà un examen tipus test al finalitzar el semestre 20
Tema 2 15
Tema 3 15
Tema 4 15
Tema 5 15
Examen de pràctiques. Té una puntuació màxima de 2 punts i la nota serveix per a les dues convocatòries. La data de l'examen es notificarà amb antelació a la pàgina web de l'assignatura i serà al final del semestre, abans del període d'exàmens. 20
Examen final L’examen constarà de dues parts:

grafs, amb una puntuació màxima de 6 punts i
combinatòria (tipus test), amb una puntuació màxima de 2 punts.
80

Qualificació

La nota final serà la suma de les notes corresponents a la part de pràctiques (20%), la part de combinatòria (20%) i la part de grafs (60%)

Criteris específics de la nota «No Presentat»:
Un alumne l'hi constarà un NP en el seu expedient si no es presenta als exàmens corresponents a cadascuna de les convocatòries oficials

Observacions

Prerequisits:
És necessari tenir els coneixements mínims de Matemàtiques a nivell de batxillerat, a destacar l’àlgebra de matrius. També és recomanable tenir uns coneixements mínims sobre programació.

Mètodes docents:
L'assignatura no té assignada cap mena de classes presencials. L'alumne s'haurà de preparar l'assignatura basant-se en la bibliografia i el dossier d'exercicis que trobarà a disposició a la pàgina web de l'assignatura. Les sessions de pràctiques també les haurà de preparar pel seu compte.

L'alumne també podrà assistir a les classes de l'assignatura Lògica i Matemàtica Discreta del Grau en Informàtica i demanar sessions de tutoria al responsable de l'assignatura.

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.