| Competències |
| Tipus A | Codi | Competències Específiques |
| CM6 | Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algorismes proposats. | |
| CP1 | Capacitat per tenir un coneixement profund dels principis fonamentals i models de la computació i saber-los aplicar per interpretar, seleccionar, valorar, modelar i crear nous conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica. | |
| CP2 | Capacitat per conèixer els fonaments teòrics dels llenguatges de programació i les tècniques de processament lèxic, sintàctic i semàntic associades, i saber aplicar-les per a la creació, disseny i processament de llenguatges. | |
| CP3 | Capacitat per avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin conduir-ne a la resolució i recomanar, desenvolupar i implementar la que garanteixi el millor rendiment d'acord amb els requisits establerts. | |
| Tipus B | Codi | Competències Transversals |
| CT5 | Comunicar informació de manera clara i precisa a audiències diverses. | |
| Tipus C | Codi | Competències Nuclears |
| Resultats d'aprenentage |
| Tipus A | Codi | Resultats d'aprenentatge |
| CM6 |
Comprèn els conceptes bàsics de calculabilitat i complexitat. | |
| CP1 |
Coneix els principals tipus de llenguatges formals Sap construir expressions regulars, gramàtiques i autòmats per la descripció, generació i reconeixement de llenguatges formals Comprèn els conceptes bàsics de calculabilitat i complexitat Coneix l’estructura bàsica dels processadors de llenguatges Sap utilitzar eines per generar analitzadors lèxics i sintàctics | |
| CP2 |
Coneix els principals tipus de llenguatges formals Sap construir expressions regulars, gramàtiques i autòmats per la descripció, generació i reconeixement de llenguatges formals Coneix l’estructura bàsica dels processadors de llenguatges Sap utilitzar eines per generar analitzadors lèxics i sintàctics | |
| CP3 |
Comprèn els conceptes bàsics de calculabilitat i complexitat. | |
| Tipus B | Codi | Resultats d'aprenentatge |
| CT5 |
Produeix un text de qualitat, sense errors gramaticals i ortogràfics, amb una presentació formal acurada i un ús adequat i coherent de les convencions formals i bibliogràfiques Construeix un text estructurat, clar, cohesionat, ric i d’extensió adequada Elabora un text adequat a la situació comunicativa, consistent i persuasiu | |
| Tipus C | Codi | Resultats d'aprenentatge |
| Continguts |
| Tema | Subtema |
| 1. Introducció | 1.1. Els llenguatges de programació com a llenguatges formals. 1.2. Nocions bàsiques de llenguatges formals: definició, descripció, i reconeixement de llenguatges formals. 1.3. Estructura bàsica d'un compilador. |
| 2. Llenguatges regulars | 2.1. Expressions regulars. 2.2. Autòmats finits: deterministes, no deterministes i amb lambda-moviments. 2.3. Equivalència entre expressions regulars i autòmats finits. 2.4. Generadors d'analitzadors lèxics: flex. |
| 3. Llenguatges independents del context | 3.1. Gramàtiques independents del context. 3.2. Autòmats de pila. 3.3. Equivalència entre gramàtiques independents del context i autòmats de pila. 3.4. Generadors d'analitzadors sintàctics: bison. |
| 4. Altres llenguatges formals | 4.1. Classificació dels llenguatges formals: jerarquia de Chomsky. 4.2. Màquines de Turing. 4.3. Llenguatges recursius i llenguatges recursivament enumerables. |
| 5. Calculabilitat i complexitat | 5.1. Tesi de Church-Turing. 5.2. Màquina de Turing universal. 5.3. Problemes indecidibles: problema de l'aturada. 5.4. Introducció a la teoria de la complexitat. 5.5. Els problemes P, NP i NP-complets. |
| 6. Processadors de llenguatges formals | 6.1. Taula de símbols. 6.2. Anàlisi lèxica. 6.3. Anàlisi sintàctica. 6.4. Anàlisi semàntica. 6.5. Generació de codi intermedi. 6.6. Generació de codi objecte. |
| Planificació |
| Metodologies :: Proves | ||||||||||
| Competències | (*) Hores a classe |
Hores fora de classe |
(**) Hores totals | |||||||
| Activitats Introductòries |
|
1 | 0 | 1 | ||||||
| Sessió Magistral |
|
11 | 24 | 35 | ||||||
| Resolució de problemes, exercicis a l'aula ordinària |
|
13 | 22.5 | 35.5 | ||||||
| Pràctiques a través de TIC en aules informàtiques |
|
30 | 22.5 | 52.5 | ||||||
| Atenció personalitzada |
|
1 | 0 | 1 | ||||||
| Proves mixtes |
|
3 | 6 | 9 | ||||||
| Proves pràctiques |
|
1 | 15 | 16 | ||||||
| (*) En el cas de docència no presencial, són les hores de treball amb suport vitual del professor. (**) Les dades que apareixen a la taula de planificació són de caràcter orientatiu, considerant l’heterogeneïtat de l’alumnat | ||||||||||
| Metodologies |
| Descripció | |
| Activitats Introductòries | Presentació de l'assignatura durant la primera hora del curs. |
| Sessió Magistral | Casses teòriques introductòries de la matèria del curs. |
| Resolució de problemes, exercicis a l'aula ordinària | Per exercitar les diferents metodologies introduïdes a les sessions magistrals. |
| Pràctiques a través de TIC en aules informàtiques | Aplicar, a nivell pràctic, la teoria. Exercicis pràctics a través de les TIC. |
| Atenció personalitzada | Sis hores de consulta setmanals a disposició de l'alumne. |
| Atenció personalitzada |
| Descripció |
| Durant les 6 hores setmanals d'atenció personalitzada, l'alumne podrà anar al despatx del professor per tal d'aclarir dubtes, reforçar conceptes i tècniques, i demanar supervisió en la resolució d'exercicis. |
| Avaluació |
| Metodologies | Competències | Descripció | Pes | ||||
| Proves mixtes |
|
Tres proves individuals parcials mitjançant preguntes curtes amb solució tipus test i/o problemes de desenvolupament sobre els continguts proporcionats fins al moment. | 70% | ||||
| Proves pràctiques |
|
Els treballs realitzats al laboratori i completats a casa són presentats en forma documental. | 30% | ||||
| Altres | Lliurament d'exercicis realitzats individualment o en grup i demanats periòdicament. |
10% |
| Altres comentaris i segona convocatòria | |||
|
La segona convocatòria consistirà en un exàmen escrit avaluant el total dels continguts de l'assignatura. |
|||
| Fonts d'informació |
| Bàsica |
J. Ullman, J. John and R. Motwani, Introduccion a la teoria de Automatas, lenguajes y computación, Addison Wesley, 2002
D. Riaño, Models abstractes de càlcul, Tarragona : Universitat Rovira i Virgili, Servei Lingüístic, 1998 |
||||||||
| Complementària |
J. Levine, Flex & Bison: Text Processing Tools, O'Reilly Media, 2009 |
||||||||
| Recomanacions |
| Assignatures que en continuen el temari | |||
|
|||
| Assignatures que es recomana haver cursat prèviament | ||
|
||
(*)La Guia docent és el document on es visualitza la proposta acadèmica de la URV. Aquest document és públic i no es pot modificar, llevat de casos excepcionals revisats per l'òrgan competent/ o degudament revisats d'acord amb la normativa vigent