Estudia

• CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
• CT05 Recollir i seleccionar informació de forma eficaç
• CT06 Disenyar propostes creatives
• CC1 Capacitat per a tenir un coneixement profund dels principis fonamentals i models de la computació i saber-los aplicar per a intentar, seleccionar, valorar, modelar, i crear nous conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica.
• CC3 Capacitat per avaluar la complexitat computacional d'un problema, conèixer estratègies algorítmiques que poguin conduir a la seva resolució i recomenar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.

1. Introducció

          1.1. Autòmats, computabilitat, i complexitat

          1.2. Notació matemàtica i terminologia

          1.3. Definicions, teoremes, i demostracions

          1.4. Tipus de demostracions

2. Llenguatges regulars

          2.1. Autòmats finits

          2.2. Indeterminisme

          2.3. Expressions regulars

          2.4. Llenguatges no regulars

3. Llenguatges lliures de context

          3.1. Gramàtiques lliures de context

          3.2. Autòmats amb pila

4. Tesi de Church-Turing

          4.1. Màquines de Turing

          4.2. Variants de màquines de Turing

          4.3. Definició d'algorisme

5. Decidibilitat

          5.1. Llenguatges decidibles

          5.2. Indecidibilitat

6. Reduïbilitat

          6.1. Problemes indecidibles

          6.2. Un problema indecidible simple

          6.3. Funcions de reducció

7. Complexitat en temps

          7.1. Mesures de complexitat

          7.2. La classe P

          7.3. La classe NP

          7.4. NP-completesa

          7.5. Alguns problemes NP-complets

• Michael Sipser (2012). Introduction to the Theory of Computation (3). CENGAGE learning. Recuperat , a https://omnia.udg.edu/view/action/uresolver.do?operation=resolveService&package_service_id=2193049210006713&institutionId=6713&customerId=6705&VE=true Catàleg
• Sipser, Michael (2006). Introduction to the theory of computation (2nd ed., international ed.). Boston: Course Technology/Cengage Learning. Catàleg
• Sesa Nogueras, Enric (2000). Teoria d'autòmats i llenguatges formals I. Barcelona: Universitat Oberta de Catalunya. Catàleg
• Joan Vancells, Miquel Bofill (2000). Teoria D'autòmats I Llenguatges Formals II. UOC. Catàleg
• Casas, Rafel (2003). Llenguatges, gramàtiques i autòmats (2a ed.). Barcelona: Edicions UPC, a http://biblioapps.udg.edu/biblioteca-digital/llibresdigitalsUPC/llibre.php?codi=IN010XXX Catàleg
• Serna, Maria José (2001). Els Límits de la computació. Barcelona: Edicions UPC, a http://biblioapps.udg.edu/biblioteca-digital/llibresdigitalsUPC/llibre.php?codi=IN029XXX Catàleg
• JE Hopcroft, R. Motwani, KD Ullman (2001). Introduccion a la teoria de automatas, lenguajes, y computacion. Addison-Wesley. Catàleg
• Kelley, Dean (1995). Teoría de autómatas y lenguajes formales. Madrid [etc.]: Prentice Hall. Catàleg
• P. Isasi, P. Martinez, D. Borrajo (1997). Lenguajes, gramáticas y autómatas. Un enfoque práctico (1). Madrid: Addison-Wesley Iberoamericana España, S.A.. Catàleg
• JG Brookshear (1979). Teoria de la computacion. Addison-Wesley. Catàleg

Activitats d'avaluació:

Es faran classes expositives de teoria setmanals, i classes de suport a la teoria (repàs, discussions, exemples i exercicis) en grups petits, bisetmanalment.

L'assignatura consta de dos blocs de matèria:

1. Llenguatges, gramàtiques i autòmats
2. Decidibilitat i complexitat

La qualificació de l’assignatura es realitzarà en base als següents elements.

A: resolució d'exercicis a l'aula
PAC_1: prova d'avaluació continuada sobre el bloc 1
PAC_2: prova d'avaluació continuada sobre el bloc 2

La PAC_1 es realitzarà en acabar el temari del bloc 1 (previsiblement a mitjans de novembre).
La PAC_2 es realitzarà a final de curs, en la data prevista per a exàmens finals.

La resolució d'exercicis a l'aula no és recuperable. Les PACs són recuperables. La recuperació d'ambdues PAC tindrà lloc en la data prevista per a recuperacions. En cas de recuperació, s'agafarà la millor nota.

No es requereix nota mínima de cap part.

La nota final (NF) es calcularà de la següent manera (exceptuant el cas d'avaluació única).

NF := max( (A * 0.2 + PAC_1 * 0.4 + PAC_2 * 0.4) , (PAC_1 * 0.5 + PAC_2 * 0.5) )

Noti's que el càlcul via la funció 'max' implica no perjudicar ningú per la no realització d'exercicis a l'aula.

Es recomana donar un cop d'ull a l'apartat 'Observacions i Recomanacions'.

Criteris específics de la nota «No Presentat»:
L'alumne obrindrà la nota de 'No Presentat' si no es presenta a cap PAC, o a l'examen final en el cas d'avaluació única.

Avaluació única:
L'avaluació única consisteix d'un examen final amb un valor del 100% de la qualificació.

Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació més gran o igual que 5 de la nota final (NF) calculada com s'ha descrit a l'apartat 'Criteris de qualificació'.

Les tutories es faran de manera presencial sempre que es pugui.

Les comunicacions de l'assignatura es faran per escrit mitjançant el fòrum d'avisos i notícies del Moodle.

La interacció escrita (bidireccional) amb els estudiants es farà preferentment en fòrums del Moodle, reservant el correu electrònic per a qüestions privades. Les consultes que es realitzin per correu electrònic i que siguin d'interès general seran redirigides al fòrum corresponent del Moodle.

a) Tota la documentació necessària estarà disponible al web de l'assignatura en el moment adequat.

b) Lectura recomanada. Del llibre de text de Michael Sipser (veure bibliografia): capítols 1-5 i 7. El capítol 0 és una introducció bàsica per situar-se en el vocabulari i notació de l'assignatura, i també serveix de recordatori de conceptes previs de matemàtiques. L'ús continu del text al llarg del curs facilitarà el treball als estudiants amb assistència discontínua per motius de treball, o altres.

• Estructures de dades i algorítmica
• Lògica i matemàtica discreta