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

  • Enric Ventura Capell ( )

Altres

  • Guillem Perarnau Llobet ( )
  • Marc Noy Serrano ( )

Hores setmanals

Teoria
3
Problemes
1.5
Laboratori
0.5
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
    Competències relacionades: CE1, CT6, CB1,
  2. Comprendre l'aritmètica bàsica dels enters i polinomis, especialment els aspectes computacional
    Competències relacionades: CE1, CG5,
  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: CE1, CT5, 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 i polinomis
    Divisibilitat d'enters. Màxim comú divisor. Congrüències. Divisibilitat i congrüències de polinomis. Arrels i factorització.
  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:

Addenda

Continguts

No hi ha canvis respecte la informació publicada a la guia docent.

Metodologia docent

No hi ha canvis respecte la informació publicada a la guia docent.

Mètode d'avaluació

No hi ha canvis respecte la informació publicada a la guia docent.

Pla de contingència

El pla de contingència en cas que la situació sanitària forcés el pas a docència no presencial seria el següent: - Els examens es faran presencials (dividint en subgrups i en varios dies si cal) a menys que hi hagi ordre explícita de les autoritats acadèmiques en sentit contrari. Per les classes de teoria: - videos de tablet+veu gravats i penjats a Atenea, corresponents cronològicament a les classes que hauria tocat fer presencialment, i seguint aproximadament el mateix ritme que si fossin presencials. Aquests videos quedaran tots disponibles acumulativament fins a finals de curs per poder ser consultats en qualsevol moment. - sessions de videoconfrència periòdiques (una cada setmana / 15 dies) amb els estudiants interessats per resoldre dubtes i qüestions sobre el temari de l'assignatura, i per fer exercicis teòrics. - Disponibilitat del professor per resoldre dubtes concrets via e-mail. Per les classes de problemes: - Combinació de videos gravats i de videoconferències per a resoldre problemes de la llista, equivalents també (en quan a hores i a ritme) a les classes que hauria tocat fer presencialment. S'aniran alternant els dos tipus (video gravat, i videoconferències síncrones en l'horari de classe) segons l'evolució de la situació, necessitats puntuals, i preferència dels estudiants. - Disponibilitat del professor per resoldre dubtes concrets via e-mail.