11929 - ALGORITMI E STRUTTURE DATI

Anno Accademico 2024/2025

  • Docente: Jocelyne Elias
  • Crediti formativi: 12
  • SSD: INF/01
  • Lingua di insegnamento: Italiano
  • Moduli: Davide Rossi (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, Minimum Spanning Tree, cammini minimi,

Cenni alla teoria della NP-completezza

Testi/Bibliografia

Testi adottati:

Alan A. Bertossi, A. Montresor, Algoritmi e Strutture di Dati [http://www.utetuniversita.it/bertossi], CittàStudi 2010, ISBN: 9788825173567

Altri testi consigliati:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed [http://www.ateneonline.it/demetrescu2e/homeA.asp], 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 [http://www.ateneonline.it/demetrescu/homeB.asp], McGraw-Hill, 2007, ISBN: 9788838663741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,Introduzione agli algoritmi e strutture dati 2/ed [http://www.ateneonline.it/cormen/], McGraw-Hill, 2005, ISBN: 9788838662515

Metodi didattici

Lezioni frontali e esercitazioni

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 valutazioni ottenute nei progetti e nella prova orale.

Strumenti a supporto della didattica

Le lezioni frontali prevedono l'uso di lucidi proiettati da un laptop e una lavagna tradizionale, articoli scientifici segnalati agli studenti etc. Il materiale didattico presentato a lezione verrà messo a disposizione dello studente in formato elettronico tramite internet.

Orario di ricevimento

Consulta il sito web di Jocelyne Elias

Consulta il sito web di Davide Rossi