Lògica i Matemàtica Discreta

Esteu aquí

Crèdits
7.5
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits

Departament
MAT
La matemàtica discreta és la branca de les matemàtiques amb una relació més directa amb la teoria de la computació; de fet, el seu gran desenvolupament al segle passat es deu en bona part a l'aparició de la informàtica.
El curs introdueix diverses matèries interrelacionades –lògica, aritmètica, combinatòria i teoria de grafs—, que són el fonament de la matemàtica discreta. La presentació dels temes farà èmfasi en els aspectes algorísmics i computacionals.

Professors

Responsable

  • Marc Noy Serrano ( )

Altres

  • Anna De Mier Vinué ( )
  • Juan José Rue Perna ( )

Hores setmanals

Teoria
3
Problemes
1
Laboratori
1
Aprenentatge dirigit
0.333
Aprenentatge autònom
5

Competències

Competències Tècniques

Competències tècniques

  • CE1 - Utilitzar amb destresa els conceptes i mètodes matemàtics subjacents els problemes de la ciència i l'enginyeria de les dades.

Competències Transversals

Transversals

  • CT5 - Ús solvent dels recursos d'informació. Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació en l'àmbit de l'especialitat i valorar de forma crítica els resultats d'aquesta gestió.
  • CT6 - Aprenentatge autònom. Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement.

Bàsiques

  • CB1 - Que els estudiants hagin demostrat posseir i comprendre coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es recolza en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda del seu camp d'estudi.

Competències Tècniques Generals

Genèriques

  • CG5 - Poder recórrer a coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics del futur.

Objectius

  1. Conéixer el llenguatge de la lògica matemàtica
    Related competences: CE1, CT6, CB1,
  2. Comprendre l'aritmètica bàsica dels enters i polinomis, especialment els aspectes computacional
    Related competences: CE1, CG5,
  3. Conèixer els resultat bàsics de la combinatòria enumerativa
    Related competences: CE1, CG5,
  4. Conèixer els resultats bàsics de la teoria de grafs, amb èmfasi en els problemes algorísmics
    Related competences: CE1, CT5, CG5,

Continguts

  1. Càlcul proposicional
    Fòrmules booleanes. Assignació i taules de veritat. Satisfabilitat. Fòrmules de primer ordre. Satisfabilitat. Formes normals.
  2. Aritmètica d'enters i polinomis
    Divisibilitat d'enters. Màxim comú divisor. Congrüències. Divisibilitat i congrüències de polinomis. Arrels i factorització.
  3. Enumeració bàsica i recurrències
    Permutacions, conjunts i multiconjunts. Nombres binomials. Principi d'inclusió i exclusió.
    Equacions recurrents. Resolució d'equacions recurrents lineals.
  4. Grafs i abres
    Concepts bàsics de teoria de grafs. Distàncies i connectivitat. Representació i exploració de grafs.
    Arbres arrealts i no arrelats. Arbre generador minimal: algorismes de Kruskal i Prim.
  5. Planaritat i coloració
    Grafs planaris. Fòrmula d'Euler. Coloració de grafs. Algorismes de coloració.
  6. Fluxos en xarxes i aparellaments
    Fluxos en xarxes. Algorisme de Ford-Fulkerson. Aparellaments bipartits.

Activitats

Resolució de problemes

Teoria
0
Problemes
0
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
0
Objectius: 1 2 3 4

Mètode d'avaluació

Examen parcial (40%) i examen final (60%)

Bibliografia

Bàsica: