Tu sei qui

Algoritmi e strutture dati

Algoritmi e Strutture Dati
Corso di Laurea Triennale in Informatica F004

SCV0017
Docente: Paolo Massazza


CFU SSD LEZIONI ANNO LINGUA
9 INF/01 72 I Italiano


Obiettivi dell’insegnamento e risultati di apprendimento attesi
Conoscenza e capacità di comprensione
Il corso fornisce le conoscenze di base relative alle principali strutture dati e ai principali algoritmi associati. Vengono acquisite le tecniche di base per la progettazione e l'analisi degli algoritmi, insieme alla capacità di sviluppare programmi software per i più classici problemi legati all’elaborazione dei dati
Conoscenza e capacità di comprensione applicate
Acquisizione delle capacità di trasferimento delle conoscenze dagli ambiti teorici e metodologici a quelli più generalmente professionali, con possibilità di operare e di affrontare problematiche applicative inerenti alle specifiche tematiche studiate.
Autonomia di giudizio e abilità comunicative
I risultati di apprendimento attesi comprendono la capacità di saper individuare gli algoritmi e le strutture dati di base più indicate in un dato contesto, acquisendo al tempo stesso una proprietà di linguaggio tale da poter formalizzare un problema in modo idoneo a una sua trattazione informatica.
Capacità di apprendere
La conoscenza delle tecniche di base inerenti il mondo degli algoritmi e delle strutture di dati permette l’acquisizione di adeguate capacità per l'approfondimento delle proprie conoscenze e per lo sviluppo individuale di nuove competenze.
Prerequisiti
Prerequisiti
Viene richiesta la conoscenza di un linguaggio di programmazione di tipo procedurale, meglio se corredata da elementi di base relativi all’architettura di un elaboratore.

Contenuti e programma del corso

  • Formalizzazione dei problemi, complessità degli algoritmi, notazioni asintotiche (6h))
  • Modelli di calcolo (RAM, RASP) e criteri di costo (6h)
  • Caratteristiche dei linguaggi procedurali (2h)
  • Strutture dati elementari (vettori, matrici, liste, pile, code) (6h)
  • Grafi e alberi, rappresentazioni e algoritmi di visita (10h)
  • Il problema dell’ordinamento: aspetti generali e algoritmi elementari (4h).
  • Tecnica di progettazione Divide et Impera (2h)
  • Ordinamento digitale e algoritmi d’ordinamento avanzati (6h)
  • Heap e Heapsort (2h)
  • Tabelle hash (4h)
  • Alberi binari di ricerca (6h)
  • Alberi bilanciati (2-3, 2-3-4, red-black) (8h)
  • Operazioni su partizioni (Union e Find) (2h)
  • Problemi di ottimizzazione (4h)
  • Programmazione dinamica (4h)

Tipologia delle attività didattiche
Lezioni frontali (72h)

Testi e materiale didattico
A scelta tra:

  • R. Sedgewick, Algoritmi in Java (3ed.), Pearson Education Italia.
  • R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional 2011

in aggiunta a dispense e slide disponibili sul sito di e-learning.

Modalità di verifica dell’apprendimento
L’esame consiste in una prova scritta a cui fa seguito una prova orale. Durante il corso sono previste due prove parziali il cui superamento comporta l’esonero dalla prova scritta. Lo scritto, della durata di 2 ore, prevede una serie di 5-6 quesiti relativi agli argomenti trattati a lezione. L’esito positivo (valutato in trentesimi) della prova scritta permette sia una verbalizzazione diretta sia l’accesso alla successiva prova orale, consistente in 2 fasi:

  • una revisione della prova scritta in cui l’allievo viene informato sui criteri di correzione e chiamato a fornire eventuali precisazioni, permettendo così al docente di modificare eventualmente il giudizio
  • un colloquio d’approfondimento con il docente, volto ad accertare l’acquisizione e la corretta comprensione dei diversi contenuti del corso.

Una brillante prova orale può bilanciare una prova scritta poco convincente e permettere il raggiungimento di una valutazione complessiva (in trentesimi) di assoluto livello.

Orario di ricevimento
Il docente è a disposizione per il ricevimento studenti direttamente in aula al termine di ciascuna lezione, o su appuntamento in dipartimento (da concordare tramite posta elettronica).

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer