Teoria de la Computació

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació)
Requisits
Departament
CS
Web
www.cs.upc.edu/tc/
Des d'un punt de vista pràctic, la teoria de la computació proporciona als alumnes mètodes de descripció i tractament de llenguatges. Depenent del mètode utilitzat, s'obtenen millors o pitjors propietats expressives i computacionals. Aquests mètodes troben aplicacions en àrees com compiladors, gràfics, llenguatges de programació i algorísmia. Però de fet, aquests coneixements són la base per a qualsevol altra àrea de les ciències de la computació, i és habitual trobar-los, per exemple, en articles de recerca de congressos de bases de dades o arquitectura de computadors. A part de les aplicacions, TC és una assignatura de fonament, doncs estudia quins són els límits computacionals de les màquines amb què treballem avui en dia. A més a més, el seu estudi ajuda a desenvolupar habilitats que són de gran ajuda en qualsevol altre àmbit, tals com la capacitat de descriure la informació sense ambigüitats, fer un anàlisi de casos acurat i exhaustiu, o produir una argumentació correcta.

Professorat

Responsable

  • Antoni Lozano Boixadors (antoni.lozano@upc.edu)
  • Ilario Bonacina (ilario.bonacina@upc.edu)

Altres

  • Arnau Messegué Buisan (arnau.messegue@upc.edu)
  • Enrique Romero Merino (eromero@cs.upc.edu)

Hores setmanals

Teoria
1.4
Problemes
1.5
Laboratori
1.2
Aprenentatge dirigit
0.2
Aprenentatge autònom
5.7

Competències

Competències Transversals

