Anar al contingut (clic a Intro)
UdG Home UdG Home
UdG 30 anys
Tancar
Menú

Estudia a la UdG

Dades generals

Curs acadèmic:
2008
Descripció:
Màquines seqüencials i autòmats finits. Màquines de Turing. Funcions recursives. Gramàtiques i llenguatges formals.
Crèdits:
9
Idioma principal de les classes:
Català
S’utilitza oralment la llengua anglesa en l'assignatura:
Gens (0%)
S’utilitzen documents en llengua anglesa:
Poc (25%)

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:
ESTEBAN FERMIN DEL ACEBO PEÑA  / JAUME RIGAU VILALTA

Altres Competències

  • Assolir un coneixement sòlid dels conceptes bàsics de la informàtica teòrica. Des d'aquest punt de vista, l'assignatura és fonamental per qualsevol persona que vulgui continua estudis relacionats amb la informàtica.

Continguts

1. Llenguatges

          1.1. Conceptes fonamentals.

          1.2. Llenguatges formals. Operacions amb llenguatges.

          1.3. Exemples i problemes.

2. Gramàtiques

          2.1. Introducció.

          2.2. Gramàtiques de Chomsky.

          2.3. Gramàtiques lliures de context. (GLC) i Llenguatges lliures de context(LLC)

                    2.3.1. Arbres de derivació d’una GLC. Existència de LLCs inherentment ambigus.

                    2.3.2. Algorisme de simplificació de gramàtiques lliures de context.

                    2.3.3. Formes normals de les GLC. Forma normal de Chomsky i Forma normal de Greibach d’una GLC.

          2.4. Gramàtiques regulars, llenguatges regulars i expressions regulars.

          2.5. Exemples i problemes

3. Autòmats.

          3.1. Autòmats finits deterministes. (AFD)

                    3.1.1. Formalització.

                    3.1.2. Exemples. autòmats unitaris, autòmats retardadors, autòmats sumadors i restadors binaris.

          3.2. Autòmats com a reconeixedors.

          3.3. Autòmats finits no deterministes (AFND). Equivalència entre AFD i AFND. Problema de trobar un AFD equivalent a un AFND donat.

          3.4. AFND amb emoviments (eAFND). Equivalència entre AFND i eAFND. Problema de trobar un AFD equivalent a un AFND donat.

          3.5. Simplificació d'autòmats.

          3.6. Autòmats reconeixedors i expressions regulars. Teorema de Kleene.

          3.7. Obtenció de l’expressió regular que representa el llenguatge acceptat per un autòmat.

          3.8. Quan un llenguatge Žs regular i quan no ho es. Lema de bombejament per a llenguatges regulars. Exemples.

          3.9. Exemples i exercicis.

          3.10. Autòmats amb pila.(AP)

                    3.10.1. Definició i formalització.

                    3.10.2. Autòmats amb pila com a reconeixedors de llenguatges.

                    3.10.3. Autòmats amb pila deterministes i no deterministes.

                    3.10.4. Equivalència entre autòmats amb pila i llenguatges lliures de context.

                    3.10.5. Els autòmats amb pila com analitzadors sintàctics. Analitzadors LL(k) i LR(k).

                    3.10.6. Exemples i exercicis.

4. Models abstractes de càlcul

          4.1. Preliminar

                    4.1.1. Llenguatges formals.

                    4.1.2. Jerarquia de Chomsky.

                    4.1.3. Enumerabilitat.

          4.2. Calculabilitat I: Màquines de Turing

                    4.2.1. Model bàsic.

                    4.2.2. Disseny.

                    4.2.3. Models equivalents.

                    4.2.4. MT Universal

                    4.2.5. Llenguatges estructurats per frase.

                    4.2.6. Hipòtesi de Church.

          4.3. Calculabilitat II: Models de Càlcul equivalents

                    4.3.1. Funcions Recursives.

                    4.3.2. Màquines RAMs.

                    4.3.3. Llenguatges de Programació Elemental.

                    4.3.4. Conclusions.

          4.4. Indecidibilitat

                    4.4.1. Indecidibilitat en llenguatges.

                    4.4.2. Reduccions.

                    4.4.3. Teorema de Rice.

                    4.4.4. Indecidibilitat en llenguatges incontextuals.

          4.5. Complexitat

                    4.5.1. Les classes P i NP.

                    4.5.2. La classe NP-Complet.

                    4.5.3. La classe co-NP.

Activitats

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

Bibliografia

  • 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.
  • Maria Serna, Carme Alvarez, Rafel Cases, Antoni Lozano (2004). Els límits de la computació. Indecidibilitat i NP-Completesa. Edicions UPC.

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Teoria . Classes expositives segons el temari de l'assignatura. Veure detalls a Guia Docent Assignatura.
Resolucio d'exercicis i problemes. Veure detalls a Guia Docent Assignatura.
Pràctiques : Pràctica 1 Demostracions per inducció. El principi de Dirichlet
Pràctiques: Pràctica 2. L-Systems.
Pràctiques: Pràctica 3. Compressió d'imatges mitjançant expressions regulars.
Proves finals. Veure apartat avaluacio i guia docent.

Qualificació

La nota final de l'assignatura es calcularà com la mitjana de les notes obtingudes en les dues parts de l'assignartura, sempre tenint en compte que és necessari obtenir al menys un 4 de cadascuna de les parts.
Les notes de cadascuna de les parts es calcularan a partir de la notes de l'examen de teoria (75%) i de pràctiques/exercicis (25%), sempre i quan la nota de teoria sigui igual o superior a 4 i s'hagin entregat i aprovat totes les pràctiques/exercicis.

Observacions

L'assignatura consta de dues parts. La primera, impartida pel professor Esteve del Acebo, fins a Fires i la segona, impartida pel professor Jaume Rigau.

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.