Codice insegnamento

4S02751

Crediti

12

Coordinatore

Ugo Solitro

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Moodle Seminari 0

L'insegnamento è organizzato come segue:

Obiettivi formativi

L'insegnamento si propone fornire gli strumenti fondamentali per analizzare e risolvere problemi attraverso l'utilizzo di strumenti computazionali e, in particolare, lo sviluppo di programmi.
Scopo del corso è l'apprendimento dei principi fondamentali della programmazione imperativa e ad oggetti, dei linguaggi di programmazione e l'acquisizione delle seguenti competenze:
- comprensione e analisi dei problemi, la loro descrizione rigorosa per mezzo del linguaggio matematico e la definizione delle specifiche delle eventuali soluzioni;
- progettazione delle soluzioni e confronto di possibili soluzioni secondo diverse metodologie;
- codifica delle soluzioni per mezzo di linguaggi di programmazione sia imperativi che orientati agli oggetti;
- sviluppo di soluzioni articolate per problemi di piccole e medie dimensioni per mezzo di opportuni ambienti software;
- valutazione degli algoritmi, sia in termini di efficienza che di correttezza.

Programma

CONTENUTI

INTRODUZIONE: aspetti generali

- Problemi e soluzioni: caratterizzazione matematica, analisi di problemi descritti in linguaggio naturale e loro descrizione rigorosa nel linguaggio della matematica, specifica della soluzione.
- Modelli di computazione: modelli informali, macchina astratta, nozione di algoritmo.
- Linguaggi: introduzione ai linguaggi formali e alle grammatiche BNF, compilatore e interprete.

Attività pratica.

Ambienti di sviluppo: cenni introduttivi al sistema operativo Linux; uso di terminale, editor e ambienti di sviluppo integrato.

Linguaggi di programmazione: introduzione elementare al Python; il linguaggio Java.

PARTE I - Problemi, algoritmi e programmi.

- Principi di programmazione strutturata: costanti, variabili, espressioni; istruzioni fondamentali: assegnamento, composizione sequenziale, condizionale e iterazione, raggruppamento; struttura di un semplice programma.
- I tipi di dati. Nozione generale di tipo; rappresentazione dei dati; caratterizzazione dei tipi di dati; tipi di dati astratti.
- I tipi di dati primitivi: caratteristiche, uso e problemi; tipi di dati numerici e non; tipi enumerativi.
- Tipi di dati strutturati: array (e record), file, puntatori, stringhe, definizione di tipo.
- I sotto-programmi: funzioni, procedure e metodi; struttura di un sottoprogramma; passaggio dei parametri; regole di località e di visibilità; ricorsione.
- Introduzione agli oggetti (in Java): oggetti e classi; componenti di classe e di istanza; costruttori, campi e metodi; modificatori principali.
- Strutture dati avanzate: rappresentazione di sequenze, vettori, matrici. caratterizzazione induttiva di tipi; definizione ricorsiva di strutture dati; realizzazione concreta in Java.
- Introduzione alla programmazione ad oggetti avanzata: estensione di classi; ereditarietà e polimorfismo; interfacce e classi astratte (introduzione)

PARTE II - Analisi degli algoritmi.

- Correttezza degli algoritmi: terminazione; proprietà logiche; correttezza parziale e totale rispetto alle specifiche.
- Efficienza degli algoritmi. Introduzione alla valutazione dell'efficienza degli algoritmi: prestazioni e complessità. Elementi di complessità: misure di tempo e spazio; costo computazionale in tempo e spazio; stime asintotiche del costo computazionale; caso peggiore e caso medio; costo ammortizzato.
- Casi di studio rilevanti Sequenze statiche e dinamiche: definizione astratta; implementazione; operazioni di base; Algoritmi di ricerca (semplice e binaria), ordinamento (insertion, selection, merge, quick sort), concatenazione e fusione. Sequenze, Matrici e Vettori: implementazione, operazioni e algoritmi.
Liste: definizione astratta e implementazione; operazioni di base; introduzione a Pile e Code.
Alberi (introduzione): definizione astratta di alberi binari e implementazione; operazioni di base; alberi bilanciati e di ricerca. Introduzione ai grafi: definizione matematica; implementazione elementare.

MODALITÀ DIDATTICHE

Le attività didattiche dell'insegnamento sono strutturate indicativamente secondo lo schema seguente:

- presentazione dell'argomento della lezione;
- analisi di problemi legati all'argomento e discussione delle possibili soluzioni;
- proposta di esercitazioni di difficoltà progressiva volti alla soluzione di un problema significativo e
- risoluzione collettiva di alcuni esercizi;
- risoluzione individuale e/o di gruppo degli altri con il supporto di tutor d'aula (quando disponibili)
- correzione collettiva o, quando possibile, individuale delle esercitazioni.
- eventuale discussione sintetica finale.

Le modalità didattiche possono variare in dipendenza dell'argomento e delle risorse disponibili.

Bibliografia

Modalità d'esame

L'esame finale consiste di norma di una prova scritta, una prova pratica e un colloquio orale finale.

Le prove scritta e pratica possono essere sostituite, anche parzialmente, con attività in itinere.