ECTS - University of Pisa
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 (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 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 sono a disposizione sulla piattaforma di eLearning (Google Classroom).
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 are available on the eLearning platform (Google Classroom).
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 è presente sulla piattaforma di eLearning (Google Classroom).
Il docente è a disposizione per ricevimenti prenotabili all'indirizzo: shorturl.at/fgjFL
All teaching material is available on the eLearning platform (Google Classroom).
The teacher is available for booking meetings at: shorturl.at/fgjFL
L'esame è costituito da due prove obbligatorie:
- Test a risposta multipla
- Prova pratica di programmazione
Per poter accedere all’esercizio lo studente deve aver raggiunto la sufficienza al test. Le prove devono essere svolte nello stesso appello.
La valutazione finale sarà calcolata come la media 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 as the average of the marks from the two tests.
Failure to pass the programming exercise invalidates the assessment of the multiple-choice test.
