- Oggetto:
- Oggetto:
Istituzioni di Algoritmi e Strutture Dati
- Oggetto:
Additional Algorithms and Data Structures
- Oggetto:
Anno accademico 2022/2023
- Codice dell'attività didattica
- INF0211
- Docenti
- Andras Horvath (Titolare)
Diego Magro (Titolare)
Gian Luca Pozzato (Titolare)
Idilio Drago (Titolare)
Ugo De' Liguoro (Titolare) - Anno
- 1° anno 2° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- A scelta dello studente
- Crediti/Valenza
- 9 CFU - Numero di ore - Number of hours: 48 (in aula) + 30 (in laboratorio)
- SSD dell'attività didattica
- INF/01 - informatica
- Modalità di erogazione
- Tradizionale
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Scritto più orale obbligatorio
- Prerequisiti
-
Si presuppone che lo studente sia a conoscenza delle basi della programmazione e dei linguaggi di programmazione C e Java; che sia in possesso delle nozioni elementari della matematica del discreto, del continuo, e della logica matematica.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): Programmazione I & Laboratorio, Programmazione II & Laboratorio, Matematica Discreta, Analisi Matematica, Logica Matematica, Sistemi Operativi (in particolare l'apprendimento del linguaggio C).Students are expected to have basic knowledge and competence of the C and Java programming languages. Elementary knowledge of mathematics, both discrete and continuous, and of mathematical logic are also required.
Preparatory Courses (providing the expected entry skills): Program course I and II and labs; Discrete Mathematics; Mathematical Analysis, Mathematical Logic, Operating Systems. - Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
L’insegnamento ha lo scopo di introdurre i concetti e le tecniche fondamentali per l’analisi e la progettazione di algoritmi, che sono alla base dello sviluppo del software. Gli studenti acquisiranno conoscenze circa l’analisi di correttezza e complessità computazionale degli algoritmi, sulle strutture dati per la rappresentazione dell’informazione, sulle tecniche di problem solving mediante lo sviluppo di algoritmi efficienti. L’insegnamento è supportato da un laboratorio che ne costituisce parte integrante, finalizzato alla realizzazione e sperimentazione degli algoritmi e delle strutture dati mediante un linguaggio imperativo ed uno object-oriented. Questo insegnamento concorre agli obiettivi formativi dell'ambito propedeutico del Corso di Laurea Magistrale in Informatica.The course is an introduction to the fundamental concepts and techniques for the analysis and the design of algorithms, that is at the heart of software development. Students will acquire knowledge about correctness and complexity analysis of algorithms, data structures representing information and problem-solving techniques to efficiently solve computational problems. The course is supported by a laboratory that constitutes an essential part of it. It is aimed at implementing and experiencing algorithms using procedural and object-oriented programming languages. This teaching contributes to the educational objectives of the preparatory area of the Master's Degree in Computer Science.- Oggetto:
Risultati dell'apprendimento attesi
CONOSCENZA E CAPACITÀ DI COMPRENSIONE Acquisizione di conoscenze teoriche e operative relative a problemi algoritmici di base e della loro risoluzione mediante il disegno di algoritmi e di strutture dati efficienti, nonché la capacità di analizzare le soluzioni adottate sotto il profilo della loro correttezza logica e complessità computazionale.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE Acquisizione della capacità di applicare le conoscenze teoriche a problemi concreti nei vari ambiti della programmazione di sistemi informatici, tanto producendo il codice dei programmi quanto utilizzando librerie software preesistenti, con particolare attenzione al rigore metodologico, alla chiarezza e verificabilità delle soluzioni adottate nonché alla loro efficienza ed affidabilità.
AUTONOMIA DI GIUDIZIO Acquisizione di consapevole autonomia di giudizio con riferimento alla valutazione delle diverse soluzioni teoriche che si possono adottare e del loro impatto sulle applicazioni pratiche.
ABILITÀ COMUNICATIVE Acquisizione di competenze e strumenti per la comunicazione nella forma scritta e orale per documentare le soluzioni adottate in modo tecnicamente rigoroso.
CAPACITÀ DI APPRENDIMENTO Acquisizione di capacità autonome di apprendimento e di autovalutazione della propria preparazione, atte ad intraprendere gli studi successivi con un alto grado di autonomia.
KNOWLEDGE AND UNDERSTANDING Acquisition of theoretical and applicative skills concerning basic computational problems and their solution by designing efficient algorithms and data structures; acquisition of the ability to analyse the adopted solutions with respect to their logical correctness and computational complexity.
APPLYING KNOWLEDGE AND UNDERSTANDING Acquisition of the ability to apply theoretical knowledge to practical issues in various areas of programming computer systems, both producing new code and using preexistent libraries, with special regard to methodological rigour, clarity and verifiability of the adopted solutions and their efficiency and affordability.
MAKING JUDGEMENTS Acquisition of aware judgment autonomy concerning the evaluation of several theoretical solutions that are available and of their impact on the practical applications.
COMMUNICATION SKILLS Acquisition of oral and written communication skills and expertise as well as the ability to document the adopted solutions in a technically rigorous way.
LEARNING SKILLS Acquisition of autonomous learning capacity and self-assessment of its
preparation, in order to undertake subsequent studies with a high degree of autonomy.- Oggetto:
Modalità di insegnamento
Sono previste 48 ore di lezione frontale ed esercitazioni in aula, e 24 ore di attività guidata dai docenti in laboratorio. Per le indicazioni bibliografiche, la distribuzione di note ed altro materiale didattico si farà uso della piattaforma e-learning Moodle, e per la consegna e valutazione degli elaborati delle esercitazioni sarà impiegato un repository GitLab; si richiede agli studenti l’iscrizione ad entrambe le piattaforme.Frontal lessons and exercises will be scheduled in the amount of 48 hours, plus 24 hours of tutored activities in the laboratory. The e-learning platform Moodle will be employed for distributing bibliographies, handouts and further didactic material and a repository on the GitLab platform will be used for assignments and their grading; therefore students are required to sign in to the course page on both platforms.- Oggetto:
Modalità di verifica dell'apprendimento
L'esame di Algoritmi e strutture dati consiste in una prova scritta, somministrata mediante la piattaforma Esami, ed in una discussione orale del progetto di laboratorio. Il superamento dello scritto permette di accedere alle prove orali della sessione in cui è stato superato lo scritto. Nel caso in cui questa seconda prova non venga superata entro i termini della sessione, lo scritto dovrà essere ripetuto. Il voto sarà la media pesata dei voti ottenuti nelle due prove scritta ed orale, valutate in 30+1 esimi, essendo comunque necessario il raggiungimento della sufficienza in entrambe le prove.The exam of the course Algorithm and data structures consists of a written test, that will be available by means of the platform Esami, and of an oral discussion of the project assigned in the laboratory. The passing of the written exam must precede the oral discussion of the laboratory project, and the latter must take place in the same oral session. In case the oral exam is not passed, the written test must be repeated in a subsequent session. The registered grade will be the weighted average of the grades of the two parts, 2/3 and 1/3 for the written and oral exams respectively. To pass the exam the grades of both tests must be greater or equal to the threshold of 18/30.- Oggetto:
Programma
Programma
- Problemi e algoritmi: risolubilità, correttezza, complessità.
- Analisi computazionale e complessità asintotica
- Algoritmi di ordinamento
- Algoritmi elementari quadratici
- Divide et impera: mergesort e quicksort
- Risoluzione di relazioni di ricorrenza
- Limiti inferiori per l’ordinamento
- Programmazione dinamica
- Massima sottosequenza comune
- Strutture dati
- Strutture concrete: array, liste, tabelle hash
- Strutture astratte: pile, code, dizionari
- Code di priorità, heapsort
- Analisi ammortizzata, cenni
- Alberi
- Definizione e visita
- Alberi di ricerca
- Alberi rosso-neri
- Grafi
- Definizione e visita
- Ordinamento topologico e componenti fortemente connesse
- Algoritmi greedy: alberi di copertura minima
- Cammini minimi: algoritmo di Dijkstra
Syllabus
- Problems and algorithms
- Asyntotic notation and computational complexity
- Sorting algorithms
- Quadratic sorting algorithms
- Divide et impera: mergesort and quicksort
- Solution of recurrence relations
- Lower bounds to the sorting problem
- Dynamic programming
- Largest common subsequence
- Data structures
- Concrete structures: arrays, lists, hash tables
- Abstract structures: stacks, queues, dictionaries
- Prority queues, heapsort
- Amortized analysis
- Trees
- Definition and visit
- Search trees
- Red-black trees
- Graphs
- Definition and visit
- Topological sort and strongly connected components
- Greedy algorithms: minimum spanning trees
- Shortest paths, Dijkstra algorithm.
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Introduzione agli algoritmi e strutture dati (ed. terza)
- Anno pubblicazione:
- 2010
- Editore:
- McGraw-Hill
- Autore:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, , Clifford Stein
- Obbligatorio:
- No
- Oggetto:
- Libro
- Titolo:
- Concetti di informatica e fondamenti di Java (quinta ed. o successive)
- Anno pubblicazione:
- 2010
- Editore:
- Apogeo
- Autore:
- Cay S. Horstmann
- Obbligatorio:
- No
- Oggetto: