Programma del Corso
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.Course Syllabus
Part One: PYTHON PROGRAMMING
1. Variables, expressions and instructions - Assignments â Variable names â Expressions and instructions Script mode â operation precedence â string operations â comments
2. Functions - Calling functions â mathematical functions â composition â adding new functions â Definitions and their use â Execution flow â parameters and arguments â variables and parameters are local â productive and void functions
3. Conditions and recursion- Integer division and modulus â Boolean expressions â Logical operators â Conditional execution â alternative execution â series of conditions â nested conditions - Recursion â Infinite recursion
4. Productive functions - return values â composition â Boolean functions â Type controlÂ
5. Iterations: while and for constructs
6. Strings - A string is a sequence â String traversal â Slicing -String immutability â Searching â Cycles and counters â string methods â operator in â string comparison
7. Lists - A list is a sequence â Lists are mutable â List traversal â List manipulation â Slicing â List methods â Removing elements â Lists and strings â Objects and values â Alias â Using lists as argumentsÂ
8. Dictionaries- A dictionary is a map â A dictionary as a collection of counters â Cycles and dictionaries â Inverse lookup â Dictionaries and lists
9. Tuples-Tuples are immutable â Tuple assignment â Tuple as return values â Lists and tuples â Dictionaries and tuples â Sequences of sequences
10. Sets- Definition of sets â Sets are mutable â Fundamental operations: adding, removing, intersection, union, difference
11. Files- Reading and writing text files â Text input and output
Part Two: ALGORITHMS AND DATA STRUCTURES
1. Introduction-Insertion sort (algorithm and analysis) â Function growth (asymptotic notation): Î, O, Ω notations
2. Divide and conquer- Iterative method applied to recursion equations â mergesort algorithm (algorithm and analysis) â factorial of an integer number: recursive implementation (algorithm and analysis) â binary search (algorithm and analysis)
3. Data structures- Stack â Python implementation with lists - Queues â Double queues â Python implementation with lists - Simply and doubly linked lists â Python implementation with dictionaries - Generic and binary trees â Tree traversal: preorder, postorder, breadth first search, inorder â Search binary tree: definition, operations (insertion, removal, deletion) â Python implementation with dictionaries â Binary heaps: max-heap, min-heap, element insertion/removal, heapq Python module
- Graphs: definitions, data structures (edge list, adjacency list, adjacency matrix). Graph traversal (depth and breadth first searches). Single source shortest paths: Dijkstra algorithm. Minimum spanning trees: Prim-Jarnik and Kruskal algorithms â Python implementation with dictionaries
4. Sorting- Heapsort â Quicksort â Linear sorting: counting sort - Computational cost of sorting algorithms.