In questa pagina sono elencati gli argomenti trattati in ogni
lezione.
I codici C mostrati come esempi e i file powerpoint mostrati a lezione si trovano nella scheda file del canale Lezioni del corso su Teams.
I testi degli esercizi
assegnati in laboratorio si trovano nella sezione "Laboratorio".
|
Lez1
Presentazione del corso.
Introduzione all'informatica e centralità del concetto di algoritmo. L'algoritmo di Euclide: dalla descrizione in linguaggio naturale alla codifica in linguaggio C. |
||
|
Lab1
Conoscenza del laboratorio e trascrittura di semplici programmi e loro compilazione.
Vedi Esercizi Proposti
Codice Lab01
|
||
|
Lez2
Analisi di semplici programmi in C. Il primo (classico!)
programma in C: Scrivere un messaggio sullo schermo.
Il concetto di variabile in un programma. Sintassi per gli identificatori e per la dichiarazione di variabili. Istruzione di assegnamento. Esempio: Scambiare il valore di due variabili. Rappresentazione dei dati in C. I 5 tipi elementari char, int, float, double . Rappresentazione numeri in sistema binario, (decimale) e esadecimale. Occupazione in memoria dei vari tipi di dati. Operatore unario sizeof( ). |
||
|
Lab2
Vedi Esercizi Proposti
Codice Lab02
|
||
|
Lez3
Operatore unario sizeof( ) Espressioni aritmetiche e logiche. Operatori aritmetici, condizionali e logici in C. Sintassi dell'istruzione di selezione if Istruzioni composte. Esempi. la struttura di ripetizione while . Somiglianze e differenze tra struttura di selezione if e la struttura di ripetizione while . |
||
|
Lab3
Vedi Esercizi Proposti
Codice Lab03
|
||
|
Lez4
La programmazione strutturata e il controllo del flusso di un programma. Il Teorema di Boehm e
Jacopini. La struttura di selezione if ...else . Esempi di utilizzo di strutture if ...else nidificate. Il problema del dangling else (else appeso). La struttura di ripetizione do ...while . Equivalenza tra le due strutture di ripetizione introdotte. |
||
| Lab4 Vedi Esercizi Proposti Codice Lab04 | ||
|
Lez5
Operatori di incremento e decremento ++, --.
Operatori di assegnamento +=, -=, *=. La ripetizione definita: la struttura for . Esempi. Equivalenza tra le strutture di ripetizione introdotte. Usi particolari dei cicli for quando mancano alcune condizioni. Esempi. Uscita forzata da una istruzione: break e continue . Uscita forzata da un programma: exit e return . Correzione gli esercizidel lab03. |
||
|
Lab5
Vedi Esercizi Proposti
Codice Lab05
|
||
|
Lez6
La struttura di selezione switch . Esempi. Ulteriori cenni sui tipi di dati in C ed esempi. Il tipo char. Parametri di conversione per printf e scanf per il tipo char. Funzioni getchar( ),putchar( ). Problemi possibili nell'input di caratteri alternato a input numerici. Codifica delle informazioni non numeriche: codice ASCII e sue estensioni. Esempi. Correzione gli esercizidel lab03. |
||
| Lab6 Vedi Esercizi Proposti Codice Lab06 | ||
|
Lez7
Introduzione alle funzioni nei programmi in C. Sintassi.
Meccanismo del
passaggio dei parametri e variabili locali alle funzioni. Funzioni void. Esempi.
Correzione degli esercizi della settimana precedente. |
||
|
Lab7
Vedi Esercizi Proposti
Codice Lab07
|
||
|
Lez8
Definizione formale di funzioni nei programmi in C. Sintassi. Meccanismo del passaggio dei parametri e variabili locali alle funzioni. Esempio quadratiVari.c . Funzioni della libreria matematica. Generatore di numeri casuali. Esempi: dado1.c, dado2.c,lancidado.c. Correzione degli esercizi della settimana precedente. |
||
| Lab8 Vedi Esercizi Proposti Codice Lab08 | ||
|
Lez9
Funzioni ricorsive. Vantaggi e svantaggi. Esempi.
La struttura dati array in C. Dichiarazione e inizializzazione di array. Allocazione della memoria per una variabile di tipo array. Passaggio di array a
funzioni. Esempi. |
||
|
Lab9
Vedi Esercizi Proposti
Codice Lab09
|
||
| Lez10 Riepilogo sulla struttura dati array. Riflessioni sull'utilizzo di array in casi particolari. Calcolo frequenza lanci di un dado. Il crivello di Eratostene. | ||
| Lab10 Vedi Esercizi Proposti Codice Lab10 | ||
|
Lez11
Il problema del searching . Operazioni di ricerca su un array:
ricerca sequenziale e
ricerca binaria (in versione iterativa e ricorsiva). Calcolo della
complessitita' come numeri di confronti effettuati nel caso peggiore. Il problema dell'ordinamento. Algoritmi di ordinamento su vettori. Algoritmo SelectionSort come iterazioni di ricerca del minimo o del massimo. Dimostrazione della correttezza e analisi della complessità a partire dalla complessità dell'algoritmo che calcola il minimo tra n numeri. Algoritmo BubbleSort. Dimostrazione della correttezza e analisi della complessità. Valutazione sperimentale dell'algoritmo BubbleSort e nuova versione che riconosce quando il vettore è già ordinato. Algoritmo InsertionSort. Dimostrazione della correttezza e analisi della complessità. |
||
|
Lab11
Vedi Esercizi Proposti
Codice Lab11
|
||
|
Lez12
Cenni su analisi della complessità di un algoritmo. Notazione O e Ω per indicare limiti superiori e inferiori della complessità di algoritmi e problemi. Esempi di tempi di calcolo in relazione alle funzioni f(n)= n, nlogn, n^2, n^3, 2^n. Il gioco "indovina il numero" e un algoritmo di complessità logaritmica per risolverlo. Le torri di Hanoi: l'algoritmo ricorsivo e dimostrazione che la complessità è esponenziale. Osservazioni e commenti sul problema del baricentro di un vettore dal punto di vista della complessità degli algoritmi proposti in laboratorio. |
||
| Lab12 Vedi Esercizi Proposti Codice Lab12 | ||
|
Lez13
Array bidimensionali (matrici). Esempi. Definizione di lower bound di un problema. Albero di decisione e calcolo del lower bound per il problema del sorting. La tecnica algoritmica del divide et impera e una sua applicazione al problema dell'ordinamento: l'algoritmo MergeSort . Descrizione informale, codice C e calcolo esplicito dei confronti effettuati. Analisi complessità. |
||
|
Lab13
Vedi Esercizi Proposti
Codice Lab13
|
||
|
Lez14
L'algoritmo QuickSort . Descrizione informale e codice C.
Introduzione alle variabili puntatore. Esempi. Operatori & e *. Correzione degli esercizi del Lab09. Correzione dell'esercizio sul Crivello di Eratostene. |
||
|
Pausa didattica
|
||
| Lab14 Vedi Esercizi Proposti Codice Lab14 | ||
| Lez15 Lettura e scrittura su file di testo e ascii. | ||
|
Lab15
Vedi Esercizi Proposti
Codice Lab15
|
||
| Lez16 Introduzione alle stringhe come array di char. Esempi. | ||
| Lab16 Vedi Esercizi Proposti Codice Lab16 | ||
|
Lez17
Variabili puntatore. Esempi di variabili puntatore. Assegnazione di variabili puntatore. Funzioni malloc e free . Aritmetica sui puntatori. Esempi di definizione di array attraverso la funzione malloc.
Puntatori e loro relazioni con gli array.
Esempi di stampa degli indirizzi degli elementi di un array. (file provapunt.c e vettoripunt.c ) Tipo di dati "stringhe" come array di char . Esempi di inizializzazione, stampa e copia. | ||
|
Lab17
Vedi Esercizi Proposti
Codice Lab17
|
||
|
Lez18
Le strutture in C: dichiarazioni di variabili tipo
struct . Inizializzazioni di variabili struct. Operazioni
su variabili struc, operatore punto e operatore freccia. Parola
chiave typedef . Esempio di una struttura che rappresenta una carta da gioco. Programma che inizializza un mazzo di carte e poi lo "mescola". (file mazzoDiCarte.c). Esempio di programma che simula un piccolo campionato di 6 squadre e determina il vincitore. |
||
| Lab18 Vedi Esercizi Proposti Codice Lab18 | ||
| Lez19 Strutture autoreferenzianti per creare strutture dati dinamiche. Definizione di un nodo-lista. Definizione di una lista come puntatore ad un nodo-lista. Stampa di una lista. Operazioni di inserimento in testa e in coda in versione con lista passata per riferimento. Esempi. | ||
|
Lab19
Vedi Esercizi Proposti
Codice Lab19
|
||
|
Lez20
Riepilogo su definizione di una lista come puntatore ad un nodo-lista e alle operazioni di stampa e inserimento in testa e in coda. Funzione per inserire un elemento in una lista mantenendola ordinata. Operazioni di cancellazione di un elemento in versione con lista passata per riferimento o per valore. Esempi. ESERCIZIO per casa: Utilizzando i codici visti a lezione nelle slides (vedi Teams) integrare il programma eseListaBase0.cpp con le seguenti funzioni di inserimento in testa e in coda e cancellazione. Poi nel main richiedere due valori all'utente e inserirli rispettivamente in testa e in coda alla lista generata random. Richiedere all'utente un valore da cancellare e richiamare la funzione di cancellazione. Stampare la nuova lista. |
||
| Lab20 Vedi Esercizi Proposti Codice Lab20 | ||
|
Lez21
Strutture dati astratte "pila" e
"coda". Implementazioni in C usando strutture a puntatori e usando vettori. Esempi. Esempi di utilizzo della struttura dati pila. Algoritmo di simulazione di una coda con due pile e complessità. (codice pile_coda.c). Correzione esercizi del laboratorio precedente. |
||
|
Lab21
Vedi Esercizi Proposti
Codice Lab21
|
||
| Lez22 Commento a vari codici per problemi "tipici" su liste. Analizzati i file OrdinaLista.c, listarovesciata.c, listasenzaprimi.c, fuzioneliste.c, eselistaScambiaMeta.c disponibili nella sezione materiale del corso della classe Teams. | ||
| Lab22 Vedi Esercizi Proposti Codice Lab22 | ||
|
Lez23
Cenni su struttura dati albero binario e sua implementazione in C con una struttura nodo con due puntatori. Visita in pre-ordine, in-ordine e post-ordine. (File: alberiBinari.cpp). Visite di alberi in ampiezza
(BFS) e in profondita' (DFS): implementazione utilizzando come
struttura dati di appoggio una coda e una pila. (File:
visitaAlbero.cpp). Cenni su struttura dati grafo. Correzione dell'esercizio "maxsum". NOTA: Lezione fatta alla lavagna; non sono disponibili slides. |
||
| Lab23 LABORATORIO CANCELLATO | ||
| Lez 24 LEZIONE CANCELLATA | ||
|
Pausa vacanze di Natale
|
||
|
Lab24
SIMULAZIONE DI UNA PROVA D'ESAME
(il testo è stato fornito in aula stampato) |
||
| Lez 25 Esercizi su liste | ||
| Lab25 Vedi Esercizi Proposti Codice Lab25 | ||
| Lez 26 Correzione e commento degli esercizi del laboratorio | ||
| ESONERO PRIMA PARTE (?) |