11929 - ALGORITMI E STRUTTURE DATI (CL.B)

Anno Accademico 2023/2024

  • Moduli: Vittorio Maniezzo (Modulo 1) Moreno Marzolla (Modulo 2)
  • Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
  • Campus: Cesena
  • Corso: Laurea in Ingegneria e scienze informatiche (cod. 8615)

Conoscenze e abilità da conseguire

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

Contenuti

-matematica discreta elementare per calcolare gli ordini di grandezza;

- Algoritmi di ordinamento;

- Mediano e selezione;

- Strutture dati elementari: pile, code, alberi, grafi

- algoritmi di visita su grafi

- algoritmi di base su grafi

-classi P e NP

-problemi NP-Hard

Testi/Bibliografia

T. Cormen, C. Leiserson, R. Rivest. Introduzione agli algoritmi e strutture dati, Mc Graw Hill. 4 ed.

Metodi didattici

Lezioni frontali ed eserciitazioni in aula.

Modalità di verifica e valutazione dell'apprendimento

Esame scritto e orale opzionale aggiuntivo. Progetto.

La verifica si compone di due prove, progetto e scritto (orale opzionale). Il progetto deve essere consegnato e approvato prima dello scritto e non concorre al giudizio finale ma abilita solo all'iscrizione alla prova scritta.

La frequenza alle lezioni è molto consigliata ma non indispensabile.

La prova scritta, della durata di 1.5 h, è composta di tre esercizi, un quiz a scelta multipla e una domanda teorica riferite alla verifica di conoscenze (sapere) e un esercizio riferito alle abilità (saper fare), declinate nel quadro “conoscenze ed abilità da conseguire”.

Non sono ammessi durante le prove strumenti quali ausili di calcolo, vocabolari, codici, ecc.

La partecipazione attiva alle lezioni verrà premiata.

Strumenti a supporto della didattica

Dispense a cura del docente riferite al libro di testo.

Orario di ricevimento

Consulta il sito web di Vittorio Maniezzo

Consulta il sito web di Moreno Marzolla