Nuova ricerca

Manuela MONTANGERO

Professore Associato
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

Insegnamento: Algoritmi e strutture dati

Matematica (Offerta formativa 2024)

Obiettivi formativi

Lo scopo dell'insegnamento è quello di introdurre lo studente alle principali metodologie di progettazione e le tecniche algoritmiche di base. Tale introduzione viene fatta seguendo gli argomenti classici di un corso introduttivo di algoritmica, e cioè le strutture dati di base e alcune strutture dati più evolute, algoritmi numerici e di ordinamento, algoritmi di base sulle stringhe, gli algoritmi fondamentali su grafo e le principali tecniche algoritmiche (ricorsione e divide-et-impera, greedy, programmazione dinamica).

Lo studente sarà portato ad apprezzare l'importanza di una fase progettuale in cui vengano considerate la correttezza e l'efficienza degli algoritmi in termini di consumo spazio-tempo. Al riguardo, verranno introdotte le nozioni di complessità asintotica, con particolare accento sul caso più sfavorevole.

Prerequisiti

Lo studio teorico/pratico degli algoritmi richiede un certo grado di maturità matematica e di calcolo. Sono propedeutici, e ne costituiscono prerequisito formale, una parte dell'insegnamento di Analisi matematica (ben definito nel corso) e l'insegnamento di Programmazione I.

Programma del corso

Il corso si tiene al secondo semestre del primo anno del corso di studi triennale di Informatica, per un totale di 72 ore (9 CFU) di lezioni frontali teoriche.

I contenuti del corso sono i seguenti (le ore sono indicative, potrebbero cambiare a seconda della risposta degli studenti in aula):

- Concetti di base (8 ore): Algoritmo, analisi di algoritmi, bit- vs word-complexity, analisi worst-case, comportamento asintotico degli algoritmi.
- Ricorsione (6 ore): funzioni matematiche ricorsive, ricerca binaria, ricorrenze, Master-theorem.
- Strutture dati (12 ore): Pile e Code, alberi, Heap, grafi, insiemi, dizionari e tabelle hash.
- Tecnica divide-et-impera e ricerca binaria (3 ore).
- Algoritmi di ordinamento (9 ore): mergesort, quicksort, Insertionsort, countingsort, selectionsort.
- Algoritmi greedy (8 ore): Tecnica greedy. Codifiche Huffman. Copertura di insiemi. Minimo albero di copertura.
- Algoritmi su grafi (14 ore): Esplorazione di grafi. Algoritmo di esplorazione in profondità (depth-first search) e in ampiezza (breadth-first-search). Ordinamento topologico di grafi diretti aciclici. Componenti fortemente connesse. Ricerca di cicli in grafi. Ricerca di cammini minimi.
- Programmazione dinamica (8 ore): Algoritmo di Bellman-Ford. Cammini minimi in grafi aciclici e cammini minimi per ogni coppia di nodi. Sottosequenza più lunga di numeri ordinati in senso crescente. Problema dello zaino. Moltiplicazione iterata di matrici.
- Algoritmi di ricerca all'interno di stringhe (4 ore): Algoritmo a forza-bruta. Algoritmo di Knuth-Morris-Pratt.



Metodi didattici

Il corso prevede lezioni frontali sugli aspetti teorici ed esercitazioni sugli argomenti affrontati nella parte teorica. Nel caso di disponibilità, il corso si avvarrà dell'aiuto di un tutor (studente di dottorato o magistrale) che si occuperà di esercitazioni che si terranno in ore extra rispetto a quelle delle lezioni, aperte a tutti gli studenti del corso, e che sarà a disposizione per ricevimenti individuali. L'orario delle esercitazioni sarà scelto in modo da non sovrapporsi con altre lezioni del primo anno del corso di studi.

Durante il corso e le esercitazioni, le domande e gli interventi degli studenti sono graditi e incoraggiati.

La frequenza non è obbligatoria, ma caldamente consigliata.

Il corso è erogato in lingua italiana, così come la maggior parte del materiale fornito dal docente, ammettendo qualche eccezione in cui li materiale potrebbe essere in inglese.

Tutte le informazioni, sia pratiche che organizzative, così come il materiale didattico, sarà reso disponibile con regolarità durante lo svolgimento del corso sulla pagina moodle del corso.

Il materiale didattico fornito dal docente consiste in:
- lucidi del docente sugli argomenti trattati a lezione
- dispense scritte in toto o in parte dal docente, su argomenti selezionati del corso
- dispense scritte da altri docenti universitari, su argomenti selezionati del corso
- Esercizi propedeutici alla due parti dell'esame scritto, con soluzioni
- Vecchie tracce d'esame con soluzioni ragionate
- Brevi video (dette pillole) a supporto e integrazione di alcuni argomenti visiti a lezione
- Video con esempi di soluzione degli esercizi della prima parte dello scritto
- Indicazioni su dove trovare gli argomenti trattati a lezione sui libri di testo adottati

Durante il corso saranno erogate esclusivamente lezioni frontali con l'utilizzo di lavagna (prevalentemente) e lucidi (sporadicamente).

Testi di riferimento

Oltre al materiale fornito dal docente, (non in alternativa al testo, ma a complemento) un testo in alternativa tra:

1) Algoritmi e Strutture Dati 2a ED
Materiali per l'insegnamento
McGraw-Hill - Create
ISBN: 9781307961546

