Dades generals

Curs acadèmic:
2018
Descripció:
Introduccio als llenguatges formals. Estudi i disseny d'autòmats. Introducció a la Teoria de la Computabilitat i Teoria de la Complexitat.
Crèdits ECTS:
5

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:
JAUME RIGAU VILALTA
Idioma de les classes:
Català (100%)

Competències

  • CT05 Recollir i seleccionar informació de forma eficaç
  • 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. Tesis de Church-Turing

          4.1. Gramàtiques sense restriccions

          4.2. Maquines 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. Reducibilitat

          6.1. Problemes indecidibles

          6.2. Un simple problema indecidible

          6.3. Funció de Reducibilitat

7. Complexitat en Temps

          7.1. Mesura de complexitat

          7.2. La classe P

          7.3. La classe NP

          7.4. NP-completessa

          7.5. Alguns problemes NP-complets

8. Computació quàntica (exclòs d'avaluació)

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Total
Classes expositives 28 0 28
Classes pràctiques 14 0 14
Lectura / comentari de textos 0 40 40
Prova d'avaluació 4 0 4
Treball en equip 0 36 36
Tutories 3 0 3
Total 49 76 125

Bibliografia

  • Michael Sipser (2006). Introduction to the Theory of Computation (2). Course Technology. CENGAGE Learning. Catàleg
  • JE Hopcroft, R. Motwani, KD Ullman (2001). Introduccion a la teoria de automatas, lenguajes, y computacion. Addison-Wesley. Catàleg
  • Joan Vancells, Miquel Bofill (2000). Teoria D'autòmats I Llenguatges Formals II. UOC. Catàleg
  • JG Brookshear (1979). Teoria de la computacion. Addison-Wesley. 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

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
Resolució de problemes sobre el temari (en equip) Disseny, implementació, format presentació, eficiència, i complexitat. 50
Prova d'avaluació de continguts Solucionar questions relacionades amb el temari. 50

Qualificació

Classes de teoria setmanals més classes de suport a la teoria (exemples/exercicis) bisetmanals (s'imparteixen d'acord a la seqüència marcada pel contingut teòric setmanal) d'acord al calendari oficial de l'EPS que estableixi el Coordinador del Grau.

La qualificació de l’assignatura es realitzarà en base a dos aspectes:

A) Resolució problemes (avaluació pràctica):
Els alumnes resoldran (en paral·lel a les classes i en grup) un treball global que es desglossa en diversos subproblemes relacionats amb l'assignatura. Caldrà obligatòriament entregar-lo dins d'un termini preestablert. L'enunciat indicarà la forma i data d'entrega. S'avaluarà entre 0 i 10. Tanmateix, la no presentació, sense causa justificada, comptabilitzarà com a NP (No Presentat).

B) Coneixement sobre el contingut del temari (avaluació dels conceptes bassats en l'assistència continuada 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 és 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).

Nota final: si la qualificació de A o B és un NP, la nota final esdevé NP. Altrament, és la mitjana dels dos apartats previs: (A+B)/2. Ambdòs apartats no són recuperables i en conseqüència, la nota final comença a definir-se des del primer dia amb el vostre treball personal i en equip.

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 eficacia demostrada. La còpia comporta un 0 en la qualificació final per a tots els implicats.

Pels alumnes no-presencials o semi-presencials, el sistema d'evaluació és exactament el mateix.

Es recomana llegiu també l'apartat "Observacions i Recomanacions" d'aquesta assignatura. Tots els detalls d'implementació de l'assignaturá constaràn al document "Sylabus" (guia docent detallada del curs) i que se us posarà a disposició als inicis de setembre.

Criteris específics de la nota «No Presentat»:
Es considerarà no-presentat a l'estudiant que no entregui qualsevol dels problemes de l'apartat d'avaluació A o bé, que no es presenti a la prova escrita indicada a l'apartat B d'evaluació.

Observacions

a) 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.

b) Tota la documentació necessaria la podreu trobar a la web de l'assignatura en el moment adecuat. Se us comunicarà sempre d'acord a l'apartat previ.

c) De lectura OBLIGATÒRIA:

c.1) Tota la informació relativa a l'assignatura constarà al document electrònic "Syllabus" de l'assignatura (Guia detallada del curs) que se us enviarà els primers dies de Setembre d'acord amb els apartats previs a) i b).

c.2) 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 situarse en el vocabulari, notació, i com a recordatori de conceptes previs de matemàtiques. L'ús continuu del text al llarg de totes les classes expositives facilitarà el treball als estudiants amb assistència discontinua per motius de treball (o altres).

c.3) Tanmateix, junt amb el "Sylabus", se us facilitarà el document electrònic "Complementary Theory & Problems" (Informació adicional de teoria i problemes). En aquest document hi consten també els problemes corresponents a l'apartat A de l'evaluació.

Assignatures recomanades

  • 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
  • Projecte de programació