Strumenti Utente

Strumenti Sito


informaticaapplicata:all:start

Algoritmica e Laboratorio

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

News

Testo e soluzioni Appello del 5/9/2011

Risultati IV appello
465312 ins(16)

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

Informazioni Generali

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:00Polo G. Marconi
Giovedì 10:00-11:00Polo 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
  • 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).

Contenuti del Corso

  • Problemi Computazionali
  • Array e liste
  • Alberi e grafi
  • Dizionari
  • Pile e code
  • NP-completezza

Registro delle lezioni

  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)
  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. 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
  18. Stringhe
    • Definizioni
    • Distanza fra 2 stringhe
    • Massima sottosequenza comune
  19. Programmazione dinamica: approfondimenti (09/05/2011)
    • Ricostruzione delle soluzioni
    • Algoritmo di programmazione dinamica per il problema dello zaino
    • Algoritmi pseudo-polinomiali
    • 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
  20. Minimo albero ricoprente (19/05/2011)
    • Algoritmo di Kruskal
    • Implementazione mediante UNION-FIND
    • Esistenza di problemi indecidibili
    • Il problema dell'arresto
  21. 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
  22. 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
informaticaapplicata/all/start.txt · Ultima modifica: 12/09/2011 alle 11:49 (13 anni fa) da anna bernasconi