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 dei programmi per calcolarne la complessità e programmazione in c++ di algoritmi sulle strutture dati trattate.
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.
Conoscenza di matematica delle scuole superiori.
Conoscenza di base del linguaggio di programmazione c++.
Mathematics knowledge of higher schools. Basic knowledge of c ++ programming language.
Non ci sono co-requisiti.
There are no co-requisites.
Il corso è un pre-requisito per insegnamenti successivi di argomento informatico.
Th course is a prerequisite for the successive courses in computer science.
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 slide 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.
Definizione di complessità computazionale (notazione O-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) .
Alberi binari di ricerca: memorizzazione, visite e programmzione 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 memorizzaione. Visita in profondità, algoritmo di Kruskal per provare il minimo albero di copertura, algorirmo di Dijkstra per trovare i cammini minimi da un nodo a tutti gli altri nodi.
Cenni alla NP-completezza: definizioni, riducibiltà fra problemi, problemi non risolubili.
Nozioni avanzate di programmazione a oggetti in c++: funzioni e classi modeloo, eraditarietà semplice, gestione delle eccezioni.
Computational complexity of algorithms: big-O notation.
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 .
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.
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.
Non sono previsti.
They are not.
