9797558 - FONDAMENTI DI PROGRAMMAZIONE A - E
Modulo PROGRAMMAZIONE II
Risultati 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 2 prevede una prova in itinere, che consiste:
Nello sviluppo di una applicazione al calcolatore della durata, di norma, di 120 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, di 120 minuti
Alla prova viene assegnato un punteggio massimo di 23 punti.
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
Il voto finale è dato dalla somma dei voti conseguiti nelle due prove
Le prove di entrambi i moduli potranno essere svolte nello stesso appello
Esempi di domande e/o esercizi frequenti
English version