21710. Teoria de la Computació . Grup 2

Identificació de l'assignatura

Assignatura21710 - Teoria de la Computació
Grup Grup 2 ( Campus Digital )
Any acadèmic 2018-19
Crèdits6 crèdits
Període d'impartició Primer semestre
Idioma d'impartició Català
Titulació
  • Grau d'Enginyeria Informàtica (Pla 2014) - Segon curs
  • Grau d'Enginyeria Informàtica (Pla 2010) - Segon curs

Professors

Professor/aHorari d'atenció alumnes
Hora d'iniciHora de fiDia de la setmanaData d'iniciData de fiDespatx/Edifici
Pedro Antonio Palmer Rodríguez
pere.palmerpere.palmer@uib.esuib.es
(Responsable)
16:30h17:30h Divendres 10/09/201825/01/2019 Anselm Turmeda D142
10:30h11:30h Divendres 10/09/201828/06/2019 Anselm Turmeda D142
Gabriel Moyà Alcover
gabriel.moyagabriel.moya@uib.esuib.es
10:30h13:30h Dimecres 14/09/201830/06/2019 209

Contextualització

Els costos de producció de programari són tan alts, en part, a causa de la manca de correcció dels sistemes informàtics que es dissenyen i s'implementen. En la pràctica diària, un programador no sol verificar els programes, per la qual cosa els casos en què les solucions proposades no funcionen no es detecten fins a les proves del programa o els experiments posteriors. Aquesta situació és, fins a un cert punt, comprensible, atesa la impossibilitat teòrica i pràctica de verificar de manera algorítmica els programes.
L'objectiu bàsic d'aquesta assignatura és augmentar els elements de judici dels programadors i afinar llur intuïció a fi i efecte que puguin produir programes més correctes, per mitjà de l'entrenament en la programació i verificació de mecanismes de computació senzills, com ara els autòmats finits i amb pila, i els programes en un llenguatge de programació molt simple, però suficient per simular qualsevol altre llenguatge. El tipus de raonament que proposam per a la verificació d'autòmats es basa en la identificació d'una sèrie de propietats que són invariants en una configuració de l'autòmat (una descripció instantània d'aquest, basada en l'estat del mecanisme de control, el contingut d'una memòria auxiliar, el valor de les variables en una posició del programa, etc.); és a dir, d'unes propietats que es pot mostrar que sempre són certes cada vegada que l'autòmat arriba a la mateixa configuració, encara que per arribar-hi hagi passat per diferents passos de còmput, com ara canvis d'estats, de continguts de la memòria o de variables. D'aquesta manera, el programador descobrirà que cada símbol que apareix en una solució d'un problema té un significat concret, basat en aquestes propietats invariants, i que aquests significats es relacionen d'una manera molt precisa que pot ser analitzada mitjançant eines matemàtiques.

Requisits

Tot i que l'assignatura no té requisits formals, es recomana haver aprovat l'assignatura de Matemàtica Discreta, perquè es requereix tenir l'habilitat d'argumentar sobre objectes discrets, i Programació II, amb la finalitat de saber programar i poder desenvolupar l'habilitat de reconèixer els seus límits.

Recomanables

20300 - Matemàtica Discreta

21707 - Programació II

Competències

Considerarem que hem reeixit en l'objectiu d'aquesta assignatura si l'ús de les tècniques que descrivim té com a resultat l'hàbit durador d'escriure solucions, programes, que respectin les relacions entre els significats intuïtius dels símbols usats, siguin aquests símbols estats, noms de variables d'una gramàtica, vectors, noms i posicions dins un programa, etc.

Aquesta assignatura hauria d'ajudar a millorar les habilitats de justificació de l'estudiant en certs aspectes de la programació.

Específiques

  • CFB02. Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorítmica i complexitat computacional, i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
  • CI301. 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.

Genèriques

  • CTR01. Capacitat d'anàlisi i síntesi, d'organització, de planificació i de presa de decisions.

Bàsiques

Podeu consultar les competències bàsiques que l'estudiant ha d'haver assolit en acabar el grau a l'adreça següent: http://estudis.uib.cat/grau/comp_basiques/

Continguts

Aquesta assignatura cobreix les nocions bàsiques de la teoria d'autòmats i llenguatges formals, com ara els autòmats finits, les expressions regulars, les gramàtiques incontextuals, els autòmats amb pila, els programes deterministes i indeterministes, la indecidibilitat i la complexitat.

Els principals objectius, aptituds i actituds a assolir per part dels alumnes són:

  • Que els alumnes tenguin la capacitat per definir i verificar autòmats d'estats finits, autòmats de pila i gramàtiques, així com el coneixement de les seves limitacions.
  • Que els alumnes coneguin la relació entre el desenvolupament correcte de programes i els autòmats d'estats finits, els autòmats de pila i les gramàtiques.
  • Que els alumnes tenguin presents els límits de la programació i tenguin capacitat per reduir un problema a un altre.
  • Que els alumnes tenguin l'habilitat de reconèixer problemes NP-complets.

Per aconseguir això s'han estructurat els continguts de la següent manera:

Continguts temàtics

1 Nocions bàsiques

Definició de llenguatge, concatenació, gramàtica, estrella de Kleen.

2 Programes

Definició de programa, indecidibilitat del llenguatge de l'aturada.

3 Programes no deterministes

Definició, exemples, equivalència.

Complexitat.

Definició de problemes no deterministes polinomials (NP), NP-complets, exemples, transformació de problemes.

4 Autòmats Finits

Autòmats deterministes i indeterministes, llenguatges regulars i no regulars, expresions regulars i verificació.

5 Autòmats de pila

Autòmats deterministes i indeterministes. Equivalencia amb gramàtiques. Estratègies de determinització.

6 Verificació d'autòmats de pila

Assercions, invariants, demostracions.

Metodologia docent

L?estudiant ha de resoldre problemes, quasi tots dels apunts, i els ha d?explicar als seus companys a la pissarra, els quals hauran de col·laborar en la solució.

Les eines d?aprenentatge de l?estudiant per ordre d?importància són: resolució individual d?exercicis, lectura dels apunts, tutories, resolució col·lectiva d?exercicis i assistència a classe.

Algunes classes es duran a terme amb demostracions pràctiques de programes que implementen els mecanismes dels llenguatges formals.

Volum de treball

El curs s'impartirà al llarg del primer semestre, des del 10 de setembre del 2018 fins al 7 de gener de 2019, ambdós inclosos. Està previst que hi hagi classe els dilluns i els divendres. En total hi haurà 14 sessions els dilluns i unes altres 14 els divendres, un total de 28 sessions de dues hores. La previsió és que la tres quartes parts de les classes siguin de teoria i l'altre quarta part sigui de resolució de problemes. Aquest plantejament es correspon amb tres hores de teoria i una de problemes per setmana. Hi haurà tres dies que es reservaran per realitzar els examens parcials, dos al llarg del curs i el tercer en el periode d'avaluació.

Activitats de treball presencial (2,4 crèdits, 60 hores)

ModalitatNomTip. agr.DescripcióHores
Classes teòriques Classes de teoria Grup gran (G)

Es pretén presentar els principals conceptes teòrics i exemples de l'assignatura, així com presentar els materials suplementaris que l'estudiant haurà de fer servir per a completar-los.

40
Classes pràctiques Classes de ressolució de problemes Grup mitjà (M)

Es pretén que els estudiants solucionin, per grups o de forma individual, problemes de l'assignatura, amb el suport del professor. Aquests problemes hauran de ser degudament lliurats i/o presentats a algunes classes.

14
Avaluació Primer examen parcial Grup gran (G)

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències dels tres primers temes.

2
Avaluació Segon examen parcial Grup gran (G)

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències del quart tema.

2
Avaluació Tercer examen parcial Grup gran (G)

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències dels darrers temes.

2

A començament del semestre hi haurà a disposició dels estudiants el cronograma de l'assignatura a través de la plataforma UIBdigital. Aquest cronograma inclourà almenys les dates en què es faran les proves d'avaluació contínua i les dates de lliurament dels treballs. A més, el professor o la professora informarà els estudiants si el pla de treball de l'assignatura es durà a terme a través del cronograma o per una altra via, inclosa la plataforma Campus Extens.

Activitats de treball no presencial (3,6 crèdits, 90 hores)

ModalitatNomDescripcióHores
Estudi i treball autònom individual Estudi de teoria

Estudi de teoria, d'exemples i preparació d'exàmens.

30
Estudi i treball autònom en grup Resolució d'exercicis

Resolució de tots els exercicis assignats.

60

Riscs especifics i mesures de protecció

Les activitats d'aprenentatge d'aquesta assignatura no comporten riscs específics per a la seguretat i salut dels alumnes i, per tant, no cal adoptar mesures de protecció especials.

Avaluació de l'aprenentatge dels estudiants

Presentam a continuació com seran avaluades les diferents activitats.
Observacions:

  • Els estudiants a temps complet seran avaluats seguint l'itinerari 'A'.
  • Els estudiants a temps parcial podran escollir l'itinerari d'avaluació.
  • Les activitats marcades com a 'No recuperable' ( entrega de problemes resolts als Tallers de ressolucio de problemes i durant el seu temps d'Estudi i treball autònom individual) vendran marcades per uns terminis de lliurament que els estudiants hauran de respectar si volen ser avaluats positivament.

Les activitats marcades com a 'Recuperable' es podran recuperar al periode d'avaluació extraordinari mitjançant una prova que substituirà la nota global dels examens parcials i final.

D'acord amb l'article 33 del Reglament Acadèmic, "amb independència del procediment disciplinari que es pugui seguir contra l'estudiant infractor, la realització demostradorament fraudulenta d'algun dels elements d'avaluació inclosos en guies docents de les assignatures comportarà, a criteri del professor, una menysvaloració en la seva qualificació que pot suposar la qualificació de «suspens 0» a l'avaluació anual de l'assignatura".

Classes de ressolució de problemes
Modalitat Classes pràctiques
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

Es pretén que els estudiants solucionin, per grups o de forma individual, problemes de l'assignatura, amb el suport del professor. Aquests problemes hauran de ser degudament lliurats i/o presentats a algunes classes.

Criteris d'avaluació

Correctesa dels resultats. Claretat en l'exposició. Rigorositat en els raonaments. S'avaluarà el nivell d'assoliment de les competències CFB02, CI301 i CTR01.

Percentatge de la qualificació final: 10% per a l'itinerari A
Percentatge de la qualificació final: 0% per a l'itinerari B

Primer examen parcial
Modalitat Avaluació
Tècnica Proves de resposta llarga, de desenvolupament ( recuperable )
Descripció

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències dels tres primers temes.

Criteris d'avaluació

Correctesa dels resultats. Claretat en l'exposició. Rigorositat en els raonaments. S'avaluarà el nivell d'assoliment de les competències CFB02, CI301 i CTR01.

Percentatge de la qualificació final: 30% per a l'itinerari A amb qualificació mínima 5
Percentatge de la qualificació final: 33% per a l'itinerari B amb qualificació mínima 5

Segon examen parcial
Modalitat Avaluació
Tècnica Proves de resposta llarga, de desenvolupament ( recuperable )
Descripció

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències del quart tema.

Criteris d'avaluació

Correctesa dels resultats. Claretat en l'exposició. Rigorositat en els raonaments. S'avaluarà el nivell d'assoliment de les competències CFB02, CI301 i CTR01.

Percentatge de la qualificació final: 30% per a l'itinerari A amb qualificació mínima 5
Percentatge de la qualificació final: 33% per a l'itinerari B amb qualificació mínima 5

Tercer examen parcial
Modalitat Avaluació
Tècnica Proves de resposta llarga, de desenvolupament ( recuperable )
Descripció

Examen parcial per avaluar l'evolució del nivell d'adquisició de les competències dels darrers temes.

Criteris d'avaluació

Correctesa dels resultats. Claretat en l'exposició. Rigorositat en els raonaments. S'avaluarà el nivell d'assoliment de les competències CFB02, CI301 i CTR01.

Percentatge de la qualificació final: 30% per a l'itinerari A amb qualificació mínima 5
Percentatge de la qualificació final: 34% per a l'itinerari B amb qualificació mínima 5

Recursos, bibliografia i documentació complementària

Trobareu gairebé tot el temari de l?assignatura al llibre de la bibliografia bàsica.


L?estudiant ha de llegir detingudament la part del llibre que correspon al temari i el professor explicarà la mateixa part i dedicarà més temps als temes difícils i als que no són als apunts, que el professor haurà marcat explícitament.

Bibliografia bàsica

Rocha, J., Teoria de la Computació. Servei de Publicacions, UIB, 2012.

Altres recursos

Mitjançant la plataforma de teleeducació Campus Extens, l'alumne tindrà a la seva disposició una sèrie de recursos d'interès per a la seva formació, com documents electrònics sobre la matèria elaborats pel professorat responsable de l'assignatura i enllaços a internet.