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

Altres

Hores setmanals

Teoria
1
Problemes
1
Laboratori
2
Aprenentatge dirigit
0.2
Aprenentatge autònom
5.8

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. Llenguatges formals.
      Alfabets, mots, llenguates, operacions sobre llenguatges (concatenació, revessat, estrella), morfismes, sistemes de reescriptura.
    2. 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.
    3. 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.
    4. Expressions regulars.
      Expressions regulars, equivalència amb autòmats i Lema d'Arden, operacions sobre expressions regulars.
    5. 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, jerarquia de Chomsky.
    6. No regularitat i no incontextualitat.
      Demostracions de no regularitat per repetició d'estat i per transformacions que preserven la regularitat. Demostracions de no incontextualitat per repetició de variable.
    7. Màquines de Turing.
      Màquines de Turing deterministes, extensions indeterministes o amb vàries cintes, equivalència de màquines de Turing i algorismes d'alt nivell.
    8. Decidibilitat, semi-decidibilitat, computabilitat.
      Llenguatges decidibles, llenguatges semi-decidibles, funcions computables, operacions de tancament, teorema del complementari, teorema de projecció, connexions entre semi-decidibilitat i computabilitat.
    9. No decidibilitat, no semi-decidibilitat, no computabilitat.
      El llenguatge K, K és semi-decidible però no decidible, reduccions per tal de demostrar no decidibilitat i no semi-decidibilitat, equivalència entre no semi-decidibilitat i no computabilitat. Problemes naturals indecidibles: accessibilitat de mots per reescriptura, PCP, intersecció no buida i ambigüitat de gramàtiques incontextuals, universalitat de gramàtiques incontextuals i satisfactibilitat de lògica de paraules.
    10. 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.

    Activitats

    Activitat Acte avaluatiu


    Aprenentatge del tema "teoria de llenguatges".

    Els alumnes completen el conceptes teòrics introduïts en les classes de teoria amb l'estudi dels temes de la bibliografia bàsica indicats pel professor o visionant i entenent els vídeos d'aquest tema (AA:3h). També miren de resoldre els problemes assignats sobre aquest tema (AA:3h), assisteixen a classe de teoría i problemes sobre aquest tema i demanen al professor que resolgui els seus dubtes (T:2h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:2h).
    Objectius: 3
    Continguts:
    Teoria
    1h
    Problemes
    2h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Aprenentatge del tema "Autòmats finits".

    Els alumnes assisteixen a classe de teoría sobre aquest tema (T:2h), completen el conceptes teòrics introduïts en les classes de teoria amb l'estudi dels temes de la bibliografia bàsica indicats pel professor o visionant i entenent els vídeos d'aquest tema (AA:3h). Assisteixen a classe de laboratori i miren de resoldre els problemes davant de la màquina (L: 4h). També miren de resoldre els problemes assignats sobre aquest tema (AA:3h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:2h).
    Objectius: 1 2 3
    Continguts:
    Teoria
    2h
    Problemes
    2h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Aprenentatge del tema "Gramàtiques incontextuals".

    Els alumnes assisteixen a classe de teoría sobre aquest tema (T:2h), completen el conceptes teòrics introduïts en les classes de teoria amb l'estudi dels temes de la bibliografia bàsica indicats pel professor o visionant i entenent els vídeos d'aquest tema (AA:3h). Assisteixen a classe de laboratori i miren de resoldre els problemes davant de la màquina (L: 4h). També miren de resoldre els problemes assignats sobre aquest tema (AA:3h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:2h).
    Objectius: 1 2 3
    Continguts:
    Teoria
    2h
    Problemes
    2h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Aprenentatge del tema "Expressions regulars".

    Els alumnes tracten de visionar i entendre els vídeos d'aquest tema (AA:3h), miren de resoldre els problemes assignats sobre aquest tema (AA:3h), assisteixen a classe de laboratori sobre aquest tema i miren de resoldre els problemes devant de la màquina (L: 2h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:2h).
    • Aprenentatge dirigit: Repàs dels temes per preparar l'examen parcial.
    Objectius: 1 2 3
    Continguts:
    Teoria
    0h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    1.5h
    Aprenentatge autònom
    6h

    Primer examen.

    Un examen de 3h de duració 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 estudien la teoria a partir dels temes de la bibliografia indicats pel professor o visionant i entenent els vídeos d'aquest tema (AA:3h), miren de resoldre els problemes assignats sobre aquest tema (AA:3h), assisteixen a classe de laboratori sobre aquest tema i miren de resoldre els problemes devant de la màquina (L: 2h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:2h).
    Objectius: 1 2 3
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Aprenentatge del tema "No regularitat i no incontextualitat".

    Els alumnes completen els conceptes bàsics introduïts a classe de teoria (T: 1h) a partir dels temes de la bibliografia indicats pel professor o tracten de visionant i entenent els vídeos d'aquest tema (AA:3h), miren de resoldre els problemes assignats sobre aquest tema (AA:3h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:1h).
    Objectius: 1 3
    Continguts:
    Teoria
    1h
    Problemes
    1h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Aprenentatge del tema "Màquines de Turing".

    Els alumnes tracten de completar els conceptes introduïts a classe de teoria (T: 1h) estudiant els temes de la bibliografia bàsica indicats pel profesor o visionant i entenent els vídeos d'aquest tema (AA:3h), miren de resoldre els problemes assignats sobre aquest tema (AA:3h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:1h).
    Objectius: 1 3
    Continguts:
    Teoria
    1h
    Problemes
    1h
    Laboratori
    1h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Aprenentatge del tema "Decidibilitat, semi-decidibilitat, computabilitat".

    Els alumnes tracten de completar els conceptes introduïts a classe de teoria (T: 1h) estudiant els temes de la bibliografia bàsica indicats pel profesor o visionant i entenent els vídeos d'aquest tema (AA:3h), miren de resoldre els problemes assignats sobre aquest tema (AA:3h) i assisteixen a classe de laboratori sobre aquest tema i miren de resoldre els problemes davant de la màquina (L: 2h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:1h).
    Objectius: 1 3
    Continguts:
    Teoria
    1h
    Problemes
    1h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Aprenentatge del tema "No decidibilitat, no semi-decidibilitat, no computabilitat".

    Els alumnes tracten de comletar elc conceptes teòrics introduïts a la classe de teoria (T: 1h) estudiant els temes de la bibliografia bàsica indicats pel professor o visionant i entenent els vídeos d'aquest tema (AA:4h), miren de resoldre els problemes assignats sobre aquest tema (AA:4h), assisteixen a classe de laboratori sobre aquest tema i miren de resoldre els problemes devant de la màquina (L: 4h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:3h).
    Objectius: 1 3
    Continguts:
    Teoria
    2h
    Problemes
    3h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

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

    Els alumnes tracten d'entendre els conceptes teòrics corresponents estudiant el temes de la bibliografia bàsica indicats pel professor o de visionant i entenent els vídeos d'aquest tema (AA:4h), miren de resoldre els problemes assignats sobre aquest tema (AA:4h), assisteixen a classe de laboratori sobre aquest tema i miren de resoldre els problemes devant de la màquina (L: 4h) i assisteixen a la classe de problemes on tots els alumnes presenten públicament els seus problemes sobre aquest tema (P:4h).
    • Aprenentatge dirigit: Repàs dels temes per preparar l'examen parcial.
    Objectius: 1 3
    Continguts:
    Teoria
    2h
    Problemes
    1h
    Laboratori
    2h
    Aprenentatge dirigit
    1.5h
    Aprenentatge autònom
    3h

    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

    La principal característica de la metodologia docent és l'auto-aprenentatge que es basa en la utilització del material docent per conèixer els fonaments tèorics de l'assignatura així com en la resolució de problemes a la pissarra que consoliden aquests coneixements teòrics. El professor introdueix els fonaments tèorics bàsics de cada tema i soluciona alguns problemes. Els estudiants aprenen la teoria durant el seu temps de treball personal mitjançant l'estudi dels temes indicats pel professor de la bibliografia o dels vídeos i d'altres materials complementaris com apunts, llibres i llistes de problemes resolts, tots ells lliurement accessibles a través de la web.

    Durant les hores de problemes, els estudiants surten a la pissarra a explicar solucions a problemes que se'ls hi han assignat amb anterioritat. El professor intervé per corregir una solució, matitzar un argument, o posar émfasi en aquells aspectes que considera rellevants i que no han quedat del tot clars en l'explicació de l'alumne. També pren nota de cada presentació per tal de tenir-la en compte en l'avaluació de l'assignatura.

    Durant les hores de laboratori, els estudiants miren de resoldre problemes davant de la màquina que són avaluats automàticament. El professor està present per tal d'atendre els dubtes que els alumnes li puguin plantejar. Els estudiants poden aprofitar aquestes classes per preparar els problemes que se'ls hi han assignat amb anterioritat, però també per estudiar el material teòric si no ho han fet abans pel seu compte, i per preguntar dubtes sobre la teoria.

    Mètode d'avaluació

    Aquesta assignatura es pot aprovar per avaluació continua (sense assistir a l'examen final). La nota de l'avaluació contínua s'obté de la nota L corresponent als 2 examens del curs (actes avaluatius que valen entre 0 i 8 punts en total, el primer examen amb un pes del 50% i el segon examen amb un pes del 50%), i la nota P corresponent a l'avaluació de les presentacions a la pissarra dels problemes que s'han assignat als alumnes (entre 0 i 2 punts). La nota de l'avaluació contínua
    C s'obté sumant aquestes dues notes, C=L+P.

    Els estudiants que no vagin a l'examen final tenen com a Nota Final (NF) la nota C de l'avaluació contínua.

    Aquells estudiants que facin l'examen final renuncien a la nota de l'avaluació contínua com a nota final de curs. En tal cas, la nota de l'assignatura s'obté de la nota de l'avaluació contínua C i de la nota F de l'examen final (entre 0 i 10) segons la fórmula:

    NF= max(F, 0.5 F+0.5 C)



    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 llengua comú
    Capacitat de manipular fórmules lògiques
    Coneixements algebraics fonamentals: monoides, grups, tancaments, morfismes.
    Coneixements bàsics de combinatòria
    Capacitat d'utilitzar amb facilitat les propietats d'una àlgebra de Boole
    Coneixement de les estructures de dades bàsiques i d'algorísmia fonamental
    Capacitat d'avaluar la complexitat temporal d'un algorisme