ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| ALGORITMI E STRUTTURE DATI | ING-INF/05 | LEZIONI | 60 |
|
Le conoscenze che lo studente dovrá acquisire riguardano la complessità computazionale degli algoritmi e alcuni algoritmi di base per la soluzione di problemi su diverse strutture dati (array, liste, alberi, grafi). Lo studente inoltre dovrá acquisire conoscenze relative a 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 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 (test a risposta multipla).
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 progettazione e valutazione di algoritmi, e della loro programmazione.
Sensitivity to coding issues will be gained.
Tramite le due prove di esame.
By two exam stages (multiple choice test and programming test)
Prerequisito obbligatorio di questo insegnamento è il superamento dell'unità didattica
Fondamenti di Programmazione
Mathematics knowledge of higher schools. Basic knowledge of c ++ programming language.
Il corso sarà erogato secondo le modalità stabilite dall'ateneo. Sono previste sessioni di lezioni teoriche ed esercitazioni pratiche al calcolatore. Si consiglia a ciascuno studente di fornirsi di laptop personale per seguire le attività pratiche.
The course will be delivered in the manner established by the university. There will be sessions of theoretical lectures and practical exercises at the computer. Each student is advised to provide a personal laptop to follow the practical activities.
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 saranno messi a disposizione sulla piattaforma Microsoft Teams.
Testi consigliati:
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano «ALGORITMI E STRUTTURE DATI 2/ED»
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein «INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 3/ED»
Course notes and slides from lectures and practical classes will be made available on the Microsoft Teams platform.
Recommended texts:
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano «ALGORITMI E STRUTTURE DATI 2/ED»
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein «INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 3/ED»
Tutto il materiale didattico sará reso disponibile sulla piattaforma Microsoft Teams.
Il docente è a disposizione per ricevimenti prenotabili tramite email.
All teaching materialwill be made available on the Microsoft Teams platform
The teacher is available for booking meetings via email.
L'esame è costituito da due prove obbligatorie:
- Test a risposta multipla
- Prova pratica di programmazione
Per poter accedere alla prova pratica di programmazione lo studente deve aver raggiunto la sufficienza al test. Le prove devono essere svolte nello stesso appello.
La valutazione finale sarà calcolata tenendo conto dei voti delle due prove.
Il non superamento della prova pratica di programmazione annulla la valutazione del test a risposta multipla.
The examination consists of two compulsory tests:
- Multiple-choice test
- Programming exercise
To be eligible for the exercise, the student must have achieved a pass mark in the test. The tests must be taken in the same call.
The final mark will be calculated considering the marks from the two tests.
Failure to pass the programming exercise invalidates the assessment of the multiple-choice test.
