Teoria de la Computació

Esteu aquí

Crèdits
6
Tipus
Obligatòria d'especialitat (Computació)
Requisits
  • Corequisit: PROP
  • Prerequisit: EDA
Departament
CS
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 produïr una argumentació correcta.

Professors

Responsable

  • Maria Del Carme Alvarez Faura ( )

Altres

  • Antoni Lozano Bojados ( )
  • Enrique Romero Merino ( )
  • Jaume Baixeries Juvillà ( )
  • Jose Luis Balcázar Navarro ( )

Hores setmanals

Teoria
0.5
Problemes
1.5
Laboratori
2
Aprenentatge dirigit
0.2
Aprenentatge autònom
6

Competències

Competències Transversals

Raonament

  • G9 - 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 - 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.
    Related competences: 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.
    Related competences: 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.

    Related competences: 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. Expressions regulars.
    Expressions regulars, equivalència amb autòmats i Lema d'Arden, operacions sobre expressions regulars.
  4. 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.
  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
2h
Problemes
2h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

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 "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).
Objectius: 1 2 3
Continguts:
Teoria
0h
Problemes
2h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Primer examen

Un examen de 2h de duració realitzat parcialment devant de l'ordinador i parcialment per escrit, on s'avalúa l'habilitat de descriure llenguatges regulars.
Objectius: 1 2
Setmana: 5
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
7h

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 "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
2h
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

Segon examen.

Un examen de 2h de duració realitzat parcialment devant de l'ordinador i parcialment per escrit, on s'avalúa l'habilitat de descriure llenguatges incontextuals definint gramàtiques incontextuals i autòmats amb pila..
Objectius: 1 2
Setmana: 11
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
7h

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
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
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
1h
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).
Objectius: 1 3
Continguts:
Teoria
0h
Problemes
4h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Tercer examen

Un examen de 2h de duració realitzat parcialment devant de l'ordinador i parcialment per escrit, on s'avalúa l'habilitat de construïr reduccions per a demostrar no decidibilitat i no semi-decidibilitat.
Objectius: 1
Setmana: 14
Tipus: examen de laboratori
Teoria
0h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Examen final.


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

Metodologia docent

La principal característica d'aquesta metodologia docent és la utilització del material docent per a l'auto-aprenentatge de la teoria de l'assignatura. 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 només 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 devant 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 mirar els vídeos amb el seu portàtil, 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), i l'avaluació s'obté de la nota L corresponent als 3 examens del curs (actes avaluatius que valen entre 0 i 8 punts en total i tots ells tenen el mateix pes), 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). Obtindran nota final L+P els estudiants tals que el seu L+P sigui major o igual a 5, no vagin a l'examen final, no hagin obtingut qualificació de 0 en cap dels examens del curs, i en opinió del professor de les classes de problemes hagin defensat de forma suficientment correcta totes les presentacions públiques d'exercicis.

Aquells estudiants que facin l'examen final renuncien a la nota de curs (en cas que haguessin aprovat). En tal cas, la nota de l'assignatura s'obté de les notes L i P abans esmentades, i de la nota F de l'examen final (entre 0 i 10) segons la fórmula:

max(F,0.5F+0.5(L+P))

Els estudiants que no hagin aprovat per curs i que no facin l'examen final obtindran qualificació NP.

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