Ateneo - UPO

Gestione di stutture dati dinamiche.
Iterazione.
Ricorsione.
Algoritmi classici di ordinamento
Tipi dati astratti: Code e liste

Paul Deitel, Harvey Deitel “Il linguaggio C. Fondamenti e tecniche di programmazione”. Pearson Italia, 2013

Brian W. Kernighan, Dennis M. Ritchie "Il linguaggio C. Principi di programmazione e manuale di riferimento" Pearson Italia

Permettere agli studenti l’acquisizione di concetti di programmazione avanzati, approfondendo il concetto di programmazione iterativa ed introducendo il concetto di programmazione in ricorsione.
Consentire la valutazione delle prestazioni di un algoritmo iterativo e/o ricorsivo attraverso il concetto di complessità asintotica.
Acquisire il concetto di gestione della memoria dinamica attraverso l’uso del linguaggio C e la sua applicazione per l’uso di strutture dati avanzate come le liste collegate, le code e le pile.
Comprendere il funzionamento e la complessità di due tra i principali algoritmi ricorsivi di ordinamento (quicksort e mergesort).

Lo studente deve aver superato Programmazione 1

Lezioni frontali, esercitazioni in aula e in laboratorio

L'attività in laboratorio richiede una partecipazione attiva e individuale degli studenti, che in tal modo sviluppano abilità pratiche (le capacità di realizzare un programma). La partecipazione attiva permette una verifica del modo in cui gli argomenti vengono recepiti.

Esame scritto/ in laboratorio. 6 Quesiti. Due domande mirate a valutare le conoscenze teoriche: una domanda sugli argomenti di teoria trattati durante il corso, ed un esercizio sulla simulazione di un algoritmo mediante i record di attivazione. Sviluppo in laboratorio di un programma che comprende 4 esercizi orientati a testare le capacità e le conoscenze inerenti alla programmazione iterativa e ricorsiva, all’uso delle liste, alla gestione della memoria dinamica. Per superare la prova lo studente deve almeno raggiungere un punteggio pari al 60% del punteggio massimo raggiungibile per entrambe le parti (prova scritta e di laboratorio).

- puntatori in C e loro uso per la realizzazione di liste
- funzioni interattive sulla liste:
- gestione di una singola lista
- gestione di più liste
- ricorsione:
- definizione e concetti di base
- simulazione di funzione ricorsive mediante record di attivazione
- un esempio complesso: le torri di Hanoi
- funzioni ricorsive su liste:
- gestione di una singola lista
- gestione di più liste
- funzioni ricorsive di ordinamento:
- QuickSort
- MergeSort
- Tipi dati astratti:
- Pile
- code

Al termine del corso, lo studente deve essere in grado, dato un problema di programmazione (per gestire la struttua dinamica lista), di individuarne un algoritmo risolutivo sia iterazione sia in ricorsione, implementarlo in linguaggio C, eseguirlo al calcolatore.

Conoscenza e comprensione: programmazione in iterazione, programmazione in ricorsione, la struttura dinamica lista.

Capacità di applicare conoscenza e comprensione: dato un problema inerente alla struttura dinamica lista,
- definire un algoritmo iterativo che trasforma i dati di input nei dati di output, seguendo i costrutti della programmazione;
- definire un algoritmo ricorsivo che trasforma i dati di input nei dati di output, seguendo i costrutti della programmazione;
- scrivere al calcolatore il programma sorgente che implementa l'algoritmo, utilizzando un linguaggio di programmazione (C);
- compilare, eseguire e testare tale programma al calcolatore.

Autonomia di giudizio: in modo autonomo lo studente deve riuscire definire ed implementare un'algoritmo per risolvere un problema inerenti alla gestione di strutture dinamiche nel linguaggio di programmazione (C), a valutarne la complessità, e compilare ed eseguire il programma.

Abilità comunicative: lo studente deve riuscire a definire un algoritmo sia in iterazione sia in ricorsione, e deve sapere presentare il suo costo espresso come complessità in tempo e spazio.

Capacità di apprendimento: lo studente deve essere capace di apprendere come si definiscae un algoritmo a partire dal problema sia in iterazione sia in ricorsione, valutarne i costi (complessità in tempo e spazio) e come si implementa tale algoritmo in C.