Algorísmia ( ALG )
| Crèdits: |
Departament: |
Tipus: |
Requisits: |
| 7.5 |
LSI |
Optativa per l'EI
Optativa per l'ETIG
Optativa per l'ETIS
|
|
ADA
- Pre-requisit per l' EI , ETIG
|
|
|
EST
- Pre-requisit per l' EI , ETIG , ETIS
|
|
|
Professors
| Responsable: | M Jose Serna Iglesias (mjserna lsi.upc.edu). |
| Altres: | Jordi Petit Silvestre (jpetitlsi.upc.edu). |
Objectius Generals
Ampliar el ventall de tècniques algorismiques i aprofundir en els seus fonaments teòrics. Aprofundir en el disseny i evaluació dels algorismes. Introduïr el algorismes probabilístics com a eina de disseny d'algorismes i l'enginyeria algorísmica com a selecció de les estructures de dades i de les tècniques algorismiques mes adients per a la resolució d'un problema concret.
Objectius Específics
Coneixements
- Anàlisi d'algorismes: Eficiència, costos, notació asimptòtica. Recurrències. Anàlisi en cas mitjà.
- Fonaments teòrics dels esquemes algorísmics.
- Algorismes fonamentals avançats: ordenació, grafs, hashing.
- Algorismes aleatòris: Tipus, técnicas elementals de disseny. Primalitat. Tècniques d'anàlisi.
Habilitats
- Ser capaç d'utilitzar tècniques avançades de disseny i anàlisi d'algorismes
- Saber raonar sobre la correció i l'eficiencia d'algorismes probabilistics.
- Conèixer alguns algorismes clàssics per problemes fonamentals.
- Saber identificar les components més rellevants d'un problema i seleccionar la tècnica algorismica mes adient.
- Ser capaç de seleccionar els tipus de dades mes adients per millorar la eficiència d'una solució algorísmica.
Competències
- Capacitat per al raonament crític i lògico-matemàtic
- Capacitat de resoldre problemes aplicant els mètodes de la ciència i l'enginyeria
- Capacitat per dissenyar sistemes, components o processos que s'ajustin a unes necessitats, utilitzant els mètodes, tècniques i eines més adients en cada cas.
- (1) Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
- (1) Capacitat per estudiar de diverses fonts, identificant quan la informació rebuda a classe no és suficient i cercant informació complementària.
- Capacitat per relacionar i estructurar informació de diverses fonts, per integrar idees i coneixements.
- Capacitat per transmetre idees efectivament de forma escrita.
- Disposició i capacitat per actualitzar-se al llarg de la carrera professional, quant a coneixements, procediments i tècniques.
Continguts
Hores estimades de:
| T |
P |
L |
Alt |
L Ext. |
Est |
A Ext. |
| Teoria |
Problemes |
Laboratori |
Altres activitats |
Laboratori extern |
Estudi |
Altres hores fora d'horari fixat |
|
1. Conceptes bàsics
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 3,0 |
4,0 |
0 |
0 |
0 |
3,0 |
0 |
10,0 |
|
|
El paper de l'algorismia a la computació. Analisi i diseny d'algorismes. Ordres de magnitud. Recurrències. Teorema Màster.
|
|
2. Algorismes d'ordenació
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
10,0 |
0 |
20,0 |
|
|
Repàs d'algorismes elementals. Mètodes amb cost lineal. Ànalisi en cas mitjà. QuickSort.
|
|
3. Esquemes algorísmics
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 9,0 |
6,0 |
0 |
0 |
0 |
17,0 |
0 |
32,0 |
|
L'esquema voraç. Fonaments teòrics. Aplicacions.
Programació dinàmica. Fonaments teòrics. Aplicacions.
|
|
4. Algorismes per a grafs
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
4,0 |
0 |
0 |
0 |
13,0 |
0 |
23,0 |
|
|
Component connexes. Camíns curts. Algorismes de Floyd-Warshall y Johnson. Algorismes per a matchings.
|
|
5. Hashing
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 3,0 |
4,0 |
0 |
0 |
0 |
7,0 |
0 |
14,0 |
|
|
Taules de hash. Funcions de hash. Perfect hashing.
|
|
6. Algorismes aleatoris
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 9,0 |
6,0 |
0 |
0 |
0 |
18,0 |
0 |
33,0 |
|
Repàs de probabilitats. Verificació d'identitats polinomials.
Algorismes Monte-Carlo i Las Vegas. Amplificació de probabilitat. Test de primalitat. Fites de concentració. Exemples en l'anàlisi d'algorismes aleatoris.
|
|
7. Enginyeria algorísmica
|
| T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 6,0 |
0 |
0 |
0 |
0 |
6,0 |
0 |
12,0 |
|
|
Quick-sort en Linux. Cues de prioritat.
|
| - Total per tipus |
T |
P |
L |
Alt |
L Ext |
Est |
A Ext |
Total |
| 42,0 |
28,0 |
0 |
0 |
0 |
74,0 |
0 |
144,0 |
- Hores addicionals dedicades a l'avaluació:
|
6,0 |
- Total hores de treball per l'estudiant |
150,0 |
|
Metodologia docent
Les classes es divideixen en dos tipus: sessions de teoria i sessions de problemes. En mitjana, la teoria ocupa tres hores setmanals i els problemes les altres dues hores. El professor adaptarà la repatició d'aquestes hores de la forma que millor s'ajusti al temari.
Les sessions de teoria són classes de tipus magistral en les que el professor aporta nous conceptes o noves tècniques conjuntament amb exemples que els motivin o els il.lustrin.
Les classes de problemes tenen com objectiu desenvolupar exercicis i es basen en la participació activa dels alumnes. Els professors proposen els problemes per avançat. La finalitat es que els alumnes presentin el treball fet i que es discuteixen les diverses solucions i/o alternatives.
Mètode d'avaluació
Aportacions per escrit a les classes de problemes (Pro). Examens Parcial (Par) i Final (Fin). Altres treballs voluntaris (Vol).
La nota final es calcula d'acord amb la fòrmula
min(0.7*max( (Par+Fin)/2 , Fin) + 0.3*Pro + Vol, 10)
La nota dels treballs voluntaris (si n'hi ha) estarà entre 0 i 1,5.
Bibliografía bàsica
(Informació no introduïda)
Bibliografía complementària
(Informació no introduïda)
Enllaços web
(Informació no introduïda)
Capacitats prèvies
(Informació no introduïda)
|
fib.upc.edu