ALGORITMI E STRUTTURE DATI I
cod. 14839

Anno accademico 2017/18
1° anno di corso - Secondo semestre
Docente
Grazia LOTTI
Settore scientifico disciplinare
Informatica (INF/01)
Ambito
Discipline informatiche
Tipologia attività formativa
Caratterizzante
84 ore
di attività frontali
9 crediti
sede: PARMA
insegnamento
in ITALIANO

Obiettivi formativi

Scopo del corso è familiarizzare gli studenti con gli algoritmi, le strutture dati e con le tecniche per analizzare la loro efficienza.

Conoscenza e capacità di comprensione:
Acquisizione degli strumenti di base per l’analisi e la sintesi di soluzioni algoritmiche a problemi elementari del mondo reale. Lo studente alla fine del corso acquisirà una buona conoscenza dei principali algoritmi e delle più importanti strutture dati, usati per sviluppare software strutturato, efficiente, riusabile e pratico.

Capacità di applicare conoscenza e comprensione:
Sarà in grado di confrontare algoritmi diversi per uno stesso problema, di predire o garantire le prestazioni di un algoritmo per risolvere problemi di grandi dimensioni. Sarà in grado di studiare le limitazioni inerenti dei problemi da risolvere, organizzare e strutturare i dati da elaborare nel modo più opportuno, individuare e/o progettare algoritmi corretti ed efficienti.

Prerequisiti

- - -

Contenuti dell'insegnamento

Il corso presenta un’introduzione alle più importanti strutture dati e alle tecniche di base per la progettazione e l’analisi degli algoritmi.

Programma esteso

• Indecibilita', intrattabilita' dei problemi computazionali,
• Complessita' computazionale: modelli di calcolo, analisi di algoritmi.
• Tecnica divide et impera, relazioni di ricorrenza, Lemma fondamentale.
• Strutture dati di base: linked lists, stacks, queues, trees.
• Algoritmi di sorting basati sui confronti: Insertionsort, Mergesort, Quick-
sort, Heapsort.
• Limiti inferiori all’ordinamento e alla ricerca.
• Sorting in tempo lineare.
• Mediano and statistiche d’ordine.
• Introduzione alla programmazione dinamica e alla tecnica greedy.
• Alberi binari, alberi binari di ricerca, alberi AVL, B-alberi.
• Tabelle hash.
• Grafi, BFS,DFS, DAG, ordinamento topologico, componenti fortemente
connesse.
• Union-find, MST, algoritmo di Kruskal, algoritmo di Prim.
• Algoritmo di Dijkstra, algoritmo di Bellman-Ford.

Bibliografia

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.
• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, prima edizione, 2006

Metodi didattici

Lezioni frontali con esercitazioni. L'insegnamento viene svolto nello stesso semestere di “Fondamenti di Programmazione B”, nelle cui ore di laboratorio vengono implementate alcuni delle più significative strutture dati utilizzando il linguaggio C++.

Modalità verifica apprendimento

L'esame comprende una prova scritta ed un eventuale colloquio orale che viene effettuato per sciogliere residui dubbi di valutazione. La prova scritta consiste di alcune domande di teoria e di un certo numero di esercizi, da svolgersi senza poter consultare libri o appunti. Gli esercizi possono comportare la risoluzione di problemi che sono minime varianti di questioni viste a lezione, o richiedere la risoluzione di problemi che non coincidono con nessuno dei problemi visti a lezione, ma che possono essere risolti con le tecniche sviluppate in classe.
La sufficienza può essere raggiunta rispondendo correttamente alle domande e risolvendo correttamente gli esercizi del primo tipo.

Altre informazioni

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -

Referenti e contatti

Numero verde

800 904 084

Segreteria studenti


E. segreteria.scienze@unipr.it

Servizio per la qualità della didattica

Manager della didattica:
Dott.ssa Claudia Buga

T. 0521 902842
E. smfi.didattica@unipr.it
E. claudia.buga@unipr.it

Presidente del corso di studio

Prof. Alessandro Dal Palù
E. alessandro.dalpalu@unipr.it

Delegato orientamento in ingresso

Prof. Vincenzo Arceri
E. vincenzo.arceri@unipr.it

Delegato orientamento in uscita

Prof.ssa Chiara Guardasoni
E. chiara.guardasoni@unipr.it

Referente piani di studio

Prof. Flavio Bertini
E. flavio.bertini@unipr.it

Referente convalide

Prof. Andrea Munaro
E. andrea.munaro@unipr.it

Docenti tutor

Prof. Enea Zaffanella
E. enea.zaffanella@unipr.it

Delegati Erasmus

Prof. Andrea Munaro
E. andrea.munaro@unipr.it

Studente tutor per scambi all'estero (in definizione)
E.

Responsabile assicurazione qualità

Prof.ssa Chiara Guardasoni
E. chiara.guardasoni@unipr.it

Tirocini formativi

Referente prof. Enea Zaffanella
E. enea.zaffanella@unipr.it

Referente per le fasce deboli

Prof. Fiorenza Morini
E. fiorenza.morini@unipr.it

Studenti tutor

Tutor a.a. 2024-2025 
Dott. Saverio Mattia Merenda
Tutorato a sportello tutti i venerdì 9:00-10:30 in aula M a Matematica previo appuntamento via e-mail:
E. saveriomattia.merenda@studenti.unipr.it
 

Rappresentanti degli studenti in CCSU

  • Lorenzo Copelli
  • Alessandro Frasconi
  • Marcello Galli
  • Samuel Seligardi