Dades generals
-
Curs acadèmic:
- 2020
-
Descripció:
- Introduccio als llenguatges formals. Estudi i disseny d'autòmats. Introducció a la Teoria de la Computabilitat i a la Teoria de la Complexitat.
-
Crèdits ECTS:
- 5
Grups
Grup A
-
Durada:
- Semestral, 1r semestre
-
Professorat:
- Miquel Bofill Arasa
-
Idioma de les classes:
- Català (50%), Anglès (50%)
Competències
- CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
- CT05 Recollir i seleccionar informació de forma eficaç
- CT06 Disenyar propostes creatives
- CC1 Capacitat per a tenir un coneixement profund dels principis fonamentals i models de la computació i saber-los aplicar per a intentar, seleccionar, valorar, modelar, i crear nous conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica.
- CC3 Capacitat per avaluar la complexitat computacional d'un problema, conèixer estratègies algorítmiques que poguin conduir a la seva resolució i recomenar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.
Continguts
1. Introducció
1.1. Autòmats, computabilitat, i complexitat
1.2. Notació matemàtica i terminologia
1.3. Definicions, teoremes, i demostracions
1.4. Tipus de demostracions
2. Llenguatges regulars
2.1. Gramàtiques regulars
2.2. Autòmats finits
2.3. Indeterminisme
2.4. Expressions regulars
2.5. Llenguatges no regulars
3. Llenguatges lliures de context
3.1. Gramàtiques lliures de context
3.2. Autòmats de pila
3.3. Llenguatges no lliures de context
4. Tesi de Church-Turing
4.1. Gramàtiques sense restriccions
4.2. Màquines de Turing
4.3. Variants de màquines de Turing
4.4. Definició d'algorisme
5. Decidibilitat
5.1. Llenguatges decidibles
5.2. El problema de l'aturada
6. Reduïbilitat
6.1. Problemes indecidibles
6.2. Un simple problema indecidible
6.3. Funció de reduïbilitat
7. Complexitat en temps
7.1. Mesura de complexitat
7.2. La classe P
7.3. La classe NP
7.4. NP-completesa
7.5. Alguns problemes NP-complets
Activitats
Tipus d’activitat |
Hores amb professor |
Hores sense professor |
Hores virtuals amb professor |
Total |
Anàlisi / estudi de casos |
0
|
18,00 |
0
|
18,00 |
Lectura / comentari de textos |
0
|
40,00 |
0
|
40,00 |
Prova d'avaluació |
4,00 |
0
|
0
|
4,00 |
Resolució d'exercicis |
0
|
18,00 |
0
|
18,00 |
Sessió expositiva |
0
|
0
|
28,00 |
28,00 |
Sessió pràctica |
14,00 |
0
|
0
|
14,00 |
Tutories de grup |
0
|
0
|
3,00 |
3,00 |
Total |
18,00 |
76,00 |
31,00 |
125 |
Bibliografia
- Michael Sipser (2006). Introduction to the Theory of Computation (2). Course Technology. CENGAGE Learning. Catàleg
- Sesa Nogueras, Enric (2000). Teoria d'autòmats i llenguatges formals I. Barcelona: Universitat Oberta de Catalunya. Catàleg
- Joan Vancells, Miquel Bofill (2000). Teoria D'autòmats I Llenguatges Formals II. UOC. Catàleg
- Casas, Rafel (2003). Llenguatges, gramàtiques i autòmats (2a ed.). Barcelona: Edicions UPC, a http://biblioapps.udg.edu/biblioteca-digital/llibresdigitalsUPC/llibre.php?codi=IN010XXX Catàleg
- Serna, Maria José (2001). Els Límits de la computació. Barcelona: Edicions UPC, a http://biblioapps.udg.edu/biblioteca-digital/llibresdigitalsUPC/llibre.php?codi=IN029XXX Catàleg
- JE Hopcroft, R. Motwani, KD Ullman (2001). Introduccion a la teoria de automatas, lenguajes, y computacion. Addison-Wesley. Catàleg
- Kelley, Dean (1995). Teoría de autómatas y lenguajes formales. Madrid [etc.]: Prentice Hall. Catàleg
- P. Isasi, P. Martinez, D. Borrajo (1997). Lenguajes, gramáticas y autómatas. Un enfoque práctico (1). Madrid: Addison-Wesley Iberoamericana España, S.A.. Catàleg
- JG Brookshear (1979). Teoria de la computacion. Addison-Wesley. Catàleg
Avaluació i qualificació
Activitats d'avaluació:
Descripció de l'activitat |
Avaluació de l'activitat |
% |
Recuperable |
Resolució d'exercicis de llenguatges, gramàtiques i autòmats |
Presentació, precisió i correcció de les solucions proposades. |
25 |
No |
Resolució d'exercicis de calculabilitat i complexitat |
Presentació, precisió i correcció de les solucions proposades. |
25 |
No |
Examen |
Solucionar qüestions relacionades amb el temari. |
50 |
Sí |
Qualificació
Classes de teoria setmanals més classes de suport a la teoria (exemples/exercicis) bisetmanals.
La qualificació de l’assignatura es realitzarà en base a dos aspectes:
A) Resolució d'exercicis (avaluació continuada)
Els alumnes resoldran duran el curs una sèrie d'exercicis relacionats amb el temari de l'assignatura, que caldrà lliurar obligatòriament dins del termini que s'estableixi. L'enunciat indicarà la forma i data límit de lliurament. S'avaluaran entre 0 i 10. La no presentació comptabilitzarà com a 0.
Hi haurà un bloc d'exercicis de la part de llenguatges, gramàtiques i autòmats (A1) i un bloc d'exercicis de la part de calculabilitat i complexitat (A2).
B) Examen (avaluació del coneixement del temari treballat a classe i de la bibliografia de l'assignatura)
Es basarà en una prova individual per escrit i sense cap suport documental. La data i hora serà la determinada en l'horari d'exàmens de l'EPS. Aquest apartat es valorarà de 0..10 excepte si l'estudiant no es presenta a la prova (nota apartat = NP).
La nota final (NF) es calcularà de la següent manera:
NF := NP si B = NP
NF := B si B < 3
NF := ((A1 + A2) / 2) + B) / 2 si B >= 3
Sempre que es consideri oportú, es podrà citar personalment a un alumne per tal de que demostri el seu coneixement i participació en l'apartat A. Tanmateix, es recorda als estudiants que es disposen de programes automàtics de detecció de còpia d'una eficàcia demostrada. La còpia comporta un 0 en la qualificació final per a tots els implicats.
Per als alumnes no presencials o semi-presencials, el sistema d'avaluació és exactament el mateix atès que emprem el nucli d'un llibre de text que facilita el seguiment de l'assignatura (veure bibliografia).
Es recomana llegir també l'apartat "Observacions i Recomanacions" d'aquesta assignatura.
Criteris específics de la nota «No Presentat»:
L'alumne obrindrà la nota de "No Presentat" si no es presenta a examen.
Avaluació única:
L'avaluació única consistirà solament de l'examen final, amb un valor del 100% en lloc del 50%.
Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació més gran o igual que 5 de la nota final (NF) calculada com s'ha descrit més amunt.
Tutoria
Les tutories es faran preferentment via Google Meet, Skype o similar, amb sol·licitud prèvia de l'estudiant i confirmació del professor mitjançant correu electrònic. Si les circumstàncies ho permeten, i d'acord entre l'estudiant i el professor, les tutories es podran fer presencialment al despatx del professor o en algun altre espai habilitat de l'EPS.
Comunicacio i interacció amb l'estudiantat
Les comunicacions de l'assignatura es faran per escrit mitjançant el "Fòrum d'Avisos i Notícies" de la Meva-UdG de l'assignatura.
La interacció escrita amb els estudiants tindrà lloc també preferentment via fòrums del Moodle, reservant el correu electrònic només per a qüestions privades. Qualsevol consulta que es realitzi per correu electrònic que sigui d'interès general serà redirigida al fòrum corresponent del Moodle.
Les classes online es realitzaran via Google Meet i es gravaran per a posterior visualització. Per tal d'evitar interrupcions (peticions d'accés) durant les classes, només es permetrà l'accés a aquestes via el compte de Google associat a la UdG, amb el qual no és necessari demanar permís per connectar-s'hi.
Observacions
a) Està previst que les classes de teoria setmanals siguin online, mentre que les classes bisetmanals de suport siguin presencials.
b) Tota la documentació necessària la podreu trobar al web de l'assignatura en el moment adequat.
c) De lectura OBLIGATÒRIA:
Del llibre de text de Michael Sipser (veure bibliografia):
- Part 1: capítols 1 i 2.
- Part 2: capítols 3, 4, i 5.
- Part 3: capítol 7.
El capítol 0 d'introducció es bàsic per situar-se en el vocabulari, notació, i com a recordatori de conceptes previs de matemàtiques. L'ús continu del text al llarg de totes les classes expositives facilitarà el treball als estudiants amb assistència discontínua per motius de treball (o altres).
Assignatures recomanades
- Àlgebra
- Càlcul
- Estructures de dades i algorítmica
- Lògica i matemàtica discreta
- Metodologia i tecnologia de la programació I
- Metodologia i tecnologia de la programació II
Modificació del disseny
Modificació de les activitats:
En el cas que les circumstàncies obliguessin a un 0% de presencialitat, les activitats previstes es mantindrien igual amb l'excepció que les classes serien totes via Google Meet.
Modificació de l'avaluació:
La forma d'avaluació es mantindrà igual encara que les circumstàncies obliguin a un 0% de presencialitat, substituint la presencialitat per xats via Google Meet.
Tutoria i comunicació:
En el cas que les circumstàncies obliguin a un 0% de presencialitat, la forma de tutoria i comunicació continuarà sent prioritàriament via Google Meet i fòrums del Moodle, tal com s'ha descrit a l'apartat corresponent, desapareixent la possibilitat de fer tutories presencials.