ALGORITMI E STRUTTURE DATI
Prof. Giancarlo Tretola

Ricevimento in presenza: Lunedì 12:00 - 13:00
Ricevimento online: Mercoledì 19:00 - 20:00

OBIETTIVI FORMATIVI

L’insegnamento ha l’obiettivo di approfondire gli aspetti relativi a:
1. progettazione e realizzazione di algoritmi rilevanti;
2. comprensione delle strutture dati fondamentali;
3. realizzazione di algoritmi con tecniche iterative e ricorsive;
4. realizzazione di programmi in linguaggio Python;
5. valutazione dell’efficienza dei programmi implementati.

DIDATTICA EROGATIVA

N. 9 VIDEOLEZIONI ON-LINE (N. 9 UNITÀ DIDATTICHE - DELLA DURATA DI DUE ORE PER OGNI CFU)

DIDATTICA INTERATTIVA

N. 2 LEZIONI INTERATTIVE PER CFU
N. 5 DISCUSSIONI TEMATICHE SUL FORUM DIDATTICO (TOPIC) E N. 2 POST PER CFU COME DAL LINEE GUIDA SULLA DIDATTICA DEL PQA
N. 4 E-TIVITY
N. 2 TEST PER OGNI CFU CON 8 DOMANDE A RISPOSTA MULTIPLA

PROGRAMMA DEL CORSO

Introduzione alla programmazione in Python: variabili, operazioni, espressioni, istruzioni condizionali e iterative, funzioni, stringhe e gestione avanzata delle stringhe, IDLE, strumenti di sviluppo in Python.

Python Containers: i moduli Python, i tipi di dato contenitori: liste, tuple, set e dizionari, operazioni base sulle liste, tuple, set, e dizionari.

Programmazione ad Oggetti in Python: classi, oggetti e metodi in Python, astrazione, information hiding, ereditarietà e polimorfismo in Python.

Risoluzione di problemi: algoritmi e strutture dati, classi di problemi, risoluzione di problemi, progettazione top down, implementazione di algoritmi, verifica dei programmi, tecniche di testing.

Tecniche algoritmiche: tecnica del divide et impera e ricorsione, decomposizione ricorsiva, ricorsione lineare e ricorsione multipla, ricorsione mutua e ricorsione annidata, programmazione dinamica, tecnica greedy, tecnica backtracking.

Efficienza degli algoritmi: complessità computazionale, tempi di esecuzione, efficienza e complessità di un algoritmo, notazioni asintotiche, complessità computazionale di costrutti di programmazione, complessità delle funzioni ricorsive, ricorrenze notevoli.

Strutture dati di base: strutture dati dinamiche, array dinamici, pile realizzazione e operazioni, code realizzazione e operazioni.

Strutture dati avanzate: liste dinamiche, algoritmi iterativi, algoritmi ricorsivi, alberi binari, creazione, ricerca e visita ricorsiva.

Tipi di dato astratto: astrazione, tipi di dato astratto, TDA Sequenza, TDA Set, TDA Map, TDA Stack, TDA Queue.

MODALITÀ DI VERIFICA DEL PROFITTO IN INTINERE

Il grado di apprendimento degli studenti è monitorato costantemente attraverso gli strumenti e le metodologie di verifica.
In particolare, al fine di rendere fattibile la verifica e la certificazione degli esiti formativi il docente ed il tutor terranno conto del:
1. tracciamento automatico delle attività formative da parte del sistema - reporting;
2. il monitoraggio didattico e tecnico (a livello di quantità e qualità delle interazioni, di rispetto delle scadenze didattiche, di consegna degli elaborati previsti, ecc.).
3. le verifiche di tipo formativo in itinere, anche per l'autovalutazione (p. es. test multiple choice, vero/falso, sequenza di domande con diversa difficoltà, simulazioni, mappe concettuali, elaborati, progetti di gruppo, ecc.);
4. l'esame finale di profitto, nel corso del quale si tiene conto e si valorizza il lavoro svolto in rete (attività svolte a distanza, quantità e qualità delle interazioni on line, ecc.).
La valutazione, in questo quadro, tiene conto di più aspetti:
a. il risultato di un certo numero di prove intermedie (test on line, sviluppo di elaborati, ecc.);
b. la qualità e quantità della partecipazione alle attività on line (frequenza e qualità degli interventi monitorabili attraverso la piattaforma);
c. i risultati della prova finale.

Pertanto i dati raccolti saranno oggetto di valutazione da parte del docente per l'attività di valutazione dello studente.

MODALITÀ DI VALUTAZIONE E OBIETTIVI DELLA PROVA FINALE

L’accesso all’esame è subordinato al riconoscimento di frequenza, che verrà attestato con l'apposito certificato al momento della prenotazione dell'esame, che attesterà lo svolgimento delle attività didattiche di verifica in itinere e al livello del lavoro svolto nelle varie esercitazioni.
L'esame consisterà in un colloquio orale e la votazione sarà espressa in 30/30.
L'esame di profitto viene svolto in forma orale con analisi di esempi di codice Python. Lo studente riceverà dalla commissione almeno tre domande sugli argomenti descritti nel programma del Corso.
L’esame mira a valutare il raggiungimento degli obiettivi didattici. In particolare:
a) lo studente deve conoscere la sintassi del linguaggio Python e saper spiegare come si implementano programmi, moduli, funzioni e classi in Python.
b) dimostrare la conoscenza degli algoritmi fondamentali, delle strutture dati fondamentali e dimostrare le la conoscenza delle loro caratteristiche di progetto.
c) dimostrare la capacità di valutare la correttezza e complessità di un programma basato su una soluzione algoritmica e utilizzante una struttura dati.
In riferimento alla votazione verranno assegnati al massimo 10 punti per ogni obiettivo verificato di cui ai punti a, b e c.
Ai fini del superamento dell’esame è richiesto un punteggio minimo pari a 6 punti ad obiettivo.
La lode verrà assegnata nel caso in cui lo studente:
a) acquisisca il punteggio massimo assegnato a tutti gli obiettivi
b) dimostri piena autonomia nel condurre il colloquio orale
c) evidenzi punti di forza e criticità della soluzione algoritmica dei problemi.

CONOSCENZE E CAPACITÀ DI COMPRENSIONE IN TERMINI DI RISULTATI ATTESI (DESCRITTORE DI DUBLINO N. 1)

• La conoscenza degli algoritmi e strutture dati fondamentali consentirà allo studente di essere in grado di analizzare le soluzioni esistenti e valutare il loro utilizzo nell’affrontare problemi, operando per composizione di elementi consolidati.
• La conoscenza dei paradigmi di programmazione iterativa e ricorsiva consentirà allo studente di identificare la soluzione più adeguata in base alla natura del problema e dei suoi requisiti.
• La capacità di eseguire il confronto tra algoritmi sarà fondata sulla base dell caratteristiche dell’efficienza di memoria e di esecuzione che lo studente sarà in grado di valutare.

COMPETENZE AL FINE DI APPLICARE CONOSCENZA E COMPRENSIONE IN TERMINI DI RISULTATI ATTESI (DESCRITTORE DI DUBLINO N. 2)

● Lo studente sarà in grado di analizzare problemi tipici e realizzare applicazioni che li risolvano utilizzando algoritmi e strutture dati standard implementate in linguaggio Python, valutandone l’efficienza.
● Le competenze acquisite consentiranno allo studente di procedere in autonomia alla realizzazione di progetti software in Python di piccole dimensioni.

Algoritmi e strutture di dati. Astrazione, progetto e realizzazione
di Pasquale Foggia, Mario Vento
Editore: McGraw-Hill Education
Collana: Collana di istruzione scientifica
Data di Pubblicazione: marzo 2011
EAN: 9788838662621
ISBN: 8838662622

Algoritmi e strutture di dati. Astrazione, progetto e realizzazione
di Pasquale Foggia, Mario Vento
Versione digitale disponibile.

Pensare in Python
di Allen Downey
Editore: EGEA
Collana: Fuori collana
Edizione: 2
Data di Pubblicazione: maggio 2018
EAN: 9788823822641
ISBN: 8823822645

Pensare in Python,Titolo originale: Think Python: How to Think Like a Computer Scientist
Traduzione di Andrea Zanella.
Versione digitale disponibile