84745 - INTRODUZIONE AGLI ALGORITMI

Anno Accademico 2018/2019

  • Docente: Alan Albert Bertossi
  • Crediti formativi: 6
  • SSD: ING-INF/05
  • Lingua di insegnamento: Italiano
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea in Matematica (cod. 8010)

    Valido anche per Laurea in Informatica (cod. 8009)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - conosce gli algoritmi per risolvere problemi computazionali di base su strutture di dati elementari; - conosce le tecniche di base per calcolare il costo computazionale degli algoritmi; - è 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 dare una valutazione circa l'efficienza e la correttezza di un algoritmo.

Contenuti

Progettazione e analisi di algoritmi. Complessita' computazionale. Ordini di grandezza. Equazioni di ricorrenza lineari di ordine costante e con partizione bilanciata. Limitazioni inferiori. Strutture di dati. Vettori, record e matrici. Liste, pile e code. Alberi. Visite di alberi (anticipata, simmetrica, differita, per livelli.) Insiemi. Dizionari. Ricerca binaria e per interpolazione. Tabelle hash. Code con priorita'. Heap. Alberi bilanciati di ricerca. Alberi red-black. MFSET. Grafi. Visite DFS e BFS. Tecniche di progettazione: divide-et-impera, backtrack, greedy, ricerca locale, programmazione dinamica, randomizzazione. Algoritmi di ordinamento: Mergesort, Countingsort, Heapsort, Quicksort, Shellsort. Complessita'. Le classi P ed NP. NP-completezza. Algoritmi pseudo-polinomiali, di approssimazione, branch-&-bound, ed euristici.

Il corso include inoltre un modulo di laboratorio durante il quale si implementano e usano le strutture di dati presentate nel modulo di teoria. Si introdurrà inoltre il paradigma di programmazione Object-Oriented e alcune nozioni base sul linguaggio Java.

Testi/Bibliografia

A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino, 2014.

Metodi didattici

Il corso si svolge nel secondo semestre ed è strutturato in lezioni frontali in aula, comprendenti lezioni ed esrcitazioni. Vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, vengono presentate le principali strutture di dati e i piu' comuni problemi computazionali. Per tali problemi, sono progettati algoritmi risolutivi, evidenziando le varie tecniche di progettazione impiegate. Per gli algoritmi proposti, sono enunciati e talvolta dimostrati teoremi che provano la loro correttezza e la loro complessita' temporale. Successivamente ampio spazio viene dedicato alla risoluzione di esercizi. Si svolgeranno inoltre lezioni di laboratorio in cui gli studenti saranno coinvolti nella progettazione e implementazione delle strutture dati presentate durante il corso.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta finale di 3 ore e la consegna di un progetto.

Il progetto si svolge in gruppo e si discute con il docente, in una data precedente a quella della prova scritta.

Durante la prova scritta non è ammesso l'uso di libri, appunti, calcolatrici, supporti elettronici. La prova scritta consiste di 6 quesiti, alcuni dei quali sono esercizi che mirano ad accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri sono domande aperte che mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso.

Strumenti a supporto della didattica

Videoproiettore.

Orario di ricevimento

Consulta il sito web di Alan Albert Bertossi