11929 - ALGORITMI E STRUTTURE DATI

Anno Accademico 2021/2022

  • Docente: Lorenzo Donatiello
  • Crediti formativi: 12
  • SSD: INF/01
  • Lingua di insegnamento: Italiano
  • Moduli: Lorenzo Donatiello (Modulo 1) Jocelyne Elias (Modulo 2)
  • Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
  • Campus: Bologna
  • Corso: Laurea in Informatica per il management (cod. 8014)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - conosce gli algoritmi per risolvere problemi computazionali di base su strutture dati elementari; - conosce le tecniche di base per calcolare il costo computazionale degli algoritmi; - conosce le classi di complessità computazionale P, NP e NP-hard; - è in grado di progettare algoritmi efficienti per risolvere semplici problemi computazionali; - è in grado di stimare in ordine di grandezza il costo computazionale degli algoritmi; - è in grado di analizzare la complessità computazionale di problemi computazionali di base; - è in grado di dare una valutazione circa l'efficienza e la correttezza di un algoritmo; - è capace di elaborare e di presentare un progetto per la risoluzione di problemi computazionali di base.

Contenuti

Strutture dati elementari (Liste, Pile, Code, Alberi...)
Costo asintotico degli algoritmi, 

Algoritmi di ordinamento, selezione e ricerca

Insiemi, Dizionari,

Alberi binari di ricerca, alberi RB,
Tabelle Hash,  Code di priorità
Strutture union-find
Tecniche Algoritmiche: divide et impera, algoritmi greedy, programmazione dinamica
Grafi e visite di grafi: visita in ampiezza e profondità
Algoritmi elementari su grafi, cammini minimi
Cenni alla teoria della NP-completezza

Testi/Bibliografia

Testi adottati
Alan A. Bertossi, A. Montresor,Algoritmi e Strutture di Dati, CittàStudi 2010, ISBN: 9788825173567

Altri testi consigliati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano,Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687
Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano,Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill, 2005, ISBN: 9788838662515

Metodi didattici

Lezioni frontali con utilizzo di lucidi, esercitazioni, progetti di laboratorio


Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso lo svolgimento di un progetto e di una prova orale. Il progetto mira ad accertare le abilità acquisite nel risolvere problemi computazionali  tramite la progettazione e implementazione di algoritmi efficienti, e a verificare l'acquisizione delle conoscenze previste dal programma del corso. 

La valutazione dei progetti  deve risultare almeno sufficiente ( i.e., deve ottenere una valutazione ≥ 18/30) per essere valida ai fini dell'esame.  La prova orale, anch'essa valutata in trentesimi, consiste essenzialmente nella discussione dei risultati ottenuti nei progetti e mira a verificare l'acquisizione, da parte dello studente, delle conoscenze previste dal programma del corso.

 Il voto finale, espresso in trentesimi, tiene conto delle valutazione ottenente nei progetti e nella prova orale.


Strumenti a supporto della didattica

Il materiale didattico (lucidi delle lezioni, esercizi svolti, altre risorse utili) si trovano nella pagina web del corso.

Link ad altre eventuali informazioni

http://www.cs.unibo.it/~donat/

Orario di ricevimento

Consulta il sito web di Lorenzo Donatiello

Consulta il sito web di Jocelyne Elias

SDGs

Istruzione di qualità

L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.