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 0 32,00 32,00 Aprenentatge basat en problemes (PBL) 0 66,00 66,00 Prova d'avaluació 4,00 12,00 16,00 Sessió expositiva 0 94,00 94,00 Tutories de grup 2,00 0 2,00 Total 6,00 204,00 210
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.
Engunay no s'imparetix docència d'aquesta assignatura (pertany al pla àntic). L’avaluació de l’assignatura es realitzarà en base a un examen (dues convocatòries) a partir dels apartats que consten a la secció de Continguts (veure Competències/Continguts/Activitats) del llibre base de text (veure bibliografia) on es troba tota la teoria, exemples, i exercicis objecte de l'assignatura i en que es basarà l'exàmen; Capítols del 0 al 7 excepte el 6. Criteris específics de la nota «No Presentat»:Es considerarà No Presentat si l'alumne no es presenta a l'exàmen preestablert per l'EPS.
No s'imparteix docència (pla antic). Tot el contingut de l'assignatura i material necessari per superar els exàmens es troba al llibre de text de la bibiografia de Michael Sipser. Només cal llegir els capítols corresponents al contingut de l'assignatura: Capítols del 0 al 7 excepte el 6.
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