Corso tenuto presso il Polo Universitario “G. Marconi” di La Spezia, Corso di Laurea in Informatica Applicata.

Testo e soluzioni Appello del 5/9/2011

Qui trovate vecchi compiti, con relative soluzioni: Testi e alcune soluzioni compiti scritti AA2009-10

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.

• 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

• Laboratorio (Programmazione in C)
  • B.W. Kernighan, D.M. Ritchie. Il Linguaggio C, Pearson-Prentice Hall, seconda edizione, 2004

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

1. Introduzione al Corso (07/03/2011)
2. 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)
3. 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
4. Esercitazione (Capitoli 1 e 2 del testo di riferimento)
5. Strutture dati elementari (04/03/2011)
   • Strutture indicizzate: array
   • Strutture collegate: record e puntatori
   • Dizionari
   • Pile e code
   • Relazione tra Pila e Ricorsione
   • Alberi
     • Rappresentazioni indicizzate
     • Rappresentazioni collegate
     • Visite di alberi
6. Ordinamento con confronti (24/03/2011)
   • Limite inferiore al problema
   • Algoritmi quadratici: Selection Sort, Insertion Sort, Bubble Sort
   • Heapsort
   • Mergesort
   • Introduzione al Quicksort
7. Laboratorio C n. 1 (28/03/2011). Per la lezione, è di fondamentale importanza conoscere:
   • Struttura generale di un programma C
   • Sintassi di:
     • Dichiarazione variabili
     • Array
     • Dichiarazione e invocazione di funzioni
8. Quicksort: Analisi di complessità nel caso medio del Quicksort (31/03/2011)
9. Altri tipi di ordinamento
   • Integer sort, Bucket sort, Radix sort
10. Selezione del k-esimo elemento
    • Soluzione con k piccolo
      • Algoritmo semplice e algoritmo del torneo
    • Heapselect
    • Quickselect
    • Mediano dei mediani
11. Esercitazione (04/04/2011)
    • Progettazione di algoritmi efficienti e analisi della loro complessita`
    • Algoritmi ricorsivi su alberi
12. Alberi di ricerca (07/04/2011)
    • Alberi binari di ricerca
    • Alberi AVL (rotazioni)
    • Esercitazione: ABR, AVL.
    • Alberi 2-3 (11/04/2011)
    • Panoramica sui B-Alberi
13. Tabelle Hash
14. 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
15. Prima verifica intermedia (18/04/2011)
16. Liste invertite (28/04/2011)
17. Trie, trie compatti, suffix tree
18. Tecniche algoritmiche (02/05/2011)
    • Divide et impera
      • Moltiplicazione di interi di grandezza arbitraria
      • Moltiplicazione tra matrici
    • Programmazione dinamica
      • Sottovettore di valore massimo
      • Cammini di valore minimo su matrici
    • Greedy (05/05/2011)
      • Il problema dello zaino
      • Il distributore automatico di resto
      • Ricoprimento di punti con intervalli
19. Stringhe
    • Definizioni
    • Distanza fra 2 stringhe
    • Massima sottosequenza comune
20. Programmazione dinamica: approfondimenti (09/05/2011)
    • Ricostruzione delle soluzioni
    • Algoritmo di programmazione dinamica per il problema dello zaino
    • Algoritmi pseudo-polinomiali
21. Grafi
    • 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
22. Liste per insiemi disgiunti (union-find)
23. Minimo albero ricoprente (19/05/2011)
    • Algoritmo di Kruskal
    • Implementazione mediante UNION-FIND
24. Teoria della calcolabilità
    • Esistenza di problemi indecidibili
    • Il problema dell'arresto
25. 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
26. 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
27. Teoria della complessità (30/05/2011)
    • 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