ID:
3332
Durata (ore):
48
CFU:
6
Url:
MATEMATICA/PERCORSO COMUNE Anno: 3
Anno:
2023
Dati Generali
Periodo Di Attività
Secondo Semestre (26/02/2024 - 31/05/2024)
Syllabus
Obiettivi Formativi
I principali obiettivi del corso sono: analizzare le principali tecniche di progettazione degli algoritmi, classificare, analizzare, progettare ed implementare algoritmi, valutare i costi in termini di efficienza computazionale, giungere al miglior compromesso tra esigenze conflittuali (costo, semplicità, efficienza).
Prerequisiti
Matematica di base (algebra di base, concetto di funzione). Programmazione procedurale.
Metodi Didattici
Lezioni teoriche ed esercitazioni con l'implementazione di alcuni algoritmi in linguaggi di programmazione di alto livello (C, Python).
Verifica Apprendimento
L'esame orale prevede l'analisi e l'implementazione (in C o Python) di algoritmi trattati nel corso.
Testi
1) F. Oliveri. Algoritmi e Programmazione in C. Aracne, 2008.
2) M. T. Goodrich, R. Tamassia, M. H. Goldwasser. Data structures and algorithms in Python. Wiley, 2013.
2) M. T. Goodrich, R. Tamassia, M. H. Goldwasser. Data structures and algorithms in Python. Wiley, 2013.
Contenuti
Definizione di algoritmo. Proprietà di un algoritmo.
Costo computazionale di un algoritmo. Modello RAM. Notazione asintotica. Notazione asintotica per equazioni. Proprietà dei simboli della notazione asintotica. Complessità di un algoritmo. Istruzione dominante. Complessità di un problema. Strategie di sviluppo degli algoritmi. Stima di sommatorie. Stima mediante integrali. Ricorrenze. Risoluzione per iterazione. Risoluzione con il metodo master.
Algoritmi elementari.
Potenza n–esima. Numeri di Fibonacci. Generazione di numeri casuali. Il metodo della congruenza lineare. Il metodo della congruenza quadratica.
Strutture astratte di dati.
Rappresentazione di dati astratti. Vettori e record. Matrici. Matrici compatte. Liste. Liste semplici. Liste composite. Alberi binari di ricerca. Alberi n–ari. Visita di un albero. Grafi. Rappresentazione dei grafi. Attraversamento di un grafo.
Minimo e massimo di un array. Partizione di un array. k-esimo minimo di un array. Fusione di due array ordinati.
Eliminazione doppioni da un array ordinato. Ordinamento per selezione diretta (selectionsort). Ordinamento per inserimento (insertionsort). Ordinamento per interscambio (bubblesort). Ordinamento di Shell.
Quicksort. Mergesort, Heapsort. Complessità degli algoritmi di ordinamento basati sui confronti. Ricerca di un elemento in un array. Ricerca sequenziale. Ricerca binaria. Ricerca di Fibonacci. Ricerca interpolata. Ricerca adattativa. Ricerca calcolata.
Pile, code, liste ordinate.
Ordinamento di array in tempo lineare. Un caso semplice: ordinamento per permutazione. Ordinamento per conteggio (countingsort). Bucketsort.
Ricerca su stringhe. L’algoritmo diretto (ingenuo). L’algoritmo di Knuth–Morris–Pratt. L’algoritmo di Boyer-Moore. L’algoritmo di Karp–Rabin.
Alberi binari di ricerca. Minimo, massimo, predecessore, successore. Ricerca in un albero binario ordinato.
Inserimento di un nodo in un albero binario ordinato.
Rimozione di un nodo da un albero binario ordinato.
Visita di un albero binario ordinato.
Alberi RB e AVL.
Proprietà degli alberi RB. Rotazioni in un albero RB. Inserimento di un nodo in un albero RB. Rimozione di un nodo da un albero RB. Alberi AVL. Rotazioni in un albero AVL. Inserimento di un nodo in un albero AVL. Rimozione di un nodo da un albero AVL.
Grafi. Rappresentazione di un grafo con la matrice di adiacenza. Rappresentazione di un grafo con le liste di adiacenza. Visita in ampiezza. Cammini minimi. Visita in profondità. Connettività di un grafo. Componenti connesse. Duplice connettività. Componenti fortemente connesse.
Costo computazionale di un algoritmo. Modello RAM. Notazione asintotica. Notazione asintotica per equazioni. Proprietà dei simboli della notazione asintotica. Complessità di un algoritmo. Istruzione dominante. Complessità di un problema. Strategie di sviluppo degli algoritmi. Stima di sommatorie. Stima mediante integrali. Ricorrenze. Risoluzione per iterazione. Risoluzione con il metodo master.
Algoritmi elementari.
Potenza n–esima. Numeri di Fibonacci. Generazione di numeri casuali. Il metodo della congruenza lineare. Il metodo della congruenza quadratica.
Strutture astratte di dati.
Rappresentazione di dati astratti. Vettori e record. Matrici. Matrici compatte. Liste. Liste semplici. Liste composite. Alberi binari di ricerca. Alberi n–ari. Visita di un albero. Grafi. Rappresentazione dei grafi. Attraversamento di un grafo.
Minimo e massimo di un array. Partizione di un array. k-esimo minimo di un array. Fusione di due array ordinati.
Eliminazione doppioni da un array ordinato. Ordinamento per selezione diretta (selectionsort). Ordinamento per inserimento (insertionsort). Ordinamento per interscambio (bubblesort). Ordinamento di Shell.
Quicksort. Mergesort, Heapsort. Complessità degli algoritmi di ordinamento basati sui confronti. Ricerca di un elemento in un array. Ricerca sequenziale. Ricerca binaria. Ricerca di Fibonacci. Ricerca interpolata. Ricerca adattativa. Ricerca calcolata.
Pile, code, liste ordinate.
Ordinamento di array in tempo lineare. Un caso semplice: ordinamento per permutazione. Ordinamento per conteggio (countingsort). Bucketsort.
Ricerca su stringhe. L’algoritmo diretto (ingenuo). L’algoritmo di Knuth–Morris–Pratt. L’algoritmo di Boyer-Moore. L’algoritmo di Karp–Rabin.
Alberi binari di ricerca. Minimo, massimo, predecessore, successore. Ricerca in un albero binario ordinato.
Inserimento di un nodo in un albero binario ordinato.
Rimozione di un nodo da un albero binario ordinato.
Visita di un albero binario ordinato.
Alberi RB e AVL.
Proprietà degli alberi RB. Rotazioni in un albero RB. Inserimento di un nodo in un albero RB. Rimozione di un nodo da un albero RB. Alberi AVL. Rotazioni in un albero AVL. Inserimento di un nodo in un albero AVL. Rimozione di un nodo da un albero AVL.
Grafi. Rappresentazione di un grafo con la matrice di adiacenza. Rappresentazione di un grafo con le liste di adiacenza. Visita in ampiezza. Cammini minimi. Visita in profondità. Connettività di un grafo. Componenti connesse. Duplice connettività. Componenti fortemente connesse.
Lingua Insegnamento
ITALIANO
Corsi
Corsi
MATEMATICA
Laurea
3 anni
No Results Found
Persone
Persone
Professori/esse Ordinari/e
No Results Found