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. Course Syllabus
- Introduction to computer science. Von Neumann model. Memory hierarchies.
- Binary system. Conversions. Arithmetic operators. Overflow.
- The notion of algorithm. Bohm-Jacopini theorem.
- Natural languages, programming languages, pseudo-code.
- Introduction to Boolean algebra.
- Formal grammar. Backus-Naur Form (BNF).
- Machine language, Assembler, high-level languages. Compilers and interpreters. Introduction to GCC.
- Basics of C language.
- IF and SWITCH-CASE constructs.
- WHILE, DO-WHILE, and FOR constructs.
- Arrays, pointers and their operators. Structures and enumerations. Unions. Use of Typedef.
- Functions. Differences between passage of parameters by value and by reference.
- File management. Text and binary files.
- Recursive algorithms. Examples.
- Computational complexity theory. Computation complexity of simple instructions, cycles, functions (ricorsive and not). Examples.
- Search and sorting algorithms. Sequential and binary search. Bubble sort, Selection sort, Insertion sort, Shell sort, Quick sort, Merge sort. Their C implementations and their computational complexity.
- Abstract data types: lists, stacks, queues. Their C implementation. Main related algorithms and their C implementation.
- Graphs and trees. Their C implementation. Main related algorithms and their C implementation. 
