1. Maquines de Turing 2. Variants de Màquines de Turing 3. Definició d'algorisme 4. Llenguatges decidibles 5. El problema de l'aturada 6. Problemes indecidibles 7. Un simple problema indecidible 8. Reducibilitat 9. Mesura de complexitat 10. La classe P 11. La classe NP 12. NP-completessa 13. Problemes NP-complets
Tipus d’activitat Hores amb professor Hores sense professor Total Anàlisi / estudi de casos 0 30,00 30,00 Aprenentatge basat en problemes (PBL) 0 40,00 40,00 Prova d'avaluació 5,00 0 5,00 Sessió expositiva 25,00 0 25,00 Sessió pràctica 20,00 0 20,00 Total 50,00 70,00 120
JG Brookshear (1993). Teroia de la computacion. Addison-Wesley. JE Hopcroft, R Motwani, JD Ullman (2001). Introduccion a la Teoria de Automatas, lenguajes, y computacion. Addison-Wesley. Michael Sipser (2006). Introduction to the Theory of Computation (2 international). Course Technology - CENGAGE Learning.
Activitats d'avaluació: Descripció de l'activitat Avaluació de l'activitat % Resolucio de problemes. Classes de teoria. Classes practiques. Treball en equip de problemes. Proves personals finals.
Docència (mig quadrimestre: de Fires de Girona a Nadal) Classes de teoria: 4 hores setmanals Problemes/Pràctiques: 2 hora setmanals L’avaluació de l’assignatura es realitzarà en base a 3 aspectes: A). Un examen teòric. Es valorarà de 0..10 i representa un 50% de la nota final. B) Participació a classe, assistència, i actitut. Els alumnes desenvoluparan (individualment o compartit amb un altre alumne) els temes que es programaran previament. Es valorarà de 0..10 i representa un 25% de la nota final. C) Treball pràctic (individual o compartit amb un altre alumne) a lliurar en un termini preestablert (pot constar d'un o diversos exercicis). Es valorarà de 0..10 i representa un 25% de la nota final. Els apartats A i C fan referencia a cada convocatòria però el B només té valoració durant el desenvolupament de la materia. Qui no pogui assistir a les classes haurà de posar-se doncs en contacte amb el professor per un treball alternatiu a la puntuació corresponent al apartat B. Per fer la mitjana ponderada cal un mínim de 4 de l'apartat A. Altrament, la nota és la mitjana que pertoqui amb un màxim possible de 4.5. En la convocatòria extraordinària, es manté la qualificació de les parts B i C obtinguda per l’alumne en la convocatòria ordinària, per la qual cosa només haurà de realitzar l’examen teòric A. En el cas que no hagi entregat el treball pràctic C, també ho podrà fer en segona convocatòria. Criteris específics de la nota «No Presentat»:Es considerarà No Presentat si l'alumne no porta a terme l'exàmen de la part teòrica A o bé no presenta el treball pràctic C.
Enguany es seguirà el llibre de text de la bibiografia de Michael Sipser: 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. Tota la part 1 està dedicada a autòmats i pot ser utilitzat de suport a materies d'autòmats com per exemple LGA.