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. Llenguatges Regulars

          1.1. Autòmats Finits

          1.2. Indeterminisme

          1.3. Expressions Regulars

          1.4. Llenguatges No-regulars

2. Llenguatges Lliures de Context

          2.1. Gramàtiques Lliures de Context

          2.2. Autòmats de Pila

          2.3. Llenguatges No-lliures de Context

3. Tesis de Church-Turing

          3.1. Maquines de Turing

          3.2. Variants de Màquines de Turing

          3.3. Definició d'algorisme

4. Decidibilitat

          4.1. Llenguatges decidibles

          4.2. El problema de l'aturada

5. Reducibilitat

          5.1. Problemes indecidibles

          5.2. Un simple problema indecidible

          5.3. Funció de Reducibilitat

6. Complexitat en Temps

          6.1. Mesura de complexitat

          6.2. La classe P

          6.3. La classe NP

          6.4. NP-completessa

          6.5. Problemes NP-complets

• Michael Sipser (2006). Introduction to the Theory of Computation (2). Course Technology. CENGAGE Learning. Catàleg
• JE Hopcroft, R. Motwani, KD Ullman (2001). Introduccion a la teoria de automatas, lenguajes, y computacion. Addison-Wesley. Catàleg
• Joan Vancells, Miquel Bofill (2000). Teoria D'autòmats I Llenguatges Formals II. UOC. Catàleg
• JG Brookshear (1979). Teoria de la computacion. Addison-Wesley. 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..

Activitats d'avaluació:

Classes de teoria: 2 hores setmanals
Problemes/Pràctiques: 2 hora bisetmanals (s'imparteixen en els punts adecuats dins del contingut teòric setmanal).
La qualificació de l’assignatura es realitzarà en base a 3 aspectes:
A) Un examen teòric
Es valorarà de 0..10 i representa un 60% de la nota final.
B) Resolució de problemes
Els alumnes desenvoluparan forçosament en grups de 2 o 3 un o dos problemes que es presentaran en el moment de teoria adecuat i que obligatòriament s'hauran d'entregar dins del termini preestablert.
Es valorarà de 0..10 i representa un 20% de la nota final.
C) Resolució d'exercicis
De forma individual, cada estudiant lliurarà dins del termini establert els diversos exercicis que se li vagin presentant al llarg del desenvolupament de la teoria.
Es valorarà de 0..10 i representa un 20% de la nota final.

Per l'apartat A es faran dues convocatòries (ordinaria i extraordinaria) segons el calendari establert.
Els apartats B i C s'han d'entregar obligatòriament dins del termini establert i NO tenen recuperació (cal seguir doncs l'assignatura al llarg de tot el seu desenvolupament). Sempre que es consideri oportú, es podrà citar personalment a un alumne per tal de que demostri el seu coneixement i participació en les solucions entregades. Tanmateix, es recorda als estudiants que segons la tipologia d'exercici, es disposen de programes automàtics de detecció de còpia d'una eficacia demostrada. La còpia comporta un 0 per tots els implicats (bilateralment). La forma d'entrega dels treballs s'indicarà especificament per cadascún d'ells, conjuntament amb el seu enunciat i termini d'entrega.

Per poder promitjar és obligatòri haver entregat COMPLETAMENT cadascún dels tres apartats, inclòs pels alumnes no presencials. Altrament la qualificació seria de no presentat.

Les comunicacions es faran per escrit mitjançant "Avisos" a la Meva-UdG.
Tot el material el podreu trobar a http://ima.udg.edu/~rigau/FC/

Criteris específics de la nota «No Presentat»:
Es considerarà No Presentat si l'estudiant no porta a terme l'exàmen de la part teòrica (A) o bé no presenta TOTS els treballs en equip (B) o be TOTS els treballs individuals (C).

Seguirem el llibre de text de Michael Sipser (veure Bibliografia). Específicament:
- Part 1: capítols 1 i 2.
- Part 2: capítols 3, 4, i 5.
- Part 3: capítol 7.
El capítol 0 d'introducció es bàsic per situarse en el vocabulari, notació, i com a recordatori de conceptes previs de matemàtiques.
L'ús del text al llarg de totes les classes expositives facilitarà el treball als estudiants amb assistència discontinua per motius de treball (o altres).

• Càlcul
• Estructures de dades i algorítmica
• Lògica i matemàtica discreta
• Metodologia i tecnologia de la programació I
• Metodologia i tecnologia de la programació II
• Projecte de programació