Obiettivi Formativi

Il corso ha l'obiettivo di fornire le conoscenze di base degli aspetti teorici e pratici dell'informatica.

Metodi didattici

Lezioni frontali ed esercitazioni al calcolatore.

Prerequisiti

Nessuno.

Verifiche dell'apprendimento

Prova di programmazione al calcolatore e esame orale.

Programma del Corso

- Introduzione all'informatica. Il calcolatore elettronico, macchina di Von Neumann. Gerarchie di memorie. - Sistemi numerici posizionali. Sistema binario. Conversioni di base. Operatori aritmetici nel sistema binario. Overflow. - Algoritmi, dati ed istruzioni, programmazione strutturata, Teorema di Böhm-Jacopini. - Codifica degli algoritmi, linguaggio naturale, linguaggio di programmazione, pseudo-codice. Diagramma a blocchi e di flusso. - Algebra booleana: tabelle di verità, principali operatori e loro proprietà. - Linguaggi e grammatiche. Grammatiche formali. Grammatica Backus-NaurForm(BNF). Sintassi e semantica. - Linguaggi di programmazione: linguaggio macchina, Assembler, linguaggi di alto livello. Compilatori ed interpreti. Compilatori per linguaggio C, GCC. - Caratteristiche del linguaggio C, struttura di un programma C, principali librerie. - Tipi di dato, tipi elementari. Stringhe e I/O da terminale. Operatori ed espressioni, precedenza ed associatività, overloading degli operatori, conversioni di tipo. - Istruzioni semplici, istruzioni di controllo, blocchi, regole di visibilità. Costrutto IF e costrutto SWITCH-CASE. - Costrutti WHILE, DO-WHILE, FOR. - Tipi di dato strutturato in C. Array: definizione, operatori, inizializzazione. - Gestione della memoria, Heap. Puntatori e loro operatori. Implementazione di array con puntatore. - Le strutture. Tipi enumerativi. Le unioni. Tipi di dato definiti dall'utente. - Le funzioni. Passaggio dei parametri per valore e per riferimento, utilizzo dei puntatori. - Gestione dei file, file di testo e binari, canali standard, uso dei buffer. - Algoritmi ricorsivi: funzioni ricorsive e parametri di funzioni ricorsive in C, condizione di terminazione, esempi di algoritmi ricorsivi e loro implementazione in C. - Calcolo della complessità: introduzione alla valutazione della complessità di un algoritmo, utilizzo di espressioni asintotiche per esprimere la complessità computazionale di un algoritmo e loro proprietà e regole. - Complessità computazionale di operazioni semplici, cicli e funzioni (ricorsive e non). - Esempi di calcolo di complessità computazionale di programmi in C. - Ricerca e ordinamento in strutture dati semplici. Algoritmi di ricerca: ricerca sequenziale e ricerca binaria. Loro implementazione in C e calcolo della loro complessità computazionale. - Algoritmi di ordinamento semplici e evoluti: Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Merge sort. Loro implementazione in C e calcolo della relativa complessità computazionale. - Tipi di dato astratto: liste, pile e code. Liste concatenate: ricerca, inserimento in testa, in coda e ordinato, cancellazione. Liste doppiamente concatenate: ricerca, inserimento in testa, in coda e ordinato, cancellazione. - Implementazione delle liste tramite array collegati e tramite allocazione dinamica della memoria e puntatori in C. - Implementazione di pile e code con liste concatenate e con array monodimensionali in C. Code circolari. Operazioni di push, pop e peak. Operazioni di enqueue e dequeue. - Strutture dati complesso: grafi e alberi. Definizione di grafo. Grafi orientati e non orientati. Rappresentazione dei grafi con matrici di adiacenza e liste di adiacenza in C. - Algoritmi di attraversamento dei grafi: in ampiezza e in profondità. Loro implementazione in C. - Definizione di albero come grafo aciclico. Definizione di albero binario, algoritmi di attraversamento e loro implementazione in C. - Definizione di albero binario di ricerca. Algoritmi di creazione, inserimento ordinato, cancellazione, ricerca e loro implementazione in C.