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).

Learning Goals

The main objectives of the course are: - analyze the main techniques for algorithm design - classify, analize, design and implement algorithms - evaluate costs in terms of computational efficiency - choose and implement suitable data structures - make the best compromise among conflicting requirements (cost, simplicity, efficiency)

Metodi didattici

Lezioni frontali Esercizi assegnati dal docente, esercizi guidati con il supporto del docente.

Teaching Methods

Lectures Exercises given by the teacher, guided exercises with teacher support.

Prerequisiti

Conoscenze di base di matematica (algebra di base, concetto di funzione, progressioni) Conoscenza di base di un linguaggio di programmazione di alto livello

Prerequisites

Basic knowledge of mathematics (basic algebra, definition of function, progressions) Basic knowledge of a high-level programming language

Verifiche dell'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. La prova scritta viene sostituita da una prova orale in caso di didattica a distanza. Prova orale facoltativa (solo per gli studenti il cui voto alla prova scritta è non inferiore a 18/30). 

Assessment

Mandatory written exam (solution of problems with recursive or iterative approach on Python programming and data structures). The written exam is considered as passed if the grade is at least 18/30. The written exam will be replaced by an oral exam in case of distance learning.  Elective oral exam (only for students whose written exam grade is not smaller than 18/30).

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.