Llenguatges regulars Llenguatges lliures de context Tesis de Church-Turing Decidibilitat Reducibilitat Complexitat en temps
1. Autòmats finits 2. Indeterminisme 3. Expressions regulars 4. llenguatges no-regulars 5. Gramàtiques lliures de context 6. Autòmats de pila 7. Llenguatges no-lliures de context 8. Màquines de Turing 9. Variants de Màquines de Turing 10. Definició d'algorisme 11. Llenguatges decidibles 12. El problema de l'aturada 13. Problemes indecidibles 14. Un problema indecidible 15. Reducibilitat 16. Mesura de complexitat de temps 17. La classe P 18. La classe NP 19. NP-completessa 20. Problemes NP-complets
Tipus d’activitat Hores amb professor Hores sense professor Total Anàlisi / estudi de casos 14,00 18,00 32,00 Aprenentatge basat en problemes (PBL) 28,00 38,00 66,00 Prova d'avaluació 4,00 12,00 16,00 Sessió expositiva 42,00 52,00 94,00 Tutories de grup 2,00 0 2,00 Total 90,00 120,00 210
Joaquim Gabarro (1995). Informàtica clàssica : autòmats i gramàtiques, indecidibilitat,.... Vic: Eumo. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to automata theory, languages, and computation. Reading, MA, USA: Addison-Wesley. J. Glenn Brookshear (1993). Teoría de la computación : lenguajes formales, autómatas y complejidad. Addison-Wesley Iberoamericana. 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 % Teoria . Classes expositives segons el temari de l'assignatura. Resolucio d'exercicis i problemes. Pràctiques Proves finals.
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. B) Participació a classe, assistència, i actitut. Els alumnes desenvoluparan (individualment o compartit amb un altre alumne) els temes que es programaran previament. C) Treball pràctic (individual o compartit amb un altre alumne) a lliurar en un termini preestablert (pot constar d'un o diversos exercicis). El contingut s'impartirà en dos blocs: Bloc I: Temes 1-7 (fins a Fires de Girona) Bloc II: temes 8-20 (fins a Nadal) La nota final és la mitjana dels dos blocs. Pel Bloc 1: Es comptabilitzen l'apartat A i C. Cadascun amb un pes del 50%. Pel Bloc 2: Es comptabilitza A al 50%, B al 25%, i C també al 25%. 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. Comú a cada bloc: 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 (bloc II) 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, en qualsevol dels dos blocs, no porta a terme l'exàmen de la part teòrica A o bé no presenta el treball pràctic C.
L'assignatura consta de dos blocs. El primer, impartit pel professor Esteve del Acebo, fins a Fires i lel segon, impartit pel professor Jaume Rigau, fins Nadal. Pel desenvolupament del Bloc II, 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 útils pels dos Blocs. Tota la part 1 està dedicada a autòmats i pot ser utilitzat de suport a al Bloc I on es segueixen els apunts del professor.
Computadors Estructura i tecnologia de computadors Introducció a la lògica Introducció a les estructures de dades Matemàtica discreta Matemàtiques Matemàtiques bàsiques