Enginyeria Tècnica en Informàtica de Sistemes - Tercer curs

Objectiu genèric de l’assignatura: Es tracta d’estudiar la teoria bàsica dels models abstractes de càlcul i llenguatges formals. Aquesta teoria permet enunciar propietats generals sobre les funcions que poden calcular els ordinadors i, més generalment, sobre els tipus de problemes resolubles. Es classificaran els problemes segons la seva dificultat relacionant-los amb els llenguatges formals. Es posarà especial atenció a l’existència de problemes indecidibles o no resolubles usant algorismes, programes i ordinadors. Finalment s’introdueix la complexitat espacial i temporal dels algorismes i problemes.

1. Ordenar les propietats dels models formals en què es basen els ordinadors.                 2. Aprendre a construir models de càlcul per acceptar els diversos tipus de llenguatges formals.
3. Aprendre a construir gramàtiques per generar els diversos tipus de llenguatges formals. 4. Aprendre a identificar i representar els llenguatges, i com es classifiquen a partir dels models de càlcul.
5. Entendre la relació entre els diversos tipus de llenguatges formals.
6. Entendre la relació entre els models de càlcul i els algorismes.
7. Entendre com els llenguatges formals representen els problemes.
8. Identificar les possibilitats i els límits de la computació a partir de la classificació dels llenguatges formals.
9. Identificar el grau de complexitat dels problemes (decidible, semidecidible o indecidible), relacionantlos amb els llenguatges formals que els representen.
10. Classificar els algorismes i els problemes segons la seva complexitat, a partir dels models de càlcul
i dels llenguatges decidibles que els modelitzen.
11. Entendre l’existència de problemes tractables i intractables.

Competències Generals: Les competències que intentem desenvolupar en aquesta assignatura són:
1. Capacitat d’estudi d’un problema abans d’afrontar la seva solució.
2. Capacitat per entendre els límits de la computació.
3. Fomentar la capacitat d’anàlisi i de síntesi (raonament crític).
4. Assumir i dominar la comunicació oral i la comunicació escrita.
5. Apreciar i potenciar el treball en equip.

Competències Específiques:
1. Proposar eines per a modelitzar el llenguatge (els llenguatges de programació).
2. Precisar les capacitats computacionals dels models de càlcul i de les gramàtiques.
3. Plantejar i resoldre problemes en termes de models de càlcul o de gramàtiques.
4. Modelitzar algorismes a partir models de càlcul.
5. Identificar problemes no resolubles.
6. Ser capaç d’abstraure els detalls d’un problema per identificar problemes intractables coneguts.