oppure

Materiali per l'insegnamento di Algoritmi e Strutture Dati,
a cura di Manuela Montangero
McGraw-Hill - Create
ISBN: 978-13-076-6722-6

questo testo contiene principalmente una selezione di capitoli di:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI - Terza Edizione
McGraw-Hill

I capitoli selezionati sono quelli relativi ad argomenti trattati nel corso.

2) A. Bertossi, A. Montresor,
"Algortimi e Strutture Dati",
Città Studi


Verifica dell'apprendimento

L'esame del corso prevede una prova scritta ed un orale facoltativo.

La prova scritta è divisa in due parti. La prima parte è volta a verificare la padronanza teorica ed operativa degli argomenti presentati a lezione. In essa viene chiesto di indicare il risultato prodotto da un algoritmo su dati assegnati, scegliendo una selezione tra quelli visti a lezione.
La seconda parte consiste nella risoluzione di problemi di media complessità simile a (ma non coincidente con) un problema visto a lezione. La seconda parte è volta a verificare la capacità degli studenti di rielaborare le conoscenze e le tecniche acquisite per approcciare in autonomia problemi nuovi e descriverne soluzioni a parole e mediate pseudo-codice. La seconda parte prevede una anche una domanda teorica in cui può venire richiesto di enunciare e/o dimostrare un teorema visto a lezione, di studiare il costo computazionale di un algoritmo, ecc.

L'esame verrà svolto in esclusivamente in presenza.

Gli studenti non potranno consultare nessun tipo di materiale durante le prove (sia scritta che orale).

Sia per la prima che la seconda parte vengono stabilite delle soglie per essere superate. Gli esercizi della prima parte
vengono considerati corretti solo se il risultato è esatto e hanno tutti lo stesso punteggio. La soglia prevede che almeno la metà degli esercizi della prima parte sia stato risolto correttamente. Gli esercizi della seconda parte possono avere punteggi massimi leggermente diversi a seconda della loro difficoltà. Esercizi con ragionamenti corretti, ma con errori minori, di implementazione, o incompleti vengono valutati con un punteggio intermedio tra zero e il massimo, a seconda della gravità delle mancanze. La domanda teorica ha un punteggio massimo che è intermedio tra quello di un esercizio della prima parte e uno della seconda. Risposte parziali o con errori minori vengono valutate con un punteggio compreso tra lo zero e il punteggio massimo, a seconda della gravità delle mancanze. La soglia di superamento richiede che almeno un esercizio sia stato risolto correttamente o con errori minori.

In caso di superamento delle soglie, i punteggi delle due parti vengono sommati per ottenere il voto finale della prova d'esame. L'esito finale dello scritto viene reso noto agli studenti al termine della correzione di tutti gli elaborati, attraverso la pubblicazione dei voti su esse3. Gli studenti avranno la possibilità di discutere il compito con il docente nei giorni successivi alla pubblicazione dei voti.

La possibilità di sostenere l'esame orale (della durata di circa 20 minuti), facoltativa e su richiesta dello studente, è vincolata al superamento della prova scritta. Durante la prova orale allo studente verrà chiesto di riportare e ragionare sugli algoritmi e risultati visti a lezione, oppure ragionare e risolvere un esercizio tipo seconda parte dell'esame scritto.

La prova orale può contribuire con un punteggio sia positivo che negativo rispetto al voto della prova scritta a seconda di quanto soddisfacenti siano le risposte dello studente nel mostrare di aver appreso e assimilato i concetti proposti a lezione, saperci ragionare sopra, e riuscire a comunicare il risultato dei suoi ragionamenti. Il voto finale verrà comunicato allo studente al termine della prova, con conseguente aggiornamento del voto su esse3.




Risultati attesi

- Conoscenza e comprensione
Gli studenti avranno solide conoscenze e capacità di comprensione delle principali tecniche di progetto di algoritmi e strutture dati e delle problematiche collegate allo studio della complessità dei problemi e della efficienza algoritmica.

- Capacità di applicare conoscenza e comprensione.
Lo studente sarà portato a sviluppare autonome capacità di applicazione delle conoscenze acquisite riconducibili a: (1) descrizione formale di problemi computazionali; (2) individuazione del "nocciolo" algoritmico di soluzione; (3) analisi di complessità della soluzione individuata

- Autonomia di giudizio
Lo studente avrà una buona capacità di reperire dati e informazioni utili allo svolgimento del proprio lavoro, particolarmente in relazione alla formalizzazione di problemi e alla scelta e messa a punto di strategie algoritmiche efficienti per la loro risoluzione. Sarà in grado di fornire giudizi autonomi sulle scelte operate e di valutare criticamente i risultati ottenuti, anche in funzione di tali scelte.

- Abilità comunicative
Nel contesto della risoluzione algoritmica di problemi computazionali, lo studente sarà in grado, utilizzando argomenti quantitativi e un linguaggio tecnico appropriato, di dare ragione delle varie opzioni progettuali, evidenziandone vantaggi e svantaggi in termini di efficienza. Avrà capacità di leggere con profitto la letteratura tecnica in lingua inglese su argomenti di algoritmica.

- Capacità di apprendimento
Questo insegnamento aiuterà lo studente a maturare ed affinare capacità di apprendimento continuo e autonomo, indispensabili per stare al passo di una disciplina tecnica in continua e rapida evoluzione.