Algoritmica e Laboratorio
Corso tenuto presso il Polo Universitario “G. Marconi” di La Spezia, Corso di Laurea in Informatica Applicata.
News
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 A5, A2 |
Giovedì | 11:00-12:30, 14:00-15:30 | Aula A7, A5 |
Ricevimento |
Lunedì | 10:00-11:00 | Polo G. Marconi |
Giovedì | 10:00-11:00 | Polo G. Marconi |
Testi Consigliati e Laboratorio
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).
Contenuti del Corso
Problemi Computazionali
Array e liste
Alberi e grafi
Dizionari
Pile e code
NP-completezza
Registro delle lezioni
Introduzione al Corso (07/03/2011)
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 (10/03/2011)
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) (14/03/2011)
Introduzione all'Analisi Ammortizzata
Esercitazione (Capitoli 1 e 2 del testo di riferimento)
Strutture dati elementari (04/03/2011)
Strutture indicizzate: array
Strutture collegate: record e puntatori
Dizionari
Pile e code
Relazione tra Pila e Ricorsione
Alberi
Ordinamento con confronti (24/03/2011)
Limite inferiore al problema
Algoritmi quadratici: Selection Sort, Insertion Sort, Bubble Sort
Heapsort
Mergesort
Introduzione al Quicksort
Laboratorio C n. 1 (28/03/2011). Per la lezione, è di fondamentale importanza conoscere:
Quicksort: Analisi di complessità nel caso medio del Quicksort (31/03/2011)
Altri tipi di ordinamento
Selezione del k-esimo elemento
Soluzione con k piccolo
Heapselect
Quickselect
Mediano dei mediani
Esercitazione (04/04/2011)
Alberi di ricerca (07/04/2011)
Alberi binari di ricerca
-
Esercitazione: ABR, AVL.
Alberi 2-3 (11/04/2011)
Panoramica sui B-Alberi
Tabelle Hash
Laboratorio C n. 2 (
14/04/2011). Programmi da sviluppare in C per il 14 Aprile (
esercizi svolti):
Fibonacci numerico
Fibonacci ricorsivo (esponenziale)
Fibonacci iterativo con array
Fibonacci iterativo con 3 variabili
Selection Sort e Insertion Sort
Prima verifica intermedia (18/04/2011)
-
-
Tecniche algoritmiche (02/05/2011)
Divide et impera
Programmazione dinamica
Greedy (05/05/2011)
Stringhe
Programmazione dinamica: approfondimenti (09/05/2011)
-
Definizioni e terminologia
Rappresentazione di grafi in memoria (12/05/2011)
Visite in ampiezza (BFS) e in profondità (DFS) e loro proprietà
Componenti connesse di un grafo non orientato (16/05/2011)
Componenti fortemente connesse di un grafo orientato (cenni)
Esercitazione: esercizi su grafi
-
Minimo albero ricoprente (19/05/2011)
-
Laboratorio C n. 3 (
23/05/2011) Programmi da sviluppare in C per il 23 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
Laboratorio C n. 4 (26/05/2011) Programmi da sviluppare in C per il 26 Maggio
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
Realizzazione di code e pile tramite strutture
-
Problemi 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