Corso tenuto presso il Polo Universitario “G. Marconi” di La Spezia, Corso di Laurea in Informatica Applicata.
Docenti: Anna Bernasconi Giuseppe Prencipe
Impegno: 12 CFU (9 di teoria e 3 di laboratorio)
Le lezioni si svolgono presso il Polo Universitario “G. Marconi” di La Spezia.
| Orario delle lezioni |
| Lunedì | 11:00-12:30, 14:00-15:30 | Aula A2 |
| Giovedì | 11:00-12:30, 14:00-15:30 | Aula A5 |
| Ricevimento |
| Lunedì | 10:00-11:00 | Polo G. Marconi |
| Giovedì | 10:00-11:00 | Polo G. Marconi |
Teoria
C. Demetrescu, I. Finocchi e G. F. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, seconda edizione, 2008 (Testo di Riferimento)
P. Crescenzi, G. Gambosi e R. Grossi, Strutture di dati e algoritmi, Pearson – Addison Wesley, 2006
Per le attività di laboratorio è sufficiente l'utilizzo di un editor e di gcc. gcc è disponibile sulle macchine Linux. Per le macchine Windows, è sufficiente installare il pacchetto MiniGW. Su sistemi MAC, è necessario installare gli Xcode Tools, presenti nel CD/DVD di installazione della macchina.
Come editor, potete utilizzare Jedit.
Per un più proficuo utilizzo delle ore di laboratorio, si consiglia fortemente di studiare approfonditamente i primi 5 capitoli del libro di testo consigliato per le attività di laboratorio (Il Linguaggio C).
Problemi Computazionali
Array e liste
Alberi e grafi
Dizionari
Pile e code
NP-completezza
Introduzione al Corso (22/02/2010)
Introduzione informale agli algoritmi
I numeri di Fibonacci
Algoritmo numerico
Algoritmo ricorsivo
Algoritmo iterativo
Occupazione di memoria e altro algoritmo iterativo
Introduzione alla notazione asintotica
Algoritmo basato su potenze ricorsive
Nota sulla dimensione dell'istanza in ingresso (25/02/2010)
Problema 1.4 (dal libro di testo)
Modelli di calcolo e metodologie di analisi
Modelli di calcolo
Criteri di costo (uniforme e logaritmico)
La notazione asintotica (O, Ω, Θ)
Costo degli algoritmi e complessità dei problemi
Metodi di analisi (caso peggiore, migliore e medio)
Ricerca sequenziale
Ricerca binaria
Analisi di algoritmi ricorsivi
Metodo iterativo
Metodo della sostituzione
Analisi dell'albero di ricorrenza
Metodo del cambiamento di variabile
Master Theorem (con dimostrazione) (01/03/2010)
Introduzione all'Analisi Ammortizzata
Esercitazione (Capitoli 1 e 2 del testo di riferimento)
Strutture dati elementari (04/03/2010)
Strutture indicizzate: array
Strutture collegate: record e puntatori
Dizionari
Pile e code
Relazione tra Pila e Ricorsione
Alberi
Ordinamento con confronti (08/03/2010)
Limite inferiore al problema
Algoritmi quadratici: Selection Sort, Insertion Sort, Bubble Sort
Heapsort
Mergesort
Introduzione al Quicksort
Analisi di complessità nel caso medio del Quicksort (11/03/2010)
Altri tipi di ordinamento
Laboratorio C n. 1 (15/03/2010). Per la lezione, è di fondamentale importanza conoscere:
Selezione del k-esimo elemento (18/03/2010)
Soluzione con k piccolo
Heapselect
Quickselect
Mediano dei mediani
Alberi di ricerca (22/03/2010)
Alberi binari di ricerca
Alberi AVL
Alberi 2-3
Panoramica sui B-Alberi
Tabelle hash
-
Laboratorio C n. 2 (
02/04/2009). Programmi da sviluppare in C per il 2 Aprile (
esercizi svolti):
Fibonacci numerico
Fibonacci ricorsivo (esponenziale)
Fibonacci iterativo con array
Fibonacci iterativo con 3 variabili
Tecniche algoritmiche (06/04/2009)
Divide et impera
Programmazione dinamica
Prima verifica intermedia (09/04/2009)
Laboratorio C n. 3 (
16/04/2009) Programmi da sviluppare in C per il 16 Aprile (
esercizi svolti):
Tecniche algoritmiche (20/04/2009)
Stringhe
Definizioni
Distanza fra 2 stringhe
Massima sottosequenza comune (LCS)
String matching
Stringhe e automi a stati finiti
Algoritmo di Knuth, Morris e Pratt (23/04/2009)
-
Definizioni
Rappresentazione di grafi
Visite (ampiezza e profondità)
Componenti connesse di un grafo non orientato
Componenti fortemente connesse di un brafo orientato (27/04/2009)
Minimo albero di copertura
Kruskal
Prim
Boruvka
-
Problemi indecidibili e intrattabili
Classi Time, PSpace, ExpTime e P
SAT e formule Booleane quantificate
La classe NP
Problemi NP-completi
Il Teorema di Cook
NP-completezza del Problema della Clique
Algoritmi di approssimazione
Cammini minimi (04/05/2009)
Laboratorio C n. 4 (
07/05/2009) Programmi da sviluppare in C per il 7 Maggio (
esercizi svolti):
LeggiScriviChar(): Lettura e scrittura di caratteri con getchar() e putchar()
Reverse1(): inversione di una stringa costante
Reverse2(): inversione di una serie di stringhe lette da tastiera. Ogni stringa termina con '\n' e la serie termina con il carattere '0'. La stringa invertita viene stampata a video
LeggiStringhe(): lettura di una serie di stringhe da tastiera. Ogni stringa termina con '\n' e la serie termina con il carattere '0'. Tutte le stringhe sono inserite in un array, che viene stampato
GeneraStringhe(): genera casualmente un intero x; alloca memoria per un array di x stringhe lunghe al più 10 caratteri; genera x stringhe casuali lunghe al più 10 caratteri che sono inserite nell'array. NOTA: inizializzare il seme casuale mediante invocazione di srand(time(NULL))
OrdinaStringhe(): ordina un array di stringhe. Utilizzare come base di partenza un qualsiasi algoritmo di ordinamento sviluppato per la Lezione n. 3. Inoltre, utilizzare GeneraStringhe() per generare le stringhe da inserire nel vettore da ordinare
Laboratorio C n. 5 (14/05/2009)
