ID:
A000861
Durata (ore):
72
CFU:
9
Url:
INFORMATICA/DATA ANALYSIS Anno: 1
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)
Metodi didattici
Lezioni frontali
Esercizi assegnati dal docente, esercizi guidati con il supporto del docente.
Esercizi assegnati dal docente, esercizi guidati con il supporto del docente.
Verifica Apprendimento
Prova scritta obbligatoria (risoluzione di problemi mediante approccio ricorsivo o iterativo sulla programmazione Python e le strutture dati). La prova si intende superata in caso di valutazione non inferiore a 18/30. Prova orale facoltativa (solo per gli studenti il cui voto alla prova scritta è non inferiore a 18/30).
Testi
Allen Downey Think Python, Second Edition
Cay Horstmann, Rance D. Necaise Python for everyone (2014) Wiley
David Beazley, Brian K. Jones Python Cookbook O’Reilly, Third Edition
Cormen, Leiserson, Rivest, Stein Algorithms and Data Structures: an introduction, Third Edition
Goodrich, Tamassia, Goldwasser Data Structures and Algorithms in Python (2014) Wiley
Cay Horstmann, Rance D. Necaise Python for everyone (2014) Wiley
David Beazley, Brian K. Jones Python Cookbook O’Reilly, Third Edition
Cormen, Leiserson, Rivest, Stein Algorithms and Data Structures: an introduction, Third Edition
Goodrich, Tamassia, Goldwasser Data Structures and Algorithms in Python (2014) Wiley
Contenuti
Parte 1: PROGRAMMAZIONE PYTHON
1. Variabili, espressioni e istruzioni – Istruzioni di assegnazione – Nomi delle variabili – Espressioni e istruzioni – Modalità script – Ordine delle operazioni – Operazioni sulle stringhe – Commenti
2. Funzioni– Chiamate di funzione – Funzioni matematiche – Composizione – Aggiungere nuove funzioni – Definizioni e loro utilizzo – Flusso di esecuzione – Parametri e argomenti – Variabili e parametri sono locali – Funzioni produttive e funzioni vuote
3. Istruzioni condizionali e ricorsione – Divisione intera e modulo – Espressioni booleane – Operatori logici – Esecuzione condizionale – Esecuzione alternativa – Condizioni in serie – Condizioni nidificate – Ricorsione – Ricorsione infinita
4. Funzioni produttive – Valori di ritorno – Composizione – Funzioni booleane – Controllo dei tipi
5. Iterazione: costrutti while e for
6. Stringhe – Una stringa è una sequenza – Attraversamento di una stringa – Slicing – Immutabilità delle stringhe – Ricerca – Cicli e contatori – Metodi delle stringhe – Operatore in – Confronto di stringhe
7. Liste – Una lista è una sequenza – Le liste sono mutabili – Attraversamento di una lista – Operazioni sulle liste – Slicing – Metodi delle liste – Cancellare elementi – Liste e stringhe – Oggetti e valori – Alias – Liste come argomenti
8. Dizionari – Un dizionario è una mappatura – Il dizionario come raccolta di contatori – Cicli e dizionari – Lookup inverso – Dizionari e liste
9. Tuple – Le tuple sono immutabili – Assegnazione di tupla – Tuple come valori di ritorno – Liste e tuple – Dizionari e tuple – Sequenze di sequenze
10. Set – Definizione di set – I set sono mutabili – Operazioni fondamentali: aggiunta, rimozione, intersezione, unione, differenza
11. File – Lettura e scrittura di file di testo – Input e output di testi
Parte 2: ALGORITMI E STRUTTURE DATI
1. Introduzione – Insertion sort (algoritmo e analisi) – Crescita delle funzioni (notazione asintotica): notazione Θ, O, Ω
2. Divide et Impera – Risoluzione delle equazioni alle ricorrenze con il metodo iterativo – Ordinamento mergesort (algoritmo e analisi) – Implementazione ricorsiva dell’algoritmo per il calcolo del fattoriale (algoritmo ed analisi) – Ricerca binaria (algoritmo e analisi)
3. Strutture dati – Stack – Implementazione Python mediante liste – Code – Code doppie – Implementazione Python mediante liste – Liste concatenate (semplici, doppie) – Implementazione Python di liste mediante dizionari – Alberi: generici, binari – Visita di un albero: preorder, postorder, in ampiezza, inorder – Alberi binari di ricerca: definizione, operazioni (inserimento, cancellazione, ricerca) – Implementazione Python di alberi mediante dizionari – Heap binari: max-heap, min-heap, inserimento/rimozione di elementi, modulo Python heapq – Grafi: definizioni, strutture dati (edge list, adjacency list, adjacency matrix). Esplorazione di un grafo (in profondità e in ampiezza). Percorsi minimi da singola sorgente: algoritmo di Dijkstra. Alberi minimi di copertura: algoritmi di Prim-Jarnik e Kruskal. – Implementazione Python mediante dizionari
4. Ordinamento – Heapsort – Quicksort – Ordinamento lineare: counting sort – Costo computazionale degli algoritmi di ordinamento.
1. Variabili, espressioni e istruzioni – Istruzioni di assegnazione – Nomi delle variabili – Espressioni e istruzioni – Modalità script – Ordine delle operazioni – Operazioni sulle stringhe – Commenti
2. Funzioni– Chiamate di funzione – Funzioni matematiche – Composizione – Aggiungere nuove funzioni – Definizioni e loro utilizzo – Flusso di esecuzione – Parametri e argomenti – Variabili e parametri sono locali – Funzioni produttive e funzioni vuote
3. Istruzioni condizionali e ricorsione – Divisione intera e modulo – Espressioni booleane – Operatori logici – Esecuzione condizionale – Esecuzione alternativa – Condizioni in serie – Condizioni nidificate – Ricorsione – Ricorsione infinita
4. Funzioni produttive – Valori di ritorno – Composizione – Funzioni booleane – Controllo dei tipi
5. Iterazione: costrutti while e for
6. Stringhe – Una stringa è una sequenza – Attraversamento di una stringa – Slicing – Immutabilità delle stringhe – Ricerca – Cicli e contatori – Metodi delle stringhe – Operatore in – Confronto di stringhe
7. Liste – Una lista è una sequenza – Le liste sono mutabili – Attraversamento di una lista – Operazioni sulle liste – Slicing – Metodi delle liste – Cancellare elementi – Liste e stringhe – Oggetti e valori – Alias – Liste come argomenti
8. Dizionari – Un dizionario è una mappatura – Il dizionario come raccolta di contatori – Cicli e dizionari – Lookup inverso – Dizionari e liste
9. Tuple – Le tuple sono immutabili – Assegnazione di tupla – Tuple come valori di ritorno – Liste e tuple – Dizionari e tuple – Sequenze di sequenze
10. Set – Definizione di set – I set sono mutabili – Operazioni fondamentali: aggiunta, rimozione, intersezione, unione, differenza
11. File – Lettura e scrittura di file di testo – Input e output di testi
Parte 2: ALGORITMI E STRUTTURE DATI
1. Introduzione – Insertion sort (algoritmo e analisi) – Crescita delle funzioni (notazione asintotica): notazione Θ, O, Ω
2. Divide et Impera – Risoluzione delle equazioni alle ricorrenze con il metodo iterativo – Ordinamento mergesort (algoritmo e analisi) – Implementazione ricorsiva dell’algoritmo per il calcolo del fattoriale (algoritmo ed analisi) – Ricerca binaria (algoritmo e analisi)
3. Strutture dati – Stack – Implementazione Python mediante liste – Code – Code doppie – Implementazione Python mediante liste – Liste concatenate (semplici, doppie) – Implementazione Python di liste mediante dizionari – Alberi: generici, binari – Visita di un albero: preorder, postorder, in ampiezza, inorder – Alberi binari di ricerca: definizione, operazioni (inserimento, cancellazione, ricerca) – Implementazione Python di alberi mediante dizionari – Heap binari: max-heap, min-heap, inserimento/rimozione di elementi, modulo Python heapq – Grafi: definizioni, strutture dati (edge list, adjacency list, adjacency matrix). Esplorazione di un grafo (in profondità e in ampiezza). Percorsi minimi da singola sorgente: algoritmo di Dijkstra. Alberi minimi di copertura: algoritmi di Prim-Jarnik e Kruskal. – Implementazione Python mediante dizionari
4. Ordinamento – Heapsort – Quicksort – Ordinamento lineare: counting sort – Costo computazionale degli algoritmi di ordinamento.
Lingua Insegnamento
INGLESE
Corsi
Corsi
INFORMATICA
Laurea
3 anni
No Results Found
Persone
Persone
Professori/esse Associati/e
No Results Found