Anālisi i Disseny d'Algorismes (ADA)

Quatrimestre Q2 curs 2007-2008
Grup ADA 20

Calendari

Semana	Data	Dilluns	Dimarts	Divendres
1	18/2-22/2	Alg. Ord.	Alg. Ord.	An. Alg.
2	25/2-29/2	An. Alg.	An. Alg.
3	3/3-7/3	Est. Dades	Est. Dades	Est. Dades
4	10/3-14/3	Est. Dades		Est. Dades
5	25/3-28/3	Est. Dades	Grafs (Dill.)	Grafs
6	31/3-4/4	Grafs	Div. i Včncer	Div. i Včncer
7	7/4-11/4	Div. i Včncer	Prog. Din.
8	14/4-18/4
9	21/4-25/4	Prog. Din.	Prog. Din.	Prog. Din.
10	28/4-30/4	Alg.Voraįos	Alg.Voraįos (Div.)
11	5/5-8/5	Alg.Voraįos	Alg.Voraįos
12	13/5-16/5		Cerca Ex.	Cerca Ex.
13	19/5-23/5	Cerca Ex.	Cerca Ex.	Cerca Ex.
14	26/5-30/5	NP-Comp.	NP-Comp.

Temari

1. Algorismes d'ordenaciķ (taula de comparacions, en castellā).
   • Algorismes elementals d'ordenaciķ (selecciķ, inserciķ, bombolla).
   • Ordenaciķ per fusiķ.
   • Ordenaciķ rāpida.
   • Estabilitat d'algorismes d'ordenaciķ.

2. Anālisi d'algorismes (apunts, en castellā. Compte! poden haver errors tipogrāfics):
   • Costos en temps i en espai.
   • Talla de les entrades.
   • Cas pitjor, mitjā, millor.
   • Notaciķ asimptōtica.
   • Anālisi d'algorismes iteratius i recursius.

3. Ampliaciķ d'estructures de dades (apunts, en castellā. Compte! poden haver errors tipogrāfics):
   • Diccionaris implementats amb arbres binaris de cerca.
   • Cues de prioritat.
   • Heapsort.

4. Grafs (apunts, en castellā. Compte! poden haver errors tipogrāfics):
   • Representaciķ (matrius i llistes d'adjacčncia).
   • Costos.
   • Recorreguts (amplada i fondāria).
   • Ordenaciķ topolōgica.

5. Dividir i včncer (apunts. Compte! poden haver errors tipogrāfics):
   • Esquema general.
   • Cerca bināria.
   • Selecciķ.
   • Karatsuba
   • Strassen

6. Examen parcial: guia d'estudi.
7. Programaciķ dināmica.
8. Algorismes voraįos.
9. Cerca exhaustiva.
10. NP-completesa: transpas.
11. Examen final: guia d'estudi.