1. Tesis de Church-Turing 1.1. Maquines de Turing 1.2. Variants de Màquines de Turing 1.3. Definició d'algorisme 2. Decidibilitat 2.1. Llenguatges decidibles 2.2. El problema de l'aturada 3. Reducibilitat 3.1. Problemes indecidibles 3.2. Un simple problema indecidible 3.3. Funció de Reducibilitat 4. Complexitat en Temps 4.1. Mesura de complexitat 4.2. La classe P 4.3. La classe NP 4.4. NP-completessa 4.5. Problemes NP-complets
Tipus d’activitat Hores amb professor Hores sense professor Total Prova d'avaluació 4,00 9,00 13,00 Resolució d'exercicis 0 15,00 15,00 Sessió expositiva 25,00 8,00 33,00 Sessió pràctica 20,00 8,00 28,00 Treball en equip 0 15,00 15,00 Tutories de grup 15,00 1,00 16,00 Total 64,00 56,00 120
Michael Sipser (2006). Introduction to the Theory of Computation (2 international). Course Technology - CENGAGE Learning. JE Hopcroft, R Motwani, JD Ullman (2001). Introduccion a la Teoria de Automatas, lenguajes, y computacion. Addison-Wesley. JG Brookshear (1993). Teroia de la computacion. Addison-Wesley.
Activitats d'avaluació: Descripció de l'activitat Avaluació de l'activitat % Resolució de problemes (en equip) Disseny, implementació, participació, compliment termini. 20 Resolució d'exercicis (individual) Disseny, implementació, compliment termini. 20 Prova d'avaluació (teòrica) Solució i demostració de les solucions a un conjunt de questions relacionades amb el temari. 60
Docència (mig quadrimestre: de Fires de Girona a Nadal emprant totes les hores d'horari on consta LGA o MAC) Classes de teoria: 4 hores setmanals Problemes/Pràctiques: 2 hora setmanals (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 sels presentaran en el moment de teoria adecuat i que obligatòriament 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. 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/MAC/ 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 la bibiografia de Michael Sipser. Específicament de la - 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. 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).