View syllabus
ALGORITHMS AND DATA STRUCTURES
NICOLETTA DE FRANCESCO
Academic year2019/20
CourseCOMPUTER ENGINEERING
Code756II
Credits6
PeriodSemester 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
ALGORITMI E STRUTTURE DATIING-INF/05LEZIONI60
NICOLETTA DE FRANCESCO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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).

Knowledge

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.

Modalità di verifica delle conoscenze

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.

Assessment criteria of knowledge

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.

Capacità

Analisi della complessità degli algoritmi. Progettazione  di algoritmi e loro implementazione in c++ sulle strutture dati presentate.

Skills

Complexity analysis of programs. c ++ programming of algorithms on introduced
data structures.

Modalità di verifica delle capacità

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.

Assessment criteria of skills

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.

Comportamenti

Saranno acquisite sensibilità alle problematiche della programmazione.

Behaviors

Sensitivity to coding issues will be gained.

Modalità di verifica dei comportamenti

Tramite la stesura del testo di esame.

Assessment criteria of behaviors

By writing the exam text.

Prerequisiti (conoscenze iniziali)

Prerequisito obbligatorio di questo insegnamento è il superamento dell'unità didattica

 Fondamenti di Programmazione

 

Prerequisites

Mathematics knowledge of higher schools. Basic knowledge of c ++ programming language.

Indicazioni metodologiche

 

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.

 

Teaching methods

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.

Programma (contenuti dell'insegnamento)

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.

 

 

Syllabus

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.

 

Bibliografia e materiale didattico

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.

Bibliography

Course notes and slides are on the course site, where some bibliographical
references and examples of exam trails are also indicated.

Indicazioni per non frequentanti

Tutto il materiale didattico è presente sul sito. E' consigliabile chiedere qualche ricevimento al docente.

Non-attending students info

All teaching material is on the site. It is advisable to ask some meeeting
to the teacher.

Modalità d'esame

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

  • Lo studente deve essere identificato mostrando alla videocamera il libretto universitario (o altro documento di riconoscimento se il libretto non è disponibile). Coloro che non vogliono mostrare le informazioni personali alla videocamera possono mostrare il libretto o documento coprendo tali informazioni, facendo vedere solamente il nome e la foto.
  • Lo studente dovrà scrivere su fogli propri mantenendo la videocamera del PC a circa 1 metro in modo che sia visibile, oltre allo studente stesso, il tavolo su cui lavora. Il tavolo dovrà essere sgombro e lo studente dovrà avere a disposizione solamente la penna e i fogli su cui scrivere. Lo studente non dovrà avere la luce alle spalle.
  • La prova consta di alcuni quesiti, che verranno forniti in sequenza (sulla chat o via email).
  • Per ogni quesito lo studente, dopo aver ricopiato il testo del quesito sul suo foglio, dovrà allontanarsi dal PC e quindi dalla videocamera (per rispettare la distanza).
  • Lo studente avrà a disposizione un tempo per risolverlo, commisurato alla complessità del quesito. Dopo questo tempo dovrà mostrare a video il foglio con la soluzione, fare una copia del foglio insieme al libretto universitario o documento, (mediante foto con lo smartphone, tablet, …), e mandarla immediatamente, in formato JPG, via email utilizzando il proprio indirizzo di posta di ateneo, all’indirizzo: defrancesco@unipi.it e all’indirizzo luca.alfeo@ing.unipi.it . La mail dovrà avere come soggetto: “Cognome Nome matricola quesito n”. Gli studenti con DSA avranno a disposizione alcuni minuti in più per risolvere ogni quesito. Quando tutti gli studenti avranno inviato la soluzione di un quesito, verrà proposto il quesito successivo.
  • La correzione del compito e i risultati saranno presentati ed eventualmente discussi con gli studenti nei giorni seguenti durante una sessione online, dopo la quale verranno inseriti sul sito VALUTAMI e verbalizzati (se uno studente non potrà partecipare alla correzione chiederà un appuntamento al docente).
  • Per qualsiasi problema rivolgersi ai docenti per individuare una soluzione.

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

  • Lo studente deve essere identificato mostrando alla videocamera il libretto universitario (o altro documento di riconoscimento se il libretto non è disponibile). Coloro che non vogliono mostrare le informazioni personali alla videocamera possono mostrare il libretto o documento coprendo tali informazioni, facendo vedere solamente il nome e la foto.
  • Lo studente dovrà scrivere su fogli propri mantenendo la videocamera del PC a circa 1 metro in modo che sia visibile, oltre allo studente stesso, il tavolo su cui lavora. Il tavolo dovrà essere sgombro e lo studente dovrà avere a disposizione solamente la penna e i fogli su cui scrivere. Lo studente non dovrà avere la luce alle spalle.
  • La prova consta di alcuni quesiti, che verranno forniti in sequenza (sulla chat o via email).
  • Per ogni quesito lo studente, dopo aver ricopiato il testo del quesito sul suo foglio, dovrà allontanarsi dal PC e quindi dalla videocamera (per rispettare la distanza).
  • Lo studente avrà a disposizione un tempo per risolverlo, commisurato alla complessità del quesito. Dopo questo tempo dovrà mostrare a video il foglio con la soluzione, fare una copia del foglio insieme al libretto universitario o documento, (mediante foto con lo smartphone, tablet, …), e mandarla immediatamente, in formato JPG, via email utilizzando il proprio indirizzo di posta di ateneo, all’indirizzo: defrancesco@unipi.it e all’indirizzo luca.alfeo@ing.unipi.it . La mail dovrà avere come soggetto: “Cognome Nome matricola quesito n”. Gli studenti con DSA avranno a disposizione alcuni minuti in più per risolvere ogni quesito. Quando tutti gli studenti avranno inviato la soluzione di un quesito, verrà proposto il quesito successivo.
  • La correzione del compito e i risultati saranno presentati ed eventualmente discussi con gli studenti nei giorni seguenti durante una sessione online, dopo la quale verranno inseriti sul sito VALUTAMI e verbalizzati (se uno studente non potrà partecipare alla correzione chiederà un appuntamento al docente).
  • Per qualsiasi problema rivolgersi ai docenti per individuare una soluzione.

PROVA PRATICA

La modalità è identica a quella della prova scritta, ma verrà fornito un unico quesito.

Assessment methods

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.

Updated: 29/05/2020 11:08