Curs 2015-16

Sistemes Formals

Titulació: Codi: Tipus:
Grau en Enginyeria Informàtica 21424 Obligatòria 3r curs
Grau en Enginyeria Telemàtica 22607 Optativa
Grau en Enginyeria en Sistemes Audiovisuals 22673 Optativa

 

Crèdits ECTS: 4 Dedicació: 100 hores Trimestre: 1r

 

Departament: Dept. de Tecnologies de la Informació i les Comunicacions
Coordinador: Víctor Dalmau
Professorat:

Victor Dalmau

Idioma:

Català

Horari:
Campus: Campus de la Comunicació - Poblenou

 

Presentació de l'assignatura

En aquesta assignatura s'introdueixen i estudien els principals models de computació. El curs s'estructura en dos blocs.

En el primer bloc s'estudia les expressions regulars i les gramàtiques lliures de context. L'objectiu és proporcionar a l'estudiant els fonaments matemàtics de la tecnologia utilitzada en el disseny de compiladors i altres processadors de llenguatge. Els conceptes vistos en aquest bloc també s'apliquen en el camp de la verificació de sistemes. 

En el segon bloc s'estudia la Màquina de Turing. La Màquina de Turing és un model matemàtic que té la mateixa "potència" que un ordinador. En aquest bloc primer, s'investigarà quines tasques poden o no poden ser resoltes per una Màquina de Turing. Aquesta part del curs es coneix com Teoria de la decibilitat. Es veuran resultats sorprenents com és el fet de que es pot demostrar que hi ha tasques que no poden ser resoltes per cap programa informàtic. Segonament, es presentarà la teoria de la complexitat on s'investiga quines tasques poden ser resoltes per una Màquina de Turing (o equivalentment per un ordinador) de manera eficient. En particular és presentarà la qüestió coneguda com P=?NP, considerada com una de les 10 preguntes matemàtiques obertes més importants en l'actualitat (de fet, el "Clay Institute" concedeix un premi de un milió de dòlars a qui la solucioni).

En aquesta assignatura es pretén treballar la capacitat de raonament de l'estudiant, potenciant la seva capacitat d'abstracció. L'assignatura té un enfocament teòric i deductiu. 

 

Prerequisits

Els coneixements previs per al seguiment de l'assignatura son certes nocions matemàtiques bàsiques que l'estudiant hauria d'haver adquirit durant l'Ensenyament Secundari Obligatori i les assignatures de matemàtiques del primer curs dels estudis:

- Nocions algebraiques bàsiques.

- Aritmètica bàsica.

- Capacitat bàsica per a comprendre i escriure expressions matemàtiques a nivell elemental.

- Familiaritat amb les tècniques bàsiques de demostració: inducció, reducció a l'absurd.

- Nocions bàsiques de teoria de grafs

Els estudiants que, degut a que provenen del itinerari humanístic del Batxillerat o a que no han superat amb èxit les assignatures de matemàtiques del primer curs del estudis, no estan del tot familiaritzats amb els prerequisits matemàtics podran superar sense problemes l'assignatura però hauran de dedicar-hi un major esforç que la resta de companys, atès que hauran de reforçar aquests coneixements bàsics.

També son convenients algunes nocions bàsiques sobre algorísmica i sobre lògica que l'estudiant hauria d'haver adquirit al cursar les assignatures "fonaments de programació" i "lògica computacional" respectivament. Amb tot i això, els estudiants que, al no haver cursat aquestes assignatures, no estiguin familiaritzats amb aquests conceptes, també podran superar sense problemes l'assignatura, dedicant-hi una mica més d'esforç.

 

Competències

Competències transversalsCompetències específiques

Instrumentals
G1. Capacidad de análisis y
síntesis 

G2. Capacidad de organización
y planificación

G3. Capacidad para aplicar los
conocimientos al análisis de
situaciones y la resolución de
problemas

G4. Habilidad en la búsqueda y
la gestión de la información

G5. Habilidad en la toma de decisiones

G6. Capacidad de comunicarse
con propiedad de forma oral y
escrita en catalán y en 
castellano, tanto ante audiencias
expertas como inexpertas

Interpersonals

G8. Capacidad de trabajo en equipo

Sistèmiques

G11. Capacidad de aplicar
flexibilidad y creatividad los
conocimientos adquiridos y de
adaptarlos a contextos y
situaciones nuevas

G12. Capacidad para progresar
en los procesos de formación y
aprendizaje de manera
autónoma y continua

G14. Capacidad de motivación
por la calidad y por el logro

G15. Capacidad de generación
de nuevas ideas

H1. Capacidad de concebir y llevar a
cabo proyectos informáticos
metodologías propios de la
ingeniería.

H3. Capacidad para la redacción y
desarrollo de proyectos en el ámbito
de su especialidad.

H4. Aprender de manera autónoma
nuevos conocimientos y técnicas
adecuados para la concepción, el
desarrollo o la explotación de
sistemas informáticos.

IN25. Conocer la teoría y práctica de
autómatas de estados finitos,
propiedades de las expresiones y
lenguajes regulares, así como
técnicas para determinar si un
lenguaje es regular o no.

IN26. Conocer los lenguajes libres de
contexto y su relación con los
autómatas con pila, gramáticas libres
de contexto, árboles sintácticos,
derivaciones y ambigüedad.

IN27. Conocer la máquina de Turing
y la relación con la noción de 
algoritmo o programa.

 

 

Avaluació

Els mecanismes d'avaluació són els següents:

1.- Avaluació continua. Aquí s'inclou tant la participació a classe com el resultat dels lliuraments o altres activitats avaluades. El resultat serà una nota, C, entre 0 i 10.

 2.- Examen parcial. Consistirà en un examen obligatori amb preguntes de teoria i problemes sobre les unitats 1 i 2 de l'assignatura que es farà al mig del trimestre. El resultat serà una nota, B1 entre 0 i 10.

3.- Examen final (Desembre). Consistirà en un examen obligatori amb preguntes de teoria i problemes sobre les unitats 3 i 4 de l'assignatura (encara que també hi pot sortir, encara que en menor quantitat, preguntes sobre altres unitats) que es realitzarà durant el període d'exàmens del primer trimestre. El resultat de l'examen final de desembre serà una nota, B2 entre 0 i 10. També es realitzarà un examen opcional que permet avaluar novament les unitats 1 i 2 del parcial. S'actualitzarà la nota B1 si la nota obtinguda és millor.

4.- Examen final (Juliol). Consistirà en dos examens independents i opcionals (un per a les unitats 1 i 2 i l'altre per les unitats 3 i 4). Les notes B1 i B2 s'actualitzaran si la nota obtinguda es millor.

 

Els estudiants poden escollir el tipus d'avaluació.

A) Avaluació contínua.

Per a aprovar una convocatòria cal que les notes B1 i B2 siguin, com a mínim 4. En aquest cas la nota serà 0.30*C+0.30*B1+0.4*B2

B) Avaluació no contínua.

Per a aprovar una convocatòria cal que les notes B1 i B2 siguin, com a mínim 4. En aquest cas la nota serà (0.30*B1+0.4*B2)/0.70

 

 

Continguts

L'assignatura es divideix en quatre unitats didàctiques.

1.- Llenguatges regulars.

Autòmats finits deterministes (AFD) i no deterministes. . Expressions regulars. Equivalència entre AFDs i expressions regulars (Teorema de Kleene). Llenguatges regulars i les seves propietats bàsiques.

2.- Llenguatges lliures de context.

 Gramàtiques lliures de context (GLC). Llenguatges lliures de context i les seves propietats bàsiques.

3.- Teoria de la decidibilitat.

Màquines de Turing (TM). Equivalència entre MTs i programes. Llenguatges recursivament enumerables i recursius. Llenguatge Diagonal, universal, de la parada.

4.- Teoria de la complexitat

Complexitat temporal de una MT. Les classes P i NP. Reducció en temps polinòmica. NP-completesa i teorema de Cook.

 

Metodologia

 

 

-Treball personal de l'estudiant abans de cada sessió.

Abans de cada sessió, l'estudiant prepararà un material que serà proporcionat anteriorment pel professor. El material pot contenir exercicis que l'estudiant haurà de resoldre com part de la preparació. 

-Treball durant la sessió. 

Durant la sessió, els estudiants treballaran en grups els exercicis i sortiran a la pissarra a solucionar-los.

En adició a lo anterior el professor pot demanar altres tasques com, per exemple, el lliurament d'exercicis o la presentació d'alguna part del material. 

Taula de dedicació:

 Activitats a l'aulaActivitats fora de l'aulaAvaluació
TemesGrup granGrup mitjàGrup petit  

 Bloc 1

20

 

 

30

 

 Bloc 2

 20

 

 

30

 

Total:

 40

 

 

 60

 

Total:100

 

Recursos

Recursos didàctics. Material docent de l'assignatura

- Material proporcionat pel professor. Suport electrònic. Accessible a l'espai Moddle dedicat a l'assignatura. 

Bibliografia bàsica

-J. Hopcroft, R. Motwani i J. Ullman. Introducción a la teoria de automatas, lenguajes y computación. Addison-Wesley, 2007.

- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Bibliografia complementària

- D. Kelley. Teoría de autómatas y lenguajes formales. Prentice-Hall, 1995.

- D. Kozen. Automata and Computability. Springer-Verlag, 1997.

- H. Lewis i C. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1997.