elenco    
        corso    

Algoritmica B

Codice: AA006Crediti: 9Semestre: 1Sigla: ALG 
 
Settore disciplinare: INF/01 - Informatica

Docente

Linda Pagli   pagli@di.unipi.it  Stanza 277  Tel. 0502212735

Prerequisiti

  1. Conoscenza di un linguaggio di programmazione (Pascal, C, C++ o Java).
  2. Dimestichezza con l'uso dei puntatori e della ricorsione.
  3. Nozioni matematiche: proprietà e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).

Obiettivi di apprendimento

Definire formalmente la nozione di algoritmo e di modello di calcolo.
Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi.
Progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l'esame di diversi paradigmi. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.
Conoscenze. Cosa è un algoritmo e cosa è un modello di calcolo. Saper caratterizzare i dati da elaborare strutturandoli nel modo più opportuno al fine da agevolarne l’uso da parte degli algoritmi. Conoscere le strutture dati e le tecniche fondamentali per il progetto di algoritmi elementari. Conoscere le tecniche di valutazione della complessità di un algoritmo e le limitazioni inerenti dei problemi da risolvere. Conoscere le classi di complessità P, NP, NPC, e le limitazioni del calcolo (indecidibilità).
Capacità. Saper progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l’uso di strutture dati e tecniche algoritmiche elementari. Saper valutare la complessità di un algoritmo in tempo e spazio, al caso pessimo e al caso medio. Saper valutare le limitazioni inerenti del calcolo.
Comportamenti. Lo studente saprà essere in grado di valutare la bontà (leggi efficienza in tempo e spazio) di un software sulla base delle sue caratteristiche progettuali salienti, prescindendo dunque dalla macchina, dal Linguaggio di sviluppo o dal Sistema Operativo sul quale il software gira. Allo stesso modo, lo studente saprà essere in grado di effettuare scelte progettuali ragionevoli nella realizzazione di un software, valutando le loro implicazioni sulla prestazioni dello stesso, prima di arrivare alla fase di programmazione, debugging e profiling, mediante l’uso di modelli matematici opportuni. Ciò risulta cruciale per ridurre i tempi e i costi dello sviluppo del software.

Descrizione

Introduzione ai modelli di calcolo, all'analisi e alla complessità degli algoritmi. Algoritmi ricorsivi e relazioni di ricorrenza. Algoritmi di enumerazione. Strutture di dati elementari e avanzate. Problemi su sequenze, matrici, alberi e grafi. Problemi P, NP, RP, e NP-completi.

English Description

Introduction to the design, analysis and computation complexity of algorithms and data structures. Basic techniques for the analysis of algorithms. Design paradigms for efficient algorithms. Definition and application of main and advanced data structures. Algorithms on graphs and strings. Complexity of computationally hard problem

Indicazioni metodologiche

Per conseguire gli obiettivi indicati, sarà necessario:

Programma

  1. Problemi computazionali
    1. Indecidibilità
    2. Trattabilità
    3. Complessità computazionale: limiti superiori e inferiori.
  2. Sequenze: array
    1. Ricerca di una chiave
    2. Problemi risolti ricorsivamente ("divide et impera")
    3. Problemi risolti per programmazione dinamica
  3. Sequenze: liste
  4. Alberi
    1. Alberi binari
    2. Visite
  5. Grafi
    1. Rappresentazione
    2. Algoritmi di ricerca e cammini in un grafo
  6. Pile e code
    1. Rappresentazione
    2. Applicazioni a diversi problemi
    3. Code con priorità: Heap e ordinamenti
  7. Dizionari
    1. Alberi AVL e B-alberi
    2. Tabelle hash
    3. Trie
  8. NP-completezza
    1. Le classi P, NP, NPC
    2. Riduzioni polinomiali
    3. Algoritmi di approssimazione
Ore lezione: 36Ore esercitazione: 36   

Bibliografia

P.Crescenzi, G.Gambosi, R.Grossi. Strutture di dati e algoritmi. Pearson-Addison Wesley 2006.

Modalità di esame

L’esame di Algoritmica consiste di una prova scritta e di una prova orale. Durante la prova scritta gli studenti non possono consultare i propri libri e appunti. L'esame scritto dunque consiste di esercizi e domande teoriche. Durante il corso vengono svolte due verifiche intermedie (compitini). Gli studenti che superano entrambe le verifiche, con una votazione superiore al 18, possono sostenere la prova orale in uno dei due appelli della sessione invernale (Gennaio o Febbraio). Chi avesse riportato la sufficienza in un compitino soltanto potrà recuperare la parte insufficiente in uno degli appelli della sessione invernale. In questi appelli la prova scritta sarà composta da due parti così da consentire il recupero suddetto. Il recupero può essere anche tentato da chi desidera migliorare il voto riportato in un compitino.

Ulteriore pagina web del corso: http://www.cli.di.unipi.it/doku/doku.php/alg-b/start


home


email