Estudia > Oferta formativa > Oferta d'assignatures > Detall de l'assignatura
Anar al contingut (clic a Intro)
UdG Home UdG Home
UdG 30 anys
Tancar
Menú

Estudia a la UdG

Dades generals

Curs acadèmic:
2022
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à (100%)

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. Autòmats finits

          2.2. Indeterminisme

          2.3. Expressions regulars

          2.4. Llenguatges no regulars

3. Llenguatges lliures de context

          3.1. Gramàtiques lliures de context

          3.2. Autòmats amb pila

4. Tesi de Church-Turing

          4.1. Màquines de Turing

          4.2. Variants de màquines de Turing

          4.3. Definició d'algorisme

5. Decidibilitat

          5.1. Llenguatges decidibles

          5.2. Indecidibilitat

6. Reduïbilitat

          6.1. Problemes indecidibles

          6.2. Un problema indecidible simple

          6.3. Funcions de reducció

7. Complexitat en temps

          7.1. Mesures 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
Lectura / comentari de textos 0 40,00 0 40,00
Prova d'avaluació 4,00 0 0 4,00
Resolució d'exercicis 0 36,00 0 36,00
Sessió expositiva 28,00 0 0 28,00
Sessió pràctica 14,00 0 0 14,00
Tutories de grup 3,00 0 0 3,00
Total 49,00 76,00 0 125

Bibliografia

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 Correcció i precisió de les solucions proposades 25 No
Resolució d'exercicis de calculabilitat i complexitat Correcció i precisió de les solucions proposades 25 No
Examen Correcció i precisió de les solucions proposades 50

Qualificació

Es faran classes de teoria setmanals més classes de suport a la teoria (exemples i 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à entre 0 i 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 := max(B, ((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.

Per als alumnes no presencials o semipresencials, el sistema d'avaluació és exactament el mateix atès que s'empra el nucli d'un llibre de text que facilita el seguiment de l'assignatura (veure bibliografia).

Per accedir a l'examen de recuperació caldrà haver-se presentat a l'examen final (excepte casos justificats) i tenir l'assignatura suspesa. Notar que un examen suspès no dóna dret a recuperació si l'assignatura queda aprovada. La qualificació de l'examen de recuperació substituirà la de l'examen final.

Es recomana llegir també l'apartat 'Observacions i Recomanacions'.

Criteris específics de la nota «No Presentat»:
L'alumne obrindrà la nota de 'No Presentat' si no es presenta a l'examen.

Avaluació única:
L'avaluació única consistirà únicament de l'examen final, amb un valor del 100% de la nota.

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 a l'apartat 'Criteris de qualificació'.

Tutoria

Les tutories es faran de manera presencial sempre que es pugui.

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" del Moodle.

La interacció escrita (bidireccional) amb els estudiants tindrà lloc 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.

Observacions

a) Tota la documentació necessària la podreu trobar al web de l'assignatura en el moment adequat.

b) 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

  • Estructures de dades i algorítmica
  • Lògica i matemàtica discreta

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.