DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Algoritmica e Laboratorio ======

Corso tenuto presso il Polo Universitario "G. Marconi" di La Spezia, Corso di Laurea in Informatica Applicata.
====== News ======


Testo e soluzioni {{:informaticaapplicata:all:2011-09-05-AppelloIVSOL.pdf|Appello del 5/9/2011}}
 

^           Risultati IV appello        ^^


| 465312  | ins(16) |       



Qui trovate vecchi compiti, con relative soluzioni: {{:informaticaapplicata:all:scritti.zip|Testi e alcune soluzioni compiti scritti AA2009-10}}

====== Informazioni Generali ======
**Docenti:** [[http://www.di.unipi.it/~annab|Anna Bernasconi]] [[http://sbrinz.di.unipi.it|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

  * 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 [[http://www.minigw.org|MiniGW]]. Su sistemi MAC, è necessario installare gli //Xcode Tools//, presenti nel CD/DVD di installazione della macchina.

Come editor, potete utilizzare [[http://www.jedit.org/|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
        * Rappresentazioni indicizzate
        * Rappresentazioni collegate
        * Visite di 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:
        * Struttura generale di un programma C
        * Sintassi di:
               * Dichiarazione variabili
               * Array
               * Dichiarazione e invocazione di funzioni
  - Quicksort: Analisi di complessità nel caso medio del Quicksort (**__31/03/2011__**)
  - Altri tipi di ordinamento
        * Integer sort, Bucket sort, Radix sort 
  - Selezione del k-esimo elemento 
        * Soluzione con k piccolo
            * Algoritmo semplice e algoritmo del torneo 
        * Heapselect
        * Quickselect
        * Mediano dei mediani
  - Esercitazione (**__04/04/2011__**)
        * Progettazione di algoritmi efficienti e analisi della loro complessita`
        * {{:informaticaapplicata:all:alberi.pdf|Algoritmi ricorsivi su alberi}}
  - Alberi di ricerca (**__07/04/2011__**)
        * Alberi binari di ricerca
        * Alberi AVL ({{:informaticaapplicata:all:rotazioni.pdf|rotazioni}})
        * 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 ({{:informaticaapplicata:all:fibonacci1.zip|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__**)
  - {{:informaticaapplicata:all:listeinvertite.pdf|Liste invertite}}  (**__28/04/2011__**)
  - {{:informaticaapplicata:all:trie.pdf|Trie, trie compatti, suffix tree}} 
  - 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
  - Stringhe
        * Definizioni
        * Distanza fra 2 stringhe
        * Massima sottosequenza comune 
  -  Programmazione dinamica: approfondimenti (**__09/05/2011__**) 
        * Ricostruzione delle soluzioni
        * Algoritmo di programmazione dinamica per il {{:informaticaapplicata:all:Invio_do.pdf|problema dello zaino}}
        * Algoritmi pseudo-polinomiali
  - {{:informaticaapplicata:all:grafi.pdf|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
  - {{:informaticaapplicata:all:UnionFind.pdf|Liste per insiemi disgiunti (union-find)}}  
  - Minimo albero ricoprente (**__19/05/2011__**) 
        * Algoritmo di Kruskal
        * Implementazione mediante UNION-FIND
  - {{:informaticaapplicata:all:Calc.pdf|Teoria della calcolabilità}} 
        * Esistenza di problemi indecidibili
        * Il problema dell'arresto
  - Laboratorio C n. 3 (**__23/05/2011__**) Programmi da sviluppare in C per il 23 Maggio ({{:informaticaapplicata:all:stringhe.zip|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
  - {{:informaticaapplicata:all:PNP.pdf|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