|
Objectius
|
|
|
|
Assolir un coneixement sòlid dels conceptes més importants de la informàtica teòrica. Des d'aquest punt de vista, l'assignatura és fonamental per qualsevol persona que es vulgui dedicar seriosament a la informàtica. |
|
|
|
|
Prerrequisits
|
|
|
|
Recomanables: Introducció a la lògica i materies troncals de programació. |
|
|
|
|
Contingut (Programa)
|
|
|
|
PART 1: LLENGUATGES, GRAMÀTIQUES I AUTÒMATS
1.- Llenguatges
1.1. Introducció.
1.2. Conceptes fonamentals.
1.2.1 Alfabets i cadenes.
1.2.2 Llenguatge universal generat per un alfabet.1.3. Relacions de Thue. Càlculs associatius.
1.4. Llenguatges formals. Operacions amb llenguatges.
1.5. Exemples i problemes.2.- Gramàtiques
2.1. Introducció.
2.2. Sistemes formals.
2.2.1 Sistemes combinatoris.
2.2.2 Lleis de generació
2.2.3 Exemple. Formalització del càlcul algebraic.2.3 gramàtiques de Chomsky.
2.3.1 Introducció.
2.3.2 Concepte formal de gramàtica de Chomsky.
2.3.3 Gramàtiques no restringides o de tipus 0. Exemples.
2.3.4 Gramàtiques contextuals o de tipus 1. Exemples.
2.3.5 Gramàtiques lliures de context o de tipus 2.
2.3.5.1 Gramàtiques lliures de context. (GLC) i Llenguatges lliures de context(LLC)
2.3.5.2 Formes normals de les GLC. Forma normal de Chomsky i Forma normal de Greibach d’una GLC.
2.3.5.3 Algorisme de simplificació de gramàtiques lliures de context.
2.3.5.4 Arbres de derivació d’una GLC. Existència de LLCs inherentment ambigus.
2.3.5.5 Exemples.2.3.6 Gramàtiques regulars o de tipus 3.
2.3.6.1 Gramàtiques regulars i Llenguatges regulars.
2.3.6.2 Expressions regulars. Obtenció de l’expressió regular que representa el llenguatge generat per una gramàtica regular.2.4 Exemples i exercicis.
2.4.1 Us de GLC per especificació de sintaxi de llenguatges de programació. Notació de BackusNaur.
2.4.2 Us de GLC pel disseny d’interfícies de llenguatge natural. gramàtiques lògiques.
2.4.3 Utilització de les gramàtiques als gràfics per ordinador. Compressió d’imatges mitjançant gramàtiques regulars. LSystems.3.- Autòmats.
3.1 Autòmats finits deterministes. (AFD)
3.1.1 Introducció. Relacions de l’automat amb l’entorn
3.1.2 Formalització. autòmats finits deterministes.
3.1.3 Autòmats de Moore i de Mealy. Taules de transició.
3.1.4 Exemples. autòmats unitaris, autòmats retardadors, autòmats sumadors i restadors binaris.3.2 Autòmats com a reconeixedors.
3.2.1 Introducció
3.2.2 Formalització. Acceptació d’una paraula per un autòmat. Llenguatge acceptat per un autòmat.
3.2.3 autòmats finits no deterministes (AFND). Equivalència entre AFD i AFND. Problema de trobar un AFD equivalent a un AFND donat.
3.2.4 AFND amb emoviments (eAFND). Equivalència entre AFND i eAFND. Problema de trobar un AFD equivalent a un AFND donat.
3.2.5 Autòmats reconeixedors i expressions regulars. Teorema de Kleene.
3.2.6 Obtenció de l’expressió regular que representa el llenguatge acceptat per un autòmat.
3.2.7 Quan un llenguatge Žs regular i quan no ho es. Lema de bombejament per a llenguatges regulars. Exemples.
3.2.8 Exemple. Una màquina expenedora és un autòmat reconeixedor.3.3 Autòmats amb pila.(AP)
3.3.1 Definició i formalització.Exemples.
3.3.2 Autòmats amb pila com reconeixedors de llenguatges. Acceptació d’una paraula per pila buida i per estat final. Exemples.
3.3.3 AP deterministes i no deterministes. Exemples.
3.3.4 Equivalència entre autòmats amb pila i llenguatges lliures de context.
3.3.5 Lema de bombejament per llenguatges lliures de context. Exemples i problemes.
3.2.6 Els autòmats amb pila com analitzadors sintàctics. Introducció. Analitzadors LL(k) i LR(k). Exemples i exercicis.
PART II - MODELS ABSTRACTES DE CÀLCUL
0.- Preliminar
0.1.- Llenguatges formals.
0.2.- Jerarquia de Chomsky.
0.3.- Enumerabilitat.1.- Calculabilitat I: Màquines de Turing
1.1.- Model bàsic.
1.2.- Disseny.
1.3.- Models equivalents.
1.4.- MT Universal
1.5.- Llenguatges estructurats per frase.
1.6.- Hipòtesi de Church.2.- Calculabilitat II: Models de Càlcul equivalents
2.1.- Funcions Recursives.
2.2.- Màquines RAMs.
2.3.- Llenguatges de Programació Elemental.
2.4.- Conclusions.3.- Indecidibilitat
3.1.- Indecidibilitat en llenguatges.
3.2.- Reduccions.
3.3.- Teorema de Rice.
3.4.- Indecidibilitat en llenguatges incontextuals.4.- Complexitat
4.1.- Les classes P i NP.
4.2.- La classe NP-Complet.
4.3.- La classe co-NP.
|
|
|
|
|
Bibliografia
|
|
|
|
|
- JOHN E HOPCROFT, J.D. ULLMAN: Introduction to automata theory, languages and computation, Addison-Wesley, (1979)
- GLENN BROOKSHEAR, J.: Teoria de la computación: Lenguajes formales, autómatas y complejidad Addison-Wesley Iberoamericana, (1993)
- GABARRÓ, J.: Informàtica classica: autòmats i gramàtiques Vic - Eumo (1995)
| |
|
|
|
|
Mètodes docents
|
|
|
|
Classes de teoria i problemes
. hores setmanals 4
Pràctiques
. hores setmanals 2
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. |
|
|
|
|
Tipus d'exàmens i avaluacions
|
|
|
|
La nota final 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,5 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 (25%) de la part corresponent, sempre i quan la nota de teoria sigui igual o superior a 4,5 i s'hagin entregat i aprovat totes les pràctiques. |
|
|
|
|
Informació addicional
|
|
|
|
Es faran pràctiques curtes relacionades amb l'aplicació dels conceptes explicats a classe dins la industria i la informàtica: L-Systems, compressió d'imatges, Gramàtiques lògiques, models de càlcul, etc. |
|
|
|
|
|
La bibliografia a la biblioteca