Enginyeria Tècnica en Informàtica de Gestió - 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.