Dettagli sull'Insegnamento per l'A.A. 2013/2014

Prerequisiti

Non ci sono prerequisiti informatici obbligatori, tuttavia sarebbe auspicabile una cosiddetta alfabetizzazione informatica (capacità di lavorare con personal computer e sistemi operativi basati su finestre ed essere in grado di scrivere un testo. Inoltre sono utili nozioni di base di algebra e analisi matematica in quanto sono utilizzate durante il corso per progettare programmi per risolvere semplici problemi matematici.

Obiettivi

Il corso è finalizzato all'acquisizione dei concetti fondamentali dell'informatica, senza trascurare gli aspetti sperimentali della disciplina e la sua applicazione immediata. Si inizia con una descrizione del sistema informatico in generale per poi concentrarsi sulle tecniche di programmazione “ad alto livello” con lo scopo di far maturare negli studenti l’abilità a progettare programmi. Il linguaggio di riferimento sarà il C++, anche se i concetti presentati nel corso sono indipendenti dal linguaggio e facilmente applicabili in qualsiasi linguaggio imperativo come Pascal o Java. Nel corso si affronta inoltre lo studio degli algoritmi fondamentali, quali i principali algoritmi di ricerca e ordinamento con il calcolo del tempo di esecuzione.

Sillabo

• 1. Architettura dei sistemi informatici. Processi e processori. Problemi, algoritmi e programmi. Linguaggi di programmazione. Architettura del calcolatore. Modello di von Neumann. Sistemi numerici posizionali a base fissa. Conversioni di base. Rappresentazione di numeri negativi in modulo e segno e in complemento a due. Rappresentazione di numeri reali in virgola mobile normalizzata. Codice ASCII. Algebra di Boole e principali funzioni logiche. Ambiente di programmazione Dev-C++.
• 2. Elementi di programmazione. Sviluppo di algoritmi. Concetto di variabile. Operazioni elementari: lettura, scrittura, assegnazione e confronto. Diagrammi di flusso. Pseudo-codice. Struttura di controllo se-allora-altrimenti. Cicli con pre-condizione e post-condizione. Strutture di controllo finché-esegui e esegui-finché. Progettazione di algoritmi con cicli. Controllo sui dati di input. Traduzione in C++. Costrutti base del C++. Struttura di un programma. Parte dichiarazioni e parte istruzioni. Dichiarazione di variabili. Classificazione dei tipi. Tipi semplici, rappresentazione interna e operazioni. Espressioni numeriche e condizionali. Istruzione di assegnazione. Istruzione composta. Selezione binaria. Funzioni standard di ingresso/uscita. Istruzioni cicliche (WHILE, DO-WHILE, FOR). Costruzione di cicli annidati. Selezione n-aria.
• 3. Programmazione con tipi strutturati. Tipo array: definizione e rappresentazione in memoria. Dichiarazioni di tipo con typedef. Programmi su vettori. Array bidimensionali. Programmi su matrici. Tipo string. Tipo struct. Tipo file. Primitive per la gestione sequenziale dei files.
• 4. Programmazione con funzioni. Sottoprogrammi. Progettazione top-down. Parametricità. Dichiarazione di funzioni. Variabili globali. Variabili locali. Parametri formali e attuali. Passaggio di parametri per riferimento e per valore. Uso della memoria. Ciclo di vita delle variabili. Visibilità delle variabili. Mascheramento di variabili. Ricorsione.
• 5. Efficienza dei programmi. La funzione t(n). Modello di costo. Calcolo della t(n) per programmi iterativi. Caso migliore, caso peggiore, e caso medio. Complessità computazionale. Notazione asintotica , , . Delimitazioni alla complessità di un problema. Calcolo della t(n) per programmi ricorsivi. Soluzione dell’equazione di ricorrenza per il fattoriale e per i numeri di Fibonacci.
• 6. Algoritmi fondamentali. Ricerca sequenziale. Ricerca binaria. Inserimento e cancellazione in un array ordinato. SelectionSort. InsertionSort. Bubblesort. Mergesort. Quicksort: analisi della complessità nel caso migliore e nel caso peggiore.
• 7. Programmazione con puntatori. Gestione statica e gestione dinamica della memoria. Tipo puntatore. Operazioni con puntatori: assegnazione, new, delete, riferimento, dereferenziazione. Costante null. Uso dei puntatori. Creazione dinamica di array. Similitudine tra array e puntatori. Creazione dinamica di matrici. Strutture collegate in memoria dinamica. Liste collegate con puntatori. Programmi su liste collegate.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Testi di riferimento

• E. Clementini, Fondamenti di informatica: Programmazione strutturata in C++ , Carocci Editore. 2006.    

Modalità d'esame

Programmi da scrivere a casa e caricare online. Prova scritta e orale.

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020