Paolo Boldi

Algoritmi e complessità

Indice

  1. Avvisi
  2. Orario
  3. Link per seguire le lezioni da remoto
  4. Appelli
  5. Programma del corso
    1. Contenuti del corso
    2. Note di lezione
  6. Modalità d'esame
  7. Ricevimento studenti

Avvisi

Orario

Le lezioni si svolgeranno con il seguente orario:

Link per seguire le lezioni da remoto

Gli studenti che devono seguire da le lezioni di teoria da remoto sono pregati di autenticarsi usando il loro account Teams d'Ateneo e di collegarsi a questo link. Ricordiamo che lo scopo della trasmissione in streaming è di favorire "[...] la partecipazione degli studenti con particolari fragilità o che risultino immunodepressi, degli studenti non ancora in possesso della certificazione verde covid-19 nonché degli studenti internazionali che in presenza di limitazioni agli spostamenti determinati dall'emergenza epidemiologica tuttora in corso sarebbero impossibilitati a garantire la presenza in aula" (Decreto rettorale sulla didattica del 23 agosto). In tutti gli altri casi, è fortemente consigliata la presenza in aula.

Appelli

L'esame si tiene su appuntamento e consiste in una prova orale. Per poterlo sostenere occorre contattare il docente con sufficiente anticipo.

 Data
Gennaio 2022 (*)  
Gennaio 2022  
Febbraio 2022  
Giugno 2022  
Luglio 2022  
Settembre 2022  

L'appello di Gennaio indicato con (*) è riservato agli studenti degli A/A precedenti.

Programma di massima del corso di Programmazione

Il corso di Algoritmi e complessità è un corso di 6 crediti che costituisce una naturale prosecuzione di un corso di algoritmi di base. L'obiettivo è quello di fornire allo studente una conoscenza di algoritmi avanzati, che richiedono tecniche di progettazione sofisticate e un diverso approccio all'analisi. In particolare, il corso si concentrerà su algoritmi di approssimazione, algoritmi probabilistici e strutture succinte.

Contenuti del corso

Il programma di massima del corso è il seguente:

Programma

Riferimenti bibliografici

Ref
[A] Cap. 11 (escluso 11.7) di Jon Kleinberg, Éva Tardos: Algorithm Design, Pearson, 2013
[B] Dispense di Cornell sull'algoritmo di Christofides
[C] Lucidi di Kevin Wayne
[D] Dispense di Sebastiano Vigna
[E] Lucidi di Stanford sull'algoritmo di Karger
[F] Dispense di Luca Trevisan
[G] Sezione 3.2 di Ausiello et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer 1999
[H] Algoritmo di Miller-Rabin

Note di lezione

Rendo pubblici gli appunti che ho scritto durante le lezioni. Queste note sono finalizzate solamente a consentire agli studenti frequentanti di completare i loro appunti; non hanno ovviamente alcun significato se estrapolati dal contesto della lezione.

Modalità d'esame

L'esame consiste in una prova orale.

Ricevimento studenti

Il docente riceve nel suo studio di via Celoria 18 (quinto piano) o in via telematica, in ogni caso su appuntamento. Un appuntamento può essere fissato inviando una e-mail al docente e attendendo una risposta di conferma.