Estudia > Oferta formativa > Oferta d'assignatures > Detall de l'assignatura
Anar al contingut (clic a Intro)
UdG Home UdG Home
Tancar
Menú

Estudia a la UdG

Dades generals

Curs acadèmic:
2013
Descripció:
Introducció als autòmats i llenguatges, teoria de la computabilitat, i teoria de la complexitat algorísmica en temps.
Crèdits:
9
Idioma principal de les classes:
Anglès
S’utilitza oralment la llengua anglesa en l'assignatura:
Gens (0%)
S’utilitzen documents en llengua anglesa:
Completament (100%)

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:

Altres Competències

  • Llenguatges regulars
  • Llenguatges lliures de context
  • Tesis de Church-Turing
  • Decidibilitat
  • Reducibilitat
  • Complexitat en temps

Continguts

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

Activitats

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

Bibliografia

  • Michael Sipser (2006). Introduction to the Theory of Computation (2 international). Course Technology - CENGAGE Learning.

Avaluació i qualificació

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.

Qualificació

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.

Observacions

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.

Assignatures recomanades

  • 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

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.