Teoria de la Computació

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Teoria de la Computació
Crèdits
6
Tipus
Obligatòria d'especialitat (Computació)
Requisits
  • Prerequisit: EDA
  • Corequisit: PROP
Departament
CS
Web
www.cs.upc.edu/~alvarez/tc2.html
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

  • Maria del Carme Alvarez Faura ( )

Altres

  • Enrique Romero Merino ( )
  • Ilario Bonacina ( )

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 la jerarquia de Chomsky. En particular, aprendre tècniques que permeten determinar quan un conjunt és regular, incontextual, decidible i semi-decidible.
    Competències relacionades: G9.3, CCO1.2, CCO1.1,
  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.2, CCO1.1, 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.2, CCO1.1, 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.
  10. 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.

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
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

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
2h
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
2h
Problemes
1h
Laboratori
0h
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
2h
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 "Problemes naturals indecidibles".

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
0h
Problemes
1h
Laboratori
4h
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)
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Examen final.


Objectius: 1 2
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen de teoria
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

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 durant la classe de teoria 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 si aquesta és més gran o igual a 5. Si no van a l'examen final però la nota C és més petita que 5, aleshores obtindran qualificació NP.

Aquells estudiants que facin l'examen final renuncien a la nota de l'avaluació contínua com a nota final de curs (en cas que haguessin aprovat). 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àsica:

Complementaria:

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