|
MABC: MODELS ABSTRACTES DE CALCUL
| Pla | ETIG |
Codi | 11727 |
Tipus | OPT |
Crèdits | 4,5 |
Intensitat presencial | |
| Curs | 4 |
Sigla | MABC |
Periocitat | 2 |
Depart | 723 |
| |
|
Idioma Clases
Català:
Espanyol:
Anglès:
|
Responsable | |
|
| Descripció [Català] | |
 |
|
|
| Descripció [Castellà] | |
|
|
|
| Descripció [Anglès] | |
|
|
| Ordre | Descripció | Tipus | Hores |
| 1 | Teoria | Temes | 0 |
| |
|
| Hores exposicions teòriques: 0 |
Hores treball pràctic: 0 |
| Hores treball grup: 0 |
Hores treball individual: 0 |
| | |
| Objectius | | |
| Analitzar la dificultat inherent als processos de càlcul i ìadquirir un coneixement teòric de les limitacions ìd'aquests processos (problemes indecidibles), i de la ìmanera de classificar els problemes segons la seva ìcomplexitat. Donar els elements bàsics per a l'estudi de ìla Teoria de la Calculabilitat i de la Teoria de la ìComplexitat. Els estudiants, després de cursar aquesta assignatura, ìhaurien de ser capaços de discernir sobre la decidibilitat ìo indecidibilitat d'una varietat de problemes, i de ìdonar-ne demostracions formals. També haurien de poder ìdiscernir sobre la complexitat temporal de certs tipus de ìproblemes. | | |
| Continguts | | |
| 1. Introducció 1.1 Problemes de decisió 1.2 Codificació de problemes 1.3 Conjunts enumerables i diagonalització 1.4 Algorismes i Models Abstractes de Càlcul 2. Màquines de Turing 2.1 Definició del model TM 2.2 TMs indeterministes 2.3 Altres models de computació: Tesi de Church 2.4 TMs com generadores de llenguatges 3. Calculabilitat 3.1 Codificació de TMs 3.2 TM universal 3.3 Llenguatges recursius i problemes decidibles 3.4 Reducció entre problemes 3.5 Teorema de Rice 4. Complexitat 4.1 Models TM per mesurar la complexitat 4.2 Complexitat en temps i en espai 4.3 Classificació per complexitat 4.4 Les classes P i NP 4.5 Problemes NP-complets 4.6 Demostració d'intractabilitat per reducció | | |
| | | |
|
|
| Hores Exposicions Teòriques: [0] |
| Hores Treball Pràctic: [0] |
| Hores de Treball en Grup: [0] |
| Hores treball individual: [0] |
|
| Hores totals: [0] |
| Crèdits ECTS: [0] |
|
|
|
|
|
| Hores Avaluació: 0 |
|
| Nota Final: 30% Presentaciones en clase + 70% Examen Final |
| |
| CRÈDITS ECTS: Detall dels crèdits totals, separats per tipus |
| Treball en curs |
|
Treball encarregat durant el curs, realitzat de forma individual, en un termini prefixat |
| Treball en grup |
|
Treball encarregat durant el curs, realitzat en grup, en un termini prefixat |
| Projecte individual |
|
Treball realitzat de forma individual, integrant diversos coneixements de la matèria, i diferent per a cada estudiant |
| Pràctiques (PC) |
|
Treball d'aplicació dels coneixements de la matèria en el cas pràctic real, realitzat de forma individual o en grup |
| Treball escrit (WW) |
|
Treball realitzat de forma individual i per escrit, en un termini prefixat |
| Exàmen escrit (WE) |
|
Prova individual realitzada per escrit en un temps fixat i en un lloc predeterminat i controlat |
| Ex. Teòric/pràctic (TP) |
|
Prova individual relacionada amb aspectes teòrics i pràctics de la matèria, realitzada en un temps fixat i en un lloc predeterminat i controlat |
|
|
