Corso di Algoritmi e Strutture Dati + Laboratorio - a.a. 1999/00
Prerequisiti
Le nozioni di base su struttura della macchina, linguaggio assembler,
utilizz odel computer, fornite dal corso e dal laboratorio di Architettura degli
elaboratori; nozioni di insieme, relazione, funzione, algebra, fornite
dal corso di Algebra.
Obiettivi
- Fornire le basi per progettare algoritmi (programmi) corretti ed efficienti
(da un lato, definendo criteri di correttezza e di efficienza; dall'altro,
esaminando problemi, algoritmi e stutture dati notevoli).
- Avviare all'uso di un linguaggio di programmazione di tipo imperativo.
Programma
Nota: l'ordine in cui sono elencati,
qui sotto, i singoli argomenti (ed il modo in cui sono raggruppati)
non corrisponde necessariamente a quello in cui verranno affrontati nel corso.
- Le caratteristiche essenziali di un linguaggio imperativo; algoritmi iterativi
e ricorsivi; correttezza.
- Strumenti matematici: induzione.
- Tipi di dato e strutture dati (nozioni di tipo di dato concreto e astratto
e di implementazione; liste, pile, code, alberi; implementazione di "insiemi" con
bit vectors, liste, arrays, hashing, binary search trees, tries).
- Ordinamenti di arrays e liste.
- Complessita' degli algoritmi (complessita' come funzione della "dimensione",
ordini di grandezza, stime della complessita' (tempo) di algoritmi in linguaggio
evoluto, complessita' intrinseca dei problemi).
- Tecniche per il progetto di algoritmi (divide et impera, ricerca esaustiva,
programmazione dinamica, ...) viste tramite esempi.
Programma di massima per il laboratorio
- Gli aspetti essenziali del linguaggio C.
- Programmazione in C degli algoritmi visti nel corso.
Testi di Riferimento
- Dispense: G. Costa: Appunti per il corso di Algoritmi e Strutture Dati.
Si possono acquistare in segreteria didattica o trovare ai due indirizzi
seguenti:
- Kernighan, Ritchie : Il linguaggio C (versione ANSI) - editore Jackson
Testi di consultazione o per approfondimenti
- Aho, Ullman: Fondamenti di Informatica - editore Zanichelli
- Cormen, Leiserson, Rivest: Introduzione agli Algoritmi, Vol 1 - editore
Jackson
- Darnell, Margolis: C Manuale di programmazione - editore Mc Graw Hill
- Vedere anche elenco inserito nelle dispense (ultima pagina).
Commenti a:puppo e
catania.
Ultima modifica: 2 giugno 99
Laurea e Diploma in
Informatica
Risultati Febbraio 2001: