Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Matemàtica discreta (MATD)

Crèdits Dept. Tipus Requisits
9.0 (7.2 ECTS) MAT
  • Obligatòria per a l'EI
  • Optativa per a l'ETIG
  • Optativa per a l'ETIS
AL - Pre-requisit per la EI , ETIG , ETIS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

L'objectiu general de l'assignatura és posar a l'abast de l'estudiant un conjunt
de conceptes i tècniques propis de la matemàtica discreta i de l'àlgebra que, per la seva ubiquïtat en el món de les tecnologies noves, són part de la formació bàsica de tot enginyer en informàtica.

Objectius Específics

Coneixements

  1. Conèixer els principis bàsics d'enumeració: principi d'identitat, d'addició del producte, del colomar i d'inclusió-exclusió. Conèixer els principals nombres combinatoris: binomials, multinomials, de Catalan, de desarranjaments, etc.
  2. Conèixer les funcions generadores ordinàries i exponencials associades a una successió. Conèixer les recurrències lineals.
  3. Conèixer l'estructura de graf com a model matemàtic i les diferents formes de donar un graf. Conèixer els diferents recorreguts que es poden definir en un graf, i els conceptes de connexió i connectivitat associats. Conèixer les caracteritzacions del grafs eulerians. Conèixer la definició de graf hamiltonià, i la dificultat associada per reconèixer un graf hamiltonià.
  4. Conèixer els grafs que són arbres. Conèixer algorismes per trobar arbres generadors d'un graf connex amb pesos i sense pesos. Conèixer el nombre d'arbres generadors d'un graf.
  5. Conèixer l'estructura de cos de Z_p (els enters mòdul un primer p) i la d'anell de polinomis amb coeficients a Z_p. Saber què és un polinomi irreductible i conèixer el teorema de factorització única. Saber construir cossos finits i conèixer l'existència i la unicitat.

Habilitats

  1. Saber aplicar els principis bàsics d'enumeració. Saber reconèixer quin tipus d'estructures compten cada tipus de nombre combinatori.
  2. Saber descomposar un funció racional en fraccions simples. Saber operar amb funcions generadores. Saber plantejar problemes d'enumeració en termes de recurrències. Saber traduir recurrències a funcions generadores.
    Saber resoldre recurrències.
  3. Saber modelar problemes en termes de grafs. Saber aplicar els algorismes per obtenir un circuit eulerià i un recorregut eulerià. Saber aplicar a exemples senzills algunes condcions suficients de hamiltoneitat. Saber formar la matriu d'adjacència d'un graf i traduir propietats elementals d'un graf a propietats de la seva matriu d'adjacència.
  4. Saber aplicar els algorismes d'obtenció d'arbres generadors d'un graf. Saber aplicar els algorismes d'obtenció d'arbres generadors de cost mínim. Saber calcular el nombre d'arbres generadors d'un graf.
  5. Saber operar a Z_p amb p primer, en particular saber calcular inversos.
    Saber operar amb polinomis amb coeficients a Z_p. Saber les propietats de les arrels. Saber construir cossos finits. Saber operar en un cos finit.
    Saber operar en cossos finits emprant la forma polinòmica dels seus elements i emprant logaritmes discrets. Saber operar amb polinomis amb coeficients en un cos finit.

Competències

  1. Capacitat per al raonament crític i lògico-matemàtic
  2. Capacitat per aplicar les tècniques per construir demostracions lògico-matemàtiques.
  3. Capacitat per transformar enunciats informals a enunciats formals, i a l'inrevés.
  4. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
  5. Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Principis d'enumeració
T      P      L      Alt    L Ext. Est    A Ext. Total 
8,0 8,0 0 0 0 21,0 0 37,0
Principis d'igualtat, d'addició i del producte. Nombres binomials. Multiconjunts. Nombres multinomials. Nombres de Catalan. Particions d'un enter. Principi d'inclusió-exclusió. Principi del colomar.

2. Funcions generadores
T      P      L      Alt    L Ext. Est    A Ext. Total 
7,0 7,0 0 0 0 19,0 0 33,0
Fraccions parcials. Successions i funcions generadores. Recurrències lineals. Nombres de catalan. Particions. Funció generadora exponencial. Desarranjaments. Nombres de Stirling i nombres de Bell.

