Università degli Studi di Urbino Carlo Bo / Portale Web di Ateneo


ALGORITMI E STRUTTURE DATI
ALGORITHMS AND DATA STRUCTURES


A.A. CFU
2017/2018 12
Docente Mail Ricevimento studenti
Valerio Freschi Giovedì, 11-13
Didattica in lingua straniera
Insegnamento con materiali opzionali in lingua straniera Inglese
La didattica è svolta interamente in lingua italiana. I materiali di studio e l'esame possono essere in lingua straniera.

Assegnato ai Corsi di Studio

Informatica Applicata (L-31)
Curriculum: PERCORSO COMUNE

Obiettivi Formativi

Il Corso ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale.

Programma

01. Introduzione agli algoritmi e alle strutture dati:
  01.01 Algoritmi e loro tipologie
  01.02 Correttezza di un algoritmo rispetto ad un problema
  01.03 Complessità di un algoritmo rispetto all'uso di risorse
  01.04 Strutture dati e loro tipologie
 
02. Classi di problemi:
 02.01 Problemi decidibili e indecidibili
 02.02 Problemi trattabili e intrattabili
 02.03 Teorema di Cook
 02.04 NP-completezza
 
03. Complessità degli algoritmi:
 03.01 Notazioni per esprimere la complessità asintotica
 03.02 Calcolo della complessità di algoritmi non ricorsivi
 03.03 Calcolo della complessità di algoritmi ricorsivi
 
04. Algoritmi per array :
 04.01 Array: definizioni di base e problemi classici
  04.02 Algoritmo di visita per array
 04.03 Algoritmo di ricerca lineare per array
 04.04 Algoritmo di ricerca binaria per array ordinati
 04.05 Criteri di confronto per algoritmi di ordinamento per array
 04.06 Insertsort
 04.07 Selectsort
 04.08 Bubblesort
 04.09 Mergesort
 04.10 Quicksort
 04.11 Heapsort
 04.12 Code con priorità basate su heap binari
 
05. Algoritmi per liste:
 05.01 Liste: definizioni di base e problemi classici
 05.02 Algoritmi di visita, ricerca, inserimento e rimozione per liste
 05.03 Algoritmi di inserimento e rimozione per code
 05.04 Algoritmi di inserimento e rimozione per pile
 
06. Algoritmi per alberi:
 06.01 Alberi: definizioni di base e problemi classici
 06.02 Algoritmi di visita e ricerca per alberi binari
 06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca
 06.04 Criteri di bilanciamento per alberi binari di ricerca
 06.05 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca rosso-nero
 
07. Algoritmi per grafi:
 07.01 Grafi: definizioni di base e problemi classici
 07.02 Algoritmi di visita e ricerca per grafi
 07.03 Algoritmo di ordinamento topologico per grafi diretti e aciclici
 07.04 Algoritmo delle componenti fortemente connesse per grafi
 07.05 Algoritmo di Kruskal
 07.06 Algoritmo di Prim
 07.07  Proprietà del percorso più breve
 07.08 Algoritmo di Bellman-Ford
 07.09 Algoritmo di Dijkstra
 07.10 Algoritmo diFloyd-Warshall
 
08. Algoritmi per stringhe:
 08.01 Stringhe: definizioni di base e problemi classici
 08.02 Algoritmo ingenuo di string matching
 08.03 Algoritmo per il calcolo della distanza di edit tra stringhe
 08.04 Algoritmo per il calcolo della massima sottosequenza comune
 
09. Selezione e statistiche d'ordine:
 09.01 Definizioni di base e problemi
 09.02 Heapselect
 09.03 Selezione randomizzata
 09.04 Selezione deterministica
 
10. Tecniche algoritmiche:
 10.01 Tecnica del divide et impera
 10.02 Programmazione dinamica
 10.03 Tecnica golosa
 10.04 Tecnica per tentativi e revoche
 
11. Attività di laboratorio:
 11.01 Elementi di linguaggio C: richiami, editing, compilazione, debugging
 11.02 Generatori di numeri pseudocasuali: funzioni rand e srand
 11.03 Valutazione sperimentale della complessità degli algoritmi: timing e contatori
 11.04 Confronto sperimentale degli algoritmi di ordinamento per array 
 11.05 Confronto sperimentale degli algoritmi di ricerca per alberi binari 
 11.06 Implementazione di algoritmi su grafi: visita in ampiezza e profondità di un grafo, algoritmo di Dijkstra
 11.07  Implementazione di algoritmi su stringhe: Edit Distance e LCS

Eventuali Propedeuticità

Non vi sono propedeuticità obbligatorie. Si suggerisce di sostenere l'esame di Algoritmi e Strutture Dati dopo aver sostenuto gli esami di Programmazione Procedurale e Logica e Analisi Matematica e prima di sostenere gli esami di Sistemi Operativi, Basi di Dati, Reti di Calcolatori, Programmazione ad Oggetti e Ingegneria del Software.

Risultati di Apprendimento (Descrittori di Dublino)

