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 18 32
Aprenentatge basat en problemes (PBL) 28 38 66
Classes expositives 42 52 94
Prova d'avaluació 4 12 16
Tutories 2 0 2
Total 90 120 210

Bibliografia

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

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