Lògica i Matemàtica Discreta

Crèdits
7.5
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
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

  • Anna De Mier Vinué (anna.de.mier@upc.edu)

Altres

  • Guillem Perarnau Llobet (guillem.perarnau@upc.edu)
  • Xavier Povill Clarós (xavier.povill@upc.edu)

Hores setmanals

Teoria
3
Problemes
2
Laboratori
0
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: 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. Connectivitat i distància. Tipus de recorreguts i exploració de grafs. Arbres i arbres generadors. Coloració. Planaritat.

    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ó

    Hi haurà un examen parcial (EP) sobre la primera meitat del curs i un examen final (EF) sobre la segona meitat. De forma opcional, el dia de l'examen final hi haurà la possibilitat de recuperar la nota del parcial (REC). En cas d'entregar aquest examen, substituirà la nota de EF.

    La nota final es calcula com:

    -Si no s'entrega aquest examen de recuperació, la nota final serà NF=0.5·EP+0.5·EF.

    -Si s'entrega l'examen de recuperació, la nota final serà NF=0.5·REC+0.5·EF.

    Hi haurà un examen de reavaluació (REAV) pels estudiants amb NF<5. En aquest cas, la nota definitiva del curs serà max(NF, REAV).

    Bibliografia

    Bàsic