3. Grafs
T      P      L      Alt    L Ext. Est    A Ext. Total 
8,0 8,0 0 0 0 21,0 0 37,0
Definicions. Isomorfisme. Graus i lema de les encaixades. Recorreguts, camins, distància, connexió i connectivitat. Operacions amb grafs. Grafs eulerians. Grafs hamiltonians. Representació matricial d'un graf.

4. Arbres
T      P      L      Alt    L Ext. Est    A Ext. Total 
6,0 7,0 0 0 0 18,0 0 31,0
Definició i caracteritzacions d'arbres. Arbres generadors. Obtenció per recerca en amplada i en profunditat. Nombre d'arbres generadors d'un graf. Arbres generadors minimals. Algorismes de Kruskal i de Prim.

5. Polinomis i cossos finits.
T      P      L      Alt    L Ext. Est    A Ext. Total 
7,0 8,0 0 0 0 20,0 0 35,0
Els anells Z_p de classes de residus mòdul un enter primer. Anell de polinomis amb coeficients a Z_p.
Màxim comú divisor i identitat de Bezout. Polinomis irreductibles i factorització única.
Arrels. Quocients mòdul un polinomi. Construcció de cossos.
finits. Logaritme discret.
Polinomis sobre cossos finits. Operar en un cos finit


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
36,0 38,0 0 0 0 99,0 0 173,0
Hores addicionals dedicades a l'avaluació 7,0
Total hores de treball per l'estudiant 180,0

Metodologia docent

Les classes de teoria responen a l'esquema clàssic de classe magistral, avantualment ajudada per l'ús de retroprojector o demostració computacional.

Les classes de problemes són participatives, amb explicació per part dels estudiants de problemes encarregats prèviament i de discussió col.lectiva de problemes prèviament marcats.

Mètode d'avaluació

L'avaluació és contínua preferentment i es basa en les proves següents:

P1: examen de la part inicial del temari,
P2: examen de la part intermitja del temari,
P3: examen de la part final del temari.

La nota final es calcula com segueix:
Nota = 0.2*P1+0.4*P2+0.4*P3, (P1,P2,P3 són notes sobre 10).

Qui no segueixi l'avaluació contínua o vulgui renunciar-hi haurà de realitzar un examen del temari complet, i la nota corresponent serà la que li quedarà com a nota final. En aquest cas, l'estudiant haurà de comunicar al coordinador que renúncia a l'avaluació contínua, com a molt tard, l'últim dia de classes del quadrimestre i pels canals que es publicaran al Racó.

Bibliografía bàsica

  • Francesc Comellas ... [et al.] Matemática discreta, Edicions UPC, 2001.
  • Norman L. Biggs Matemática discreta, Vicens-Vives, 1994.
  • Ralph P. Grimaldi Matemáticas discreta y combinatoria : una introducción con aplicaciones, Addison-Wesley Iberoamericana, 1997.

Bibliografía complementària

  • Josep M. Brunat Combinatòria i teoria de grafs, Edicions UPC, 1997.
  • Joan Trias Pairó Matemàtica discreta : problemes resolts, Edicions UPC, 2001.
  • Jiri Matousek and Jaroslav Nesetril Invitation to discrete mathematics, Clarendon Press : Oxford University Press, 1998.
  • Kenneth H. Rosen Matemática discreta y sus aplicaciones, McGraw-Hill, 2004.

Enllaços web

(Informació no introduïda)

Capacitats prèvies

Conéixer les operacions i relacions amb conjunts: reunió, intersecció, diferència, producte cartesià, inclusió.
Conéixer els diferents tipus d'aplicacions.
Saber comptar combinacions i permutacions amb i sense repetició.
Conéixer les propietats elementals dels nombres binomials, i saber calcular-los.

Saber calcular el mcd de nombres enters i els coeficients de la identitat de Bezout mitjançant l'algorisme d'Euclides.

Saber calcular productes de matrius i saber calcular determinants.

Saber els continguts de l'assignatura AL.


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil