Curs 2014-15
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 |
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.
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 transversals | Competències específiques |
|---|---|
|
Instrumentals G2. Capacidad de organización G3. Capacidad para aplicar los G4. Habilidad en la búsqueda y G5. Habilidad en la toma de decisiones G6. Capacidad de comunicarse Interpersonals G8. Capacidad de trabajo en equipo Sistèmiques G11. Capacidad de aplicar G12. Capacidad para progresar G14. Capacidad de motivación G15. Capacidad de generación |
H1. Capacidad de concebir y llevar a H3. Capacidad para la redacción y H4. Aprender de manera autónoma IN26. Conocer los lenguajes libres de IN27. Conocer la máquina de Turing
|
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 en primera convocatòria 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
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.
-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'aula | Activitats fora de l'aula | Avaluació | ||||
|---|---|---|---|---|---|---|
| Temes | Grup gran | Grup mitjà | Grup petit | |||
|
Bloc 1 |
20 |
|
|
30 |
|
|
|
Bloc 2 |
20 |
|
|
30 |
|
|
|
Total: |
40 |
|
|
60 |
|
Total:100 |
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.