Estudia a la UdG

Disseny assignatura




Teoria d'autòmats i llenguatge formal (3105IS0017/2008)


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%)

Torna a l'inici / Vuelve al principio / Back to top

  Grups
Grup A

Durada : Semestral, 1r semestre

Professorat : ESTEBAN FERMIN DEL ACEBO PEÑAJAUME RIGAU VILALTA

Horaris :

Activitat Horari Grup de classe Aula
Teoria1
Pràctiques d'aula informàtica1
Pràctiques d'aula informàtica2
Pràctiques d'aula informàtica3

Torna a l'inici / Vuelve al principio / Back to top

  Competències

    Altres competències :

    1. 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.

    Torna a l'inici / Vuelve al principio / Back to top

      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 casos141832
    Aprenentatge basat en problemes (PBL)283866
    Classes expositives425294
    Prova d'avaluació41216
    Tutories202
    Total 90120210

    Torna a l'inici / Vuelve al principio / Back to top

      Bibliografia
    • Joaquim Gabarro (1995). Informàtica clàssica : autòmats i gramàtiques, indecidibilitat,.... Vic: Eumo. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
    • John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to automata theory, languages, and computation. Reading, MA, USA: Addison-Wesley. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
    • J. Glenn Brookshear (1993). Teoría de la computación : lenguajes formales, autómatas y complejidad. Addison-Wesley Iberoamericana. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova
    • Maria Serna, Carme Alvarez, Rafel Cases, Antoni Lozano (2004). Els límits de la computació. Indecidibilitat i NP-Completesa. Edicions UPC. Catàleg   Enllaç al catàleg de la Biblioteca. S'obre en finestra nova

    Torna a l'inici / Vuelve al principio / Back to top

      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.

    Torna a l'inici / Vuelve al principio / Back to top

      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.

    Torna a l'inici / Vuelve al principio / Back to top

      Assignatures recomanades
    1. Computadors
    2. Estructura i tecnologia de computadors
    3. Introducció a la lògica
    4. Introducció a les estructures de dades
    5. Matemàtica discreta
    6. Matemàtiques
    7. Matemàtiques bàsiques

    Torna a l'inici / Vuelve al principio / Back to top