DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Algoritmi e Strutture dei Dati: A.A. 2022-2023 ======

Prof. Roberto Grossi\\
Dott. Federico Lazzeri (supporto)\\
Dott. Alberto L'Episcopo (supporto)

{{:matematica:asd:asd_14:asd_logo.jpg?200|}}

==== Avvisi ====

  * **Importante: iscrizione all'esame** Ho pubblicato sul sito [[https://esami.unipi.it/]] delle date per l'iscrizione all'esame, che è obbligatoria perché così potete compilare il questionario; è sufficiente iscriversi una volta. La data effettiva dell'orale e/o discussione del progetto è concordata insieme al docente, com'è sempre stato fatto negli anni scorsi.
  * Sono disponibili il [[progetto_21|[progetto]]] e i lucidi (su Teams).   
  * Inizio ufficiale delle lezioni: lun 27.2.2023.
  * Orario lezioni (aggiornato): **lun 16:30-18:00 (4-Lab), mer 14:00-16:00 (Fib-E1), ven 9-11 (Fib-L)**.
  * Didattica erogata in presenza in aula Fib-E1, Fib-L e in modalità mista (Teams+Replit) nel laboratorio 4-Lab.
  * Si prega di iscriversi sia al[[https://teams.microsoft.com/l/team/19%3aBBD6r6UG7xiuo_RKxYBuqZD0JI0TB0HkpahWwt6m9mA1%40thread.tacv2/conversations?groupId=2046c15b-f394-4522-832f-36ee9f2b8d91&tenantId=c7456b31-a220-47f5-be52-473828670aa1|canale Teams]] che nell'[[https://agendadidattica.unipi.it/|agenda didattica]].
  * Pre-corso //facoltativo// su C++: lun 20.2 ore 16:30-18 (M-lab), mer 22.2 ore 14-16 (M-lab), ven 24.2 ore 9-11 (M-lab). Consigliato il proprio laptop, se possibile.
  * Per il ricevimento, su appuntamento in modalità telematica.

==== Motivazioni ====

//"Fino a poco tempo fa, i matematici teorici consideravano un problema risolto se esisteva un metodo conosciuto, o algoritmo, per risolverlo; il procedimento di esecuzione dell'algoritmo era di importanza secondaria.
Tuttavia, c'è una grande differenza tra il sapere che è possibile fare qualcosa e il farlo. Questo atteggiamento di indifferenza sta cambiando rapidamente, grazie ai progressi della tecnologia del computer. Adesso, è importantissimo trovare metodi di soluzione che siano pratici per il calcolo.
La teoria della complessità studia i vari algoritmi e la loro relativa effficienza computazionale. Si tratta di una teoria giovane e in pieno sviluppo, che sta motivando nuove direzioni nella matematica e nello stesso tempo trova applicazioni concrete quali quello fondamentale della sicurezza e identificazione dei dati."//

-- E. Bombieri, Medaglia Fields, in //La matematica nella società di oggi//, Bollettino UMI, Aprile 2001

==== Contenuti ====

Introduzione al modello di calcolo, all'analisi e alla complessità degli algoritmi. Algoritmi ricorsivi e relazioni di ricorrenza: divide et impera e programmazione dinamica. Strutture di dati combinatorie con applicazioni: algoritmi per array, liste, alberi, pile, code, code di priorità, dizionari, grafi. Problemi P, NP, NP-completi e approssimazione.

==== Obiettivi formativi ====

Definire formalmente le nozioni di algoritmo e di modello di calcolo caratterizzandone gli aspetti rilevanti. Organizzare e strutturare i dati da elaborare 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 paradigmi diversi e problemi provenienti dal mondo reale. Studiare le limitazioni inerenti dei problemi da risolvere, in particolare di quelli la cui soluzione richiede l'esame di tutte le possibilità.

==== Prerequisiti e metodologia ====

  * Conoscenza di un linguaggio di programmazione (C, C++, C#, Java, Phyton).
  * Lezioni frontali con esercitazioni.
  * Sviluppo di codice in laboratorio.
  * Uso di strumenti di visualizzazione.
  * Sviluppo di un progetto basato su "real-world data".


==== Modalità d'esame ====

  * Parte prima, a scelta una delle seguenti possibilità:
    * [[progetto_21|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
    * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un mini-progetto con votazione booleana (prova superata o meno per valutare le capacità programmative);
    * seminario basato su un argomento di ricerca nel campo dell'algoritmica, avente una votazione in trentesimi, più un mini-progetto con votazione booleana (vedi sopra);
  * Parte seconda, comune per tutti: verifica tramite l'orale basato sul programma dettagliato (vedi sotto).

**Nota: la discussione del progetto e l'orale posso essere svolti indipendentemente, senza un ordine o un vincolo temporale particolare tra di loro.
**
==== Testi e materiale didattico ====

  * P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di Dati e Algoritmi, Pearson, seconda edizione, 2012 [CGGR].
     * [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|Capitolo 0, solo versione elettronica]], [[http://tinyurl.com/d9ajvky|Errata-corrige]],[[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|Sito Web]]
  * T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
  * C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.


==== Programma ====

//Programma d'esame:// [[https://esami.unipi.it/programma.php?c=53655&aa=2022&cid=9&did=20|pagina ufficiale]]

Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (più [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (par.5.1, 5.2, 5.3), Capitolo 6 (par. 6.1, 6.3, 6.4, 6.5, 6.8), Capitolo 7 (tranne par. 7.3.2), Capitolo 8 (tranne par. 8.7). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]]. 


Per la lista dettagliata, consultare il [[https://unimap.unipi.it/registri/printregistriNEW.php?re=7084481::::&ri=9172|registro delle lezioni]].