Raonament

  • G9 [Avaluable] - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.
    • G9.3 - Capacitat crítica, capacitat d'avaluació.

    • Aprenentatge autònom

  • G7 [Avaluable] - Detectar carències en el coneixement propi i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement. Capacitat per a l'aprenentatge de nous mètodes i tecnologies, i versatilitat per a adaptar-se a noves situacions.
    • G7.3 - Aprenentatge autònom: capacitat de planificació i organització del treball personal. Aplicar els coneixements adquirits a la realització d'una tasca en funció de la pertinença i de la importància, decidir la manera de dur-la a terme i el temps que se li ha de dedicar, i seleccionar les fonts d'informació més adients. Identificar la importància d'establir i mantenir contactes amb els companys d'estudis, amb el professorat i amb els professionals (networking). Identificar fòrums d'informació sobre enginyeria TIC, els seus avenços i el seu impacte en la societat (IEEE, associacions, etc.).

    • Competències Tècniques de cada especialitat

    Especialitat computació

  • CCO1 - Tenir un coneixement profund dels principis fonamentals i dels models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics, relacionats amb la informàtica.
    • CCO1.1 - Avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin dur a la seva resolució, i recomanar, desenvolupar i implementar la que garanteixi el millor rendiment d'acord amb els requisits establerts.
    • CCO1.2 - Demostrar coneixement dels fonaments teòrics dels llenguatges de programació i les tècniques de processament lèxic, sintàctic i semàntic associades, i saber aplicar-les per a la creació, el disseny i el processament de llenguatges.
    • CCO1.3 - Definir, avaluar i seleccionar plataformes de desenvolupament i producció hardware i software per al desenvolupament d'aplicacions i serveis informàtics de diversa complexitat.
  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.2 - Capacitat per a adquirir, obtenir, formalitzar i representar el coneixement humà d'una forma computable per a la resolució de problemes mitjançant un sistema informàtic en qualsevol àmbit d'aplicació, particularment en els que estan relacionats amb aspectes de computació, percepció i actuació en ambients o entorns intel·ligents.
  • CCO3 - Desenvolupar les solucions informàtiques que, considerant l'entorn d'execució i l'arquitectura del computador sobre el qual s'executen, aconsegueixin el millor rendiment.
    • CCO3.1 - Implementar codi crític seguint criteris de temps d'execució, eficiència i seguretat.

    • Objectius

    1. Aprendre a classificar problemes dins de les clases de complexitad. En particular, aprendre tècniques que permeten determinar quan un conjunt és regular, incontextual, polinòmic, exponencial, decidible o semidecidible.
      Competències relacionades: G9.3, CCO1.1, CCO1.2,
    2. Aprendre a descriure llenguatges segons sistemes formals com autòmats i gramàtiques incontextuals. Conéixer les capacitats computacionals d'aquests formalismes i les seves aplicacions pràctiques.
      Competències relacionades: G9.3, CCO1.1, CCO1.2, CCO1.3, CCO2.2, CCO3.1,
    3. Resoldre problemes teòrics i pràctics d'aquesta matèria i fer presentacions públiques de les solucions obtingudes.

      Competències relacionades: G9.3, CCO1.1, CCO1.2, G7.3,

    Continguts

    1. Introducció matemàtica.
      Conjunts, tuples, relacions, funcions i homomorfismes. Mètodes de demostració.
    2. Llenguatges formals.
      Alfabets, mots, llenguatges, operacions sobre llenguatges (concatenació, revessat, estrella). Classes de llenguatges i tancament per operacions.
    3. Autòmats finits.
      Autòmats finits deterministes, autòmats finits indeterministes, autòmats finits amb lambda-transicions, equivalència entre models d'autòmats, operacions sobre autòmats, minimització d'autòmats.
    4. Expressions regulars.
      Expressions regulars, equivalència amb autòmats i Lema d'Arden, operacions sobre expressions regulars.
    5. Gramàtiques incontextuals.
      Gramàtiques incontextuals, llenguatge generat per una gramàtica, àrbre de derivació, ambigüitat, operacions sobre gramàtiques, depuració de gramàtiques. Algorisme CYK i "parsing".
    6. Autòmats amb pila.
      Autòmats amb pila indeterministes i la seva equivalència amb llenguatges incontextuals, autòmats amb pila deterministes, autòmats amb pila d'acceptació única i la seva equivalència amb llenguatges incontextuals no ambigus, operacions de tancament.
    7. No regularitat i no incontextualitat.
      Demostracions de no regularitat pel lema de bombament, per propietats de tancament i per extensions distingidores. Demostracions de no incontextualitat pel lema de bombament per incontextuals i per propietats de tancament.
    8. Màquines de Turing.
      Màquines de Turing deterministes, indeterministes i amb diverses cintes, equivalència de màquines de Turing i algorismes d'alt nivell. Màquina de Turing universal i tesi de Church-Turing.
    9. Decidibilitat, semi-decidibilitat, computabilitat.
      Llenguatges decidibles, llenguatges semi-decidibles, funcions computables, operacions de tancament, teorema del complementari, teorema de projecció, jerarquia aritmètica.
    10. No decidibilitat, no semi-decidibilitat, no computabilitat.
      Diagonalització. Llenguatges semidecidibles però indecidibles (K, HALT). Reduccions "many-one" per tal de demostrar no decidibilitat i no semi-decidibilitat, equivalència entre no semi-decidibilitat i no computabilitat. Exemples de problemes naturals indecidibles: intersecció no buida i ambigüitat de gramàtiques incontextuals, totalitat de gramàtiques incontextuals.
    11. Elements de teoria de la complexitat
      Definició formal de les classes P, NP i coNP. Reduccions en temps polinòmic i NP-completesa. Teoremes de jerarquia de temps. Complexitat en espai. Jerarquia polinòmica.

    Activitats

    Activitat Acte avaluatiu


    Aprenentatge del tema "Teoria de llenguatges".

    Els estudiants assisteixen a classe de teoria (T: 2h) i completen els conceptes teòrics introduïts amb l'estudi de la bibliografia o visionant els vídeos indicats d'aquest tema (AA: 4h). A més assisteixen a de problemes sobre aquest tema (P: 2h).
    Objectius: 3
    Continguts:
    Teoria
    2h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Aprenentatge del tema "Llenguatges regulars".

    Els alumnes assisteixen a classe de teoria sobre aquest tema (T: 4h) i completen el conceptes teòrics introduïts amb l'estudi de la bibliografia o visionant els vídeos d'aquest tema (AA: 7h). Assisteixen a classe de laboratori i resolen els problemes a l'ordinador (L: 3h). També miren de resoldre els problemes assignats sobre aquest tema (AA: 7h) i assisteixen a la classe de problemes/laboratori on tots els alumnes presenten públicament les seves solucions (P: 4h).
    Objectius: 1 2 3
    Continguts:
    Teoria
    4h
    Problemes
    4h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    14h

    Aprenentatge del tema "Llenguatges incontextuals".

    Els alumnes assisteixen a classe de teoria sobre aquest tema (T: 4h) i completen el conceptes teòrics introduïts amb l'estudi de la bibliografia o visionant els vídeos d'aquest tema (AA: 7h). Assisteixen a classe de laboratori i resolen els problemes a l'ordinador (L: 3h). També miren de resoldre els problemes assignats sobre aquest tema (AA: 8h) i assisteixen a la classe de problemes/laboratori on tots els alumnes presenten públicament les seves solucions (P: 4h). Aquesta part inclou una revisió exhaustiva de la primera part del curs com a preparació per al primer examen parcial (AD: 1,5h).
    • Aprenentatge dirigit: Repàs dels temes per preparar l'examen parcial.
    Objectius: 1 2 3
    Continguts:
    Teoria
    4h
    Problemes
    4h
    Laboratori
    3h
    Aprenentatge dirigit
    1.5h
    Aprenentatge autònom
    15h

    Primer examen.

    Un examen de 3h de durada realitzat parcialment davant de l'ordinador i parcialment per escrit, on s'avalua l'habilitat de descriure llenguatges regulars i incontextuals.
    Objectius: 1 2
    Setmana: 7
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Aprenentatge del tema "Autòmats amb pila".

    Els alumnes assisteixen a classe de laboratori i resolen els problemes a l'ordinador (L: 3h). També miren de resoldre els problemes assignats sobre aquest tema (AA: 5h) i presentar públicament les seves solucions.
    Objectius: 1 2 3
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    5h

    Aprenentatge del tema "Teoria de la calculabilitat".

    Els alumnes assisteixen a classe de teoria sobre aquest tema (T: 4h) i completen el conceptes teòrics introduïts amb l'estudi de la bibliografia o visionant els vídeos d'aquest tema (AA: 5h). Assisteixen a classe de laboratori i resolen els problemes a l'ordinador (L: 3h). També miren de resoldre els problemes assignats sobre aquest tema (AA: 6,5h) i assisteixen a la classe de problemes/laboratori on tots els alumnes presenten públicament les seves solucions (P: 6,5h).
    Objectius: 1 3
    Continguts:
    Teoria
    4h
    Problemes
    6.5h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    11.5h

    Aprenentatge del tema "Elements de teoria de la complexitat".

    Els alumnes assisteixen a classe de teoria sobre aquest tema (T: 4h) i completen el conceptes teòrics introduïts amb l'estudi de la bibliografia o visionant els vídeos d'aquest tema (AA: 5h). També miren de resoldre els problemes assignats sobre aquest tema (AA: 7h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament les seves solucions (P: 6h). Aquesta part inclou una revisió exhaustiva de la segona part del curs com a preparació per al segon examen parcial i per a l'examen final (AD: 1,5h).
    • Aprenentatge dirigit: Repàs dels temes per preparar l'examen parcial.
    Objectius: 1 3
    Continguts:
    Teoria
    4h
    Problemes
    6h
    Laboratori
    0h
    Aprenentatge dirigit
    1.5h
    Aprenentatge autònom
    12h

    Segon examen

    Un examen de 3h de duració realitzat parcialment davant de l'ordinador i parcialment per escrit, on s'avalúa l'habilitat d'analitzar la regularitat o no i la incontextualitat de llenguatges, així com la decidibilitat de problemes i de construïr reduccions per a demostrar no decidibilitat i no semi-decidibilitat .
    Objectius: 1 2
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final.


    Objectius: 1 2
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    En les classes de teoria, el professor presenta els fonaments teòrics bàsics de cada tema i resol alguns problemes. Els estudiants aprofundeixen en la teoria durant el seu temps d'estudi personal utilitzant els recursos indicats pel professor (llibres, vídeos i altres materials complementaris).

    En les classes de problemes i en les sessions de laboratori, els estudiants exposen les solucions als problemes que se'ls han assignat prèviament. El professor intervé durant les explicacions per corregir errors o proposar millores. A més, pren notes sobre les presentacions dels estudiants per tenir-les en compte en l'avaluació final de l'assignatura. En les sessions de laboratori, els estudiants resolen problemes davant de l'ordinador que són avaluats automàticament.

    Mètode d'avaluació

    Aquesta assignatura es pot aprovar per avaluació continuada o amb examen final.

    La nota de l'avaluació continuada C s'obté sumant la nota dels 2 exàmens parcials del curs (els dos amb un pes del 40%) i la nota de l'avaluació de les presentacions a la pissarra dels problemes que s'han assignat als alumnes (amb un pes del 20%).

    Els estudiants que no es presentin a l'examen final tenen com a nota final (NF) la nota C de l'avaluació continuada.

    Els estudiants que es presentin a l'examen final (amb nota F) renuncien a la nota de l'avaluació continuada C com a nota final NF de curs i la nova nota final s'obté segons la fórmula:

    NF = max{ F, 0.5 F + 0.5 C }.


    Els estudiants que no es presentin a cap examen (Parcial 1, Parcial 2 i Examen Final) obtindran la qualificació NP ("No Presentat").

    L'avaluació de les competències G7.3, G9.1 i CCO1.1 la realitza cada professor individualment per a cada alumne del seu grup basant-se en les presentacions públiques de l'avaluació continuada. L'avaluació de les competències no afecta a l'avaluació de l'assignatura.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    * Capacitat d'expressar en fórmules lògiques els enunciats descrits en llenguatge natural.
    * Capacitat de manipular fórmules lògiques.
    * Coneixements algebraics fonamentals: aritmètica modular.
    * Coneixements bàsics de combinatòria.
    * Coneixement de les estructures de dades bàsiques i d'algorísmia fonamental.
    * Capacitat d'avaluar la complexitat temporal d'un algorisme.