FONDAMENTI DI PROGRAMMAZIONE A - EModulo PROGRAMMAZIONE II
Anno accademico 2023/2024 - Docente: Vincenza CARCHIOLORisultati di apprendimento attesi
l 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)
Questo insegnamento mira a dotare gli studenti della capacità di sfruttare in modo efficace le risorse disponibili, tra cui le funzioni della libreria standard ANSI C e gli ambienti di sviluppo integrati con particolare enfasi agli strumenti di ricerca degli errori quali il debugger. Gli studenti impareranno a comprendere e gestire le risorse di memoria (sia di massa che centrale) in modo appropriato, in particolare durante l'utilizzo delle strutture dati dinamiche.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
Modalità di svolgimento dell'insegnamento
Il corso prevede come metodo di insegnamento principale le lezioni frontali per acquisire le conoscenze teoriche di base e tutti gli elementi sintattici e lo svolgimento di esercitazioni, da svolgere anche in modo autonomo, proposte dal docente per acquisire la capacità di risolvere i problemi, applicare la conoscenza e utilizzare gli ambienti e le metodologie di sviluppo.
Il docente propone, inoltre, delle esercitazioni individuali che consistono nella soluzione di un problema che lo studente deve affrontare in autonomia che vengono successivamente corrette o discusse in classe.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte le necessarie variazioni rispetto a quanto dichiarato in precedenza, al fine di rispettare il programma previsto e riportato nel syllabus.
Prerequisiti richiesti
Frequenza lezioni
La frequenza non è obbligatoria, seppure fortemente consigliata, per sostenere con successo la prova di esame.
Lo studente è tenuto a frequentare almeno il 70% delle lezioni del corso per poter sostenere la prova in itinere del modulo.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza i requisiti per la partecipazione alle prove in itinere potranno essere modificati.
Contenuti del corso
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
Testi di riferimento
[BeGu] Bellini, Guidi. Linguaggio C. Guida alla programmazione. McGraw-Hill
[Pel] Pellegrino Principe. C guida alla programmazione. Apogeo
Programmazione del corso
Argomenti | Riferimenti testi | |
---|---|---|
1 | Cenni di Complessità Computazionale | dispense |
2 | Algoritmi di Ricerca e Ordinamento | dispense |
3 | Tipi di Dato Astratto (TDA) e loro implementazione in C | dispense |
4 | Liste e liste ordinate | Disense |
5 | code | Dispense |
6 | Pile | Dispense |
7 | Alberi | Dispense |
8 | Alberi binari e binari di ricerca | Dispense |
9 | Dizionari | Dispense |
10 | Grafi | Dispense |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
Prova in itinere
Il modulo prevede una prova in itinere, che consiste:
Nello sviluppo di una applicazione al calcolatore della durata, di norma, da 60 a 90 minuti
In una prova orale, il cui accesso è subordinato al superamento della prova al calcolatore.
La partecipazione alla prova in itinere è subordinata:
Al superamento del primo modulo
Alla frequenza di almeno il 70% delle lezioni del modulo
La prova in itinere si svolgerà al termine del modulo.
Prova finale del modulo 2
La prova finale del modulo consiste:
Nello sviluppo di una applicazione al calcolatore della durata, di norma, da 60 a 90 minuti
In una prova orale, il cui accesso è subordinato al superamento della prova al calcolatore
Prova dell’insegnamento
Consiste nel superamento delle prove finali del modulo 1 e del modulo 2
Le prove di entrambi i moduli potranno essere svolte nello stesso appello