Conoscenza e capacità di comprensione:
Lo studente al termine del corso acquisirà: consapevolezza dell'importanza della progettazione efficiente degli algoritmi; le conoscenze fondamentali per l'analisi delle risorse computazionali richieste da un algoritmo; i principali algoritmi e strutture dati in grado di risolvere problemi di base di natura computazionale.

Conoscenza e capacità di comprensione applicate:
Lo studente acquisirà le metodologie proprie dell'analisi e della progettazione algoritmica. In particolare sarà in grado di progettare una serie di algoritmi classici (ordinamento, ricerca, ecc.) operanti su strutture dati differenti (array, liste, alberi e grafi) ed analizzarne la complessità computazionale. La capacità di applicare queste tecniche verrà sviluppata ed affinata nelle esercitazioni di laboratorio dove una serie di algoritmi verranno analizzati, elaborati ed implementati in linguaggio C.

Autonomia di giudizio:
Lo studente  sarà in grado di applicare le metodologie proprie dell'algoritmica per la comprensione e la risoluzione di nuovi problemi di natura computazionale. Le discussioni critiche in aula e le esercitazioni serviranno a stimolare e sviluppare l'autonomia di giudizio dello studente.
 
Abilità comunicative:
Lo studente  acquisirà la capacità di esprimere i concetti fondamentali propri degli algoritmi e delle strutture dati con terminologia appropriata e rigorosa. Imparerà a descrivere i problemi inerenti l'analisi e la progettazione di algoritmi efficienti e le metodologie adottate per la loro soluzione.
 
Capacità di apprendere:
Lo studente  acquisirà la capacità di studiare ed apprendere tecniche algoritmiche e strutture dati fondamentali. Imparerà a riconoscere l'importanza delle risorse computazionali (in particolare spazio e tempo) in modo da poter sviluppare autonomamente soluzioni per nuove problematiche inerenti la progettazione efficiente di programmi. 

Materiale Didattico e Attività di Supporto

Il materiale didattico e le comunicazioni specifiche del docente sono reperibili, assieme ad altre attività di supporto, all'interno della piattaforma Moodle › blended.uniurb.it

Modalità Didattiche, Obblighi, Testi di Studio e Modalità di Accertamento

Modalità Didattiche

Lezioni teoriche ed esercitazioni di laboratorio.

Obblighi

Sebbene fortemente consigliata, la frequenza non è obbligatoria.

Testi di Studio

Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2010.

(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2009.)
Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2008.

Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2012.
Sedgewick, "Algoritmi in C", Pearson, 2015.

(Sedgewick, "Algorithms in C", Addison-Wesley, 1998.)

Modalità di
Accertamento

I risultati di apprendimento attesi verranno valutati attraverso tre tipologie di prove: progetto (da sviluppare individualmente o in gruppi di due studenti), prova scritta, prova orale. Tale modalità di accertamento delle conoscenze acquisite è dovuta, in particolare, alla volontà di verificare le capacità di conoscenza e comprensione applicate, con particolare riferimento al problem solving e all' uso efficiente delle risorse computazionali e, al contempo, alla volontà di verificare sia la capacità di sintesi dello studente che le abilità comunicative ed espressive.

Il progetto, che cambia ad ogni sessione d'esame, deve essere consegnato almeno sette giorni prima della prova scritta, viene valutato in trentesimi ed è ritenuto sufficiente se il relativo voto, che rimane valido per tutti gli appelli dell'anno accademico in cui il progetto viene consegnato, è di almeno 18/30. Qualora il progetto venga riconsegnato in un appello successivo, il voto del progetto precedentemente consegnato viene annullato. Se la riconsegna avviene nella medesima sessione, al voto del nuovo progetto consegnato viene applicata una penale di 5/30.

La prova scritta, che può essere sostenuta solo previo superamento del progetto, consiste in sette domande da svolgere in 60 minuti. Viene valutata in trentesimi ed è ritenuta sufficiente se il relativo voto, che rimane valido per il solo appello in cui la prova viene sostenuta, è di almeno 18/30.

La prova orale, che può essere sostenuta solo previo superamento delle altre due prove, consiste in ulteriori domande sul programma del corso.  Se superata, comporta un aggiustamento per eccesso o per difetto di al più 5/30 della media aritmetica dei voti delle altre due prove, determinando così il voto finale.

Note

L'insegnamento offre servizi di didattica integrativa on-line all'interno della piattaforma Moodle > elearning.uniurb.it

« torna indietro Ultimo aggiornamento: 22/09/17


Condividi


Questo contenuto ha risposto alla tua domanda?


Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

numero verde

800 46 24 46

Richiesta informazioni

informazioni@uniurb.it

Posta elettronica certificata

amministrazione@uniurb.legalmail.it

Social

Performance della pagina

Università degli Studi di Urbino Carlo Bo
Via Aurelio Saffi, 2 – 61029 Urbino PU – IT
Partita IVA 00448830414 – Codice Fiscale 82002850418
2017 © Tutti i diritti sono riservati

Top