Lògica i Matemàtica Discreta

Esteu aquí

Inici » Estudis » Màsters » Màster en Innovació i Recerca en Informàtica » Pla d'estudis » Assignatures » Lògica i Matemàtica Discreta
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.

Professorat

Responsable

  • Marc Noy Serrano ( )

Altres

  • Guillem Perarnau Llobet ( )
  • Tassio Naia Dos ( )

Hores setmanals

Teoria
3
Problemes
1.5
Laboratori
0.5
Aprenentatge dirigit
0
Aprenentatge autònom
7.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 [Avaluable] - 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
    Competències relacionades: CB1, CT6, CE1,
  2. Comprendre l'aritmètica bàsica dels enters i polinomis, especialment els aspectes computacional
    Competències relacionades: CG5, CE1,
  3. Conèixer els resultat bàsics de la combinatòria enumerativa
    Competències relacionades: CE1, CG5,
  4. Conèixer els resultats bàsics de la teoria de grafs, amb èmfasi en els problemes algorísmics
    Competències relacionades: CT5, CE1, CG5,

Continguts

  1. Conjunts i demostracions.
    El llenguatge de la teoria de conjunts. Demostracions en matemàtiques. El mètode d'inducció.
  2. Càlcul proposicional i de predicats
    Fòrmules booleanes. Assignació i taules de veritat. Satisfactibilitat. Lògica de primer ordre.
  3. Aritmètica d'enters, polinomis, i nombres complexes
    Divisibilitat d'enters. Màxim comú divisor. Congrüències. Divisibilitat i congrüències de polinomis. Arrels i factorització. Nombres complexos (forma binomial, polar i exponencial de Moivre).
  4. Enumeració bàsica i recurrències
    Permutacions, conjunts i multiconjunts. Nombres binomials. Principi d'inclusió i exclusió.
    Equacions recurrents. Resolució d'equacions recurrents lineals.
  5. Grafs i abres
    Conceptes bàsics de teoria de grafs. Distàncies i connectivitat. Representació i exploració de grafs. Grafs eulerians.
    Arbre generador minimal: algorismes de Kruskal i Prim.
  6. Planaritat i coloració
    Grafs planaris. Fòrmula d'Euler. Coloració de grafs. Algorismes de coloració.

Activitats

Activitat Acte avaluatiu


Resolució de problemes


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

Metodologia docent

En les classes de teoria s'exposa la matèria, complementant-la amb exemples i aplicacions. En les sessions de problemes es discutiran problemes d'una llista, fomentant la participació activa dels estudiants.

Mètode d'avaluació

Examen parcial (40%) i examen final (60%). El dia de l'examen final hi haurà la possibilitat de recuperar la nota del parcial.
Hi haurà un examen de reavaluació pels estudians suspesos que substituirà el 100% de la nota de l'assignatura.

Bibliografia

Bàsica: