ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| ALGORITMI E STRUTTURE DATI | ING-INF/05 | LEZIONI | 60 |
|
Le conoscenze che lo studente deve acquisire riguardano la complessità computazionale degli algoritmi e alcuni algoritmi di base per la soluzione di problemi diversi su diverse strutture dati (array, liste, alberi, grafi). Inoltre deve acquisire la conosenza di elementi avanzati di programmazione a oggetti nel linguaggio di programmazione c++ (funzioni e classi modello, ereditarietà, eccezioni).
The knowledge that the students must acquire relates to the computational
complexity of the algorithms and some basic algorithms for solving different
problems on different data structures (arrays, lists, trees, graphs).
It must also acquire the knowledge of advanced object programming
elements in the c ++ programming language.
Tramite una prova finale scritta che presenta quesiti relativi alle conoscenze, esercizi di analisi di programmi, esercizi di programmazione di semplici algoritmi sulle strutture dati introdotte.
Through a written final exam that introduces knowledge-related questions,
program analysis exercises, programming exercises of simple algorithms
on the data structures introduced. of a written final exam that presents knowledge-related questions,
program analysis exercises, programming of simple algorithms on
the data structures introduced.
Analisi della complessità degli algoritmi. Progettazione di algoritmi e loro implementazione in c++ sulle strutture dati presentate.
Complexity analysis of programs. c ++ programming of algorithms on introduced
data structures.
Mediante una prova pratica in laboratorio di programmazione che riguarda la progettazione di un algoritmo e la sua realizzazione nel linguaggio c++. La capacità di programmazione viene ulteriormente verificata con la prova scritta.
Through a practical programming test that involves the design of an algorithm
and its implementation in the c ++ language.
The programming capacity is further verified with the written test.
Saranno acquisite sensibilità alle problematiche della programmazione.
Sensitivity to coding issues will be gained.
Tramite la stesura del testo di esame.
By writing the exam text.
Prerequisito obbligatorio di questo insegnamento è il superamento dell'unità didattica
Fondamenti di Programmazione
Mathematics knowledge of higher schools. Basic knowledge of c ++ programming language.
Le lezioni sono frontali, con ausilio di slide.
I laboratori si svolgono nelle aule informatiche.
Le esercitazioni di laboratorio possono essere svolte da codocenti
Dal sito di elearning del corso possono essere scaricati i materiali didattici, le comunicazioni docente-studenti, testi di compiti.
Per la comunicazione docenti-studenti vengono usati ricevimenti e posta elettronica.
The lessons are frontal, with slides support. Laboratories take place in computer classrooms. Laboratory exercises can be done by codocents. From the elearning site of the course you can download the teaching materials,
the teacher-student communications, the texts of exercises. For teacher-student communication, receptions and e-mail are used.
Nozione di algoritmo.
Definizione di complessità computazionale (notazioni O-grande, Omega-grande e Theta-grande).
Complessità dei programmi iterativi. Principi e metodi di programmazione ricorsiva. Complessità dei programmi ricorsivi: relazioni di ricorrenza.
Strutture lineari : array e liste. Principali algoritmi di ricerca (lineare, binaria) e ordinamento (selection-sort, bubble-sort, quicksort, mergesort, heapsort, counting sort, radix sort)
Alberi binari: memorizzazione, visite e programmazione di semplici algoritmi.
Alberi generici: : memorizzazione, visite e programmzione di semplici algoritmi.
Alberi binari di ricerca.
Tipo di dato heap.
Metodo di ricerca Hash.
Metodologie di costruzione di algoritmi: divide et impera, programmazione dinamica, programmazione greedy.
Algoritmo per trovare la più lunga sottosequenza comune fra due sequenze.
Algoritmo di Huffman di compressione del codice.
Limiti inferiori: metodo per trovarli mediante gli alberi di decisione.
Grafi orientati e non orientati: definizione e memorizzazione. Visita in profondità
Algoritmo di Kruskal per trovare il minimo albero di copertura
Algoritmo di Dijkstra per trovare i cammini minimi da un nodo a tutti gli altri nodi.
Cenni alla NP-completezza: problemi intrattabili, le classi P e NP, riducibilità fra problemi, problemi NP-completi, problemi non risolubili.
Nozioni avanzate di programmazione a oggetti in c++: funzioni e classi modello, eraditarietà semplice, gestione delle eccezioni.
Notion of Algorithm.
Computational complexity of algorithms: big-O , big-omega and big-theta notations.
Complexity of iterative programs. Principles and methods of recursion. Complexity of recursive programs: recurrence equations.
Principal research algorithm: linear serach, binary search.
Principal sorting algorithms: selection-sort, bubble-sort, quicksort, mergesort, heapsort, counting sort, radix sort.
Binary trees and bynary search trees. Generic trees. Heap. Hash tables. Decision trees.
programming methodologies: divide and conquer, dynamic programming, greedy algorithms.
Graphs: depth visit, Kruskal algorithm for finding the minimum spanning tree, Dijkstra algorithms for finding the minimum paths from a node.
Theory of NP-completness.
Advanced notions of objecy tprogramming in c++: templates, inheritance, exceptions.
Gli appunti del corso e le slide delle lezioni e dei laboratori sono presenti sul sito del corso, dove sono indicati anche alcuni riferimenti bibliografici ed esempi di tracce di esame.
Course notes and slides are on the course site, where some bibliographical
references and examples of exam trails are also indicated.
Tutto il materiale didattico è presente sul sito. E' consigliabile chiedere qualche ricevimento al docente.
All teaching material is on the site. It is advisable to ask some meeeting
to the teacher.
L'esame consiste in una prova pratica di programmazione e in una prova scritta.
Il superamento della prova pratica è prerequisito per sostenere la prova scritta.
Le due prove possono sostenute in appelli diversi nell'anno accademico.
Modalità per l’esame di Algoritmi e strutture dati per gli appelli di giugno/luglio 2020
Docenti: Nicoletta De Francesco (titolare), Antonio Luca Alfeo
La modalità dell’esame rimane quella degli anni precedenti:
- l’esame è composto da una prova pratica e da una successiva prova scritta (con contiene anche domane di orale).
- Il superamento della prova pratica permette di accedere alla prova scritta in qualsiasi appello e non deve essere ripetuta, anche nel caso che lo scritto sia stato provato più volte senza successo.
- Per sostenere le prove è comunque necessario aver superato l’esame di Fondamenti di Programmazione.
-Non ci sono limiti al numero di occasioni di esame.
La differenza con gli appelli passati è che sia la prova pratica che la prova scritta si svolgeranno in modalità telematica con i software Teams o Meet (sul sito VALUTAMI verrà indicata la modalità per ogni prova). Gli studenti, a meno che non siano pochissimi, saranno suddivisi in gruppi che svolgeranno l’esame in più mandate a partire dall’ora e dal giorno indicato sul calendario ufficiale. La suddivisione sarà comunicata sul sito VALUTAMI e/o per posta elettronica. Eventuali problemi di sovrapposizione con altri esami saranno risolti tramite comunicazione fra i docenti e gli studenti. Le iscrizioni all’esame saranno chiuse cinque giorni prima della data ufficiale dell’esame.
Le prove non sono pubbliche: possono partecipare al gruppo Teams o Meet esclusivamente gli studenti iscritti e individuati per la relativa prova.
Per poter sostenere l’esame è necessario avere a disposizione computer con microfono e videocamera, 10 fogli A4 bianchi, penna nera con tratto ben visibile, libretto universitario (o carta di identità) e smartphone (assicurarsi che questo sia carico e che sia possibile effettuare connessione tramite hotspot nel caso ci siano problemi di connessione sulla rete principale usata dallo studente).
La registrazione sia audio che video è tassativamente vietata (per direttiva dell’ateneo).
Le modalità per le prove sono le seguenti:
PROVA SCRITTA
PROVA PRATICA
La modalità è identica a quella della prova scritta, ma verrà fornito un unico quesito.
Modalità per l’esame di Algoritmi e strutture dati per gli appelli di giugno/luglio 2020
Docenti: Nicoletta De Francesco (titolare), Antonio Luca Alfeo
La modalità dell’esame rimane quella degli anni precedenti:
- l’esame è composto da una prova pratica e da una successiva prova scritta (con contiene anche domane di orale).
- Il superamento della prova pratica permette di accedere alla prova scritta in qualsiasi appello e non deve essere ripetuta, anche nel caso che lo scritto sia stato provato più volte senza successo.
- Per sostenere le prove è comunque necessario aver superato l’esame di Fondamenti di Programmazione.
-Non ci sono limiti al numero di occasioni di esame.
La differenza con gli appelli passati è che sia la prova pratica che la prova scritta si svolgeranno in modalità telematica con i software Teams o Meet (sul sito VALUTAMI verrà indicata la modalità per ogni prova). Gli studenti, a meno che non siano pochissimi, saranno suddivisi in gruppi che svolgeranno l’esame in più mandate a partire dall’ora e dal giorno indicato sul calendario ufficiale. La suddivisione sarà comunicata sul sito VALUTAMI e/o per posta elettronica. Eventuali problemi di sovrapposizione con altri esami saranno risolti tramite comunicazione fra i docenti e gli studenti. Le iscrizioni all’esame saranno chiuse cinque giorni prima della data ufficiale dell’esame.
Le prove non sono pubbliche: possono partecipare al gruppo Teams o Meet esclusivamente gli studenti iscritti e individuati per la relativa prova.
Per poter sostenere l’esame è necessario avere a disposizione computer con microfono e videocamera, 10 fogli A4 bianchi, penna nera con tratto ben visibile, libretto universitario (o carta di identità) e smartphone (assicurarsi che questo sia carico e che sia possibile effettuare connessione tramite hotspot nel caso ci siano problemi di connessione sulla rete principale usata dallo studente).
La registrazione sia audio che video è tassativamente vietata (per direttiva dell’ateneo).
Le modalità per le prove sono le seguenti:
PROVA SCRITTA
PROVA PRATICA
La modalità è identica a quella della prova scritta, ma verrà fornito un unico quesito.
The exam consists of a practica programming test of and a written test.
Passing the practical test is a prerequisite for the written test.
The two tests can be held in different appeals in the academic year.
