FONDAMENTI DI PROGRAMMAZIONE F - O

Modulo PROGRAMMAZIONE II

Il modulo Programmazione II del corso Fondamenti di Programmazione si concentra sulla formazione di studenti competenti nella programmazione avanzata in ANSI C, capaci di progettare, valutare ed implementare algoritmi e strutture dati appropriate alla risoluzione dei problemi, nonché di comunicare utilizzando il gergo del settore. Il modulo include, quindi, cenni alla teoria della complessità e applicazione diretta ad algoritmi su strutture dati lineari. Inoltre, sono presentati problemi e soluzioni su strutture non lineari.

Conoscenza e capacità di comprensione (knowledge and understanding)

Gli studenti acquisiranno una solida conoscenza e comprensione delle strutture dati lineari e gerarchiche fondamentali, tra cui liste, code e alberi binari di ricerca, insieme alla complessità computazionale delle operazioni su di esse ed agli algoritmi di ricerca e ordinamento. Saranno in grado di dimostrare una comprensione approfondita dei concetti legati alle strutture dati dinamiche, inclusi i puntatori e la loro gestione.

• Conoscenza delle principali strutture dati dinamiche e comprensione dei meccanismi di funzionamento 
• Conoscenza delle tecniche di ricerca e ordinamento
• Conoscenza dei rudimenti di complessità computazionale

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding)

Gli studenti saranno in grado di applicare le conoscenze acquisite nella progettazione e nell'implementazione di soluzioni pratiche, usando il linguaggio ANSI C, utilizzando efficacemente le strutture dati, gli algoritmi trattati nel corso e gli strumenti a disposizione. Saranno, infine, in grado di risolvere problemi complessi utilizzando queste conoscenze.

• Il corso promuoverà lo sviluppo di competenze di progettazione, consentendo agli studenti di progettare soluzioni efficienti e ben strutturate che soddisfano requisiti specifici. Saranno in grado di pianificare e implementare in modo efficace l'uso di strutture dati dinamiche nei loro progetti.
• Capacità di risolvere problemi che utilizzano la memoria dinamiche e le struttura dati dinamiche (quali liste, code ed alberi binari), scrivere l’algoritmo risolutivo e implementarlo usando il linguaggio ANSI C
• Capacità di analizzare il codice e correggere gli errori durante le fasi di sviluppo e realizzare una applicazione funzionante
• Capacità di ricerca dell’errore (debug) avanzata nel contesto di un ambiente di sviluppo (IDE)

Capacità di apprendimento (learning skills)

Gli studenti svilupperanno competenze nell'analisi critica delle prestazioni degli algoritmi e nella valutazione della complessità computazionale. Saranno in grado di valutare e confrontare soluzioni basate su algoritmi e strutture dati in base a criteri di tempo e spazio.

• Lo studente è in grado di trovare la migliore soluzione ad un problema tenendo conto anche dell’efficacia e dell’efficienza, definire l’algoritmo, codificarlo e garantirne il funzionamento 
• Essere in grado di utilizzare le conoscenze e competenze apprese per affrontare in maniera metodologica problemi complessi

Abilità comunicative (communication skills)

Gli studenti svilupperanno abilità di comunicazione attraverso la descrizione chiara e accurata, usando gli strumenti formali più adatti, delle loro soluzioni software e la capacità di comunicare efficacemente concetti legati alle strutture dati e agli algoritmi con i loro colleghi e con il docente. Saranno in grado di presentare le loro idee e soluzioni in modo chiaro e persuasivo.

• Lo studente acquisisce la conoscenza del linguaggio informatico e della terminologia tecnica

Cenni di Complessità Computazionale

• Efficienza dei programmi.

• Valutazione dell’efficienza di un algoritmo.

• Le notazioni O e Ω per valutare la complessità di un programma

Algoritmi di Ricerca e Ordinamento

• Algoritmi di ricerca

• Algoritmi di ordinamento: selection sort, insertion sort, bubble sort, quick sort e merge sort

Tipi di Dato Astratto (TDA) e loro implementazione in C

• Introduzione ai Tipi di Dato Astratto (TDA)

• Tipi di dato astratto lineari e gerarchici

• Risoluzione di problemi tramite TDA

• Traduzione dei Tipi di Dato Astratto in Tipi di Dati Concreti (TDC), tramite l’utilizzo del linguaggio ANSI C

• Scrittura di applicativi in ANSI C che sfruttino i TDA e le loro implementazioni

Strutture dati lineari 

• Liste e liste ordinate

• Definizione della ADT

• Rappresentazione sequenziale, collegata e doppiamente collegata

• Implementazione con allocazione statica e dinamica

• Code

• Definizione della ADT

• Rappresentazione sequenziale, collegata

• Implementazione con allocazione statica e dinamica

• Pile

• Definizione della ADT

• Rappresentazione sequenziale, collegata

• Implementazione con allocazione statica e dinamica

Strutture dati non lineari

• Alberi

• Concetti generali e definizioni

• Definizione della ADT

• Alberi binari e binari di ricerca

• Concetti generali e definizioni

• Definizione della ADT

• Implementazione delle operazioni principali

• Dizionari (Tabelle Hash)

• Concetti generali e definizioni

• Definizione della ADT

• Implementazione delle operazioni principali

• Grafi

• Concetti generali e definizioni

• Definizione della ADT