Informatica 1

Laboratorio di Programmazione & Informatica 1
A.A. 2017-2018

Diario delle lezioni

In questa pagina sono elencati gli argomenti trattati in ogni lezione.
I codici C mostrati come esempi si trovano nella seguente cartellaEsempi. I nomi dei programmi contengono il riferimento al numero della lezione in cui sono stati mostrati.
I testi degli esercizi assegnati in laboratorio si trovano nella sezione "Laboratorio".

Data Ora Argomento

MAR 6/3/18 9-11 L1 Presentazione del corso.
Introduzione all'informatica e centralità del concetto di algoritmo. Lucidi.
Lettura di approfondimento.

Mar 6/3/18 14-16 L2 Il primo (classico!) programma in C: scrivere un messaggio sullo schermo.
Il concetto di variabile in un programma. Identificatori per le variabili.
Il secondo programma: "sommare due numeri interi e scrivere il risultato sullo schermo.
Il terzo programma (variante): "Richiedere due numeri interi all'utente e stampare sullo schermo la loro somma".
LABORATORIO 1: Esercizi Proposti

GIO 8/3/18 9-11 L3 Cenni sulla struttura di un computer. Lo schema di Von Neumann.
Cenni sul file system: alcune istruzioni per la gestione dei files da finestra di sistema in unix e windows Le fasi di compilazione ed esecuzione di un programma in C.
Iniziare a scrivere un programma: direttive del preprocessore, e funzione main. Sintassi per gli identificatori e per la dichiarazione di variabili. Istruzione di assegnamento. Esempio: Scambiare il valore di due variabili.
Lucidi.

GIO 8/3/18 11-13 I1 Presentazione della parte di Teoria dei linguaggi. Brevi cenni storici sull'inizio dell'Informatica Teorica. Linguaggi formali: alfabeto, parola, linguaggio. Esempi. I problemi decisionali visti come un test di appartenenza di una data parola a un dato linguaggio. Definizione formale delle operazioni di concatenazione e star tra parole e tra linguaggi. Esempi.

MAR 13/3/18 9-11 L4 Rappresentazione dei dati in C. I 5 tipi elementari char, int, float, double e i modificatori short, long, long long, signed, unsigned . Rappresentazione numeri in sistema binario, (decimale) e esadecimale. Occupazione in memoria dei vari tipi di dati. Problemi di approssimazione nella rappresentazione dei numeri reali.
Operatore unario sizeof( ) .
Lucidi.

MAR 13/3/18 14-16 L5 Espressioni aritmetiche e logiche. Operatori aritmetici, condizionali e logici in C. La programmazione strutturata e il controllo del flusso di un programma. Il Teorema di Bohm e Jacopini.
La struttura di selezione if e la struttura di ripetizione while .
Lucidi.
LABORATORIO 2: Esercizi Proposti

GIO 15/3/18 09-11 L6 La struttura di selezione if ...else . Esempi di utilizzo di strutture if ...else nidificate. Il problema del dangling else (else appeso). Problema: trovare il max tra 3 numeri utilizzando 2 confronti. Problema: ordinare 3 numeri utilizzando 3 confronti. Lucidi.
LABORATORIO 3: Esercizi Proposti

GIO 15/3/18 11-13 I2 Presentazione del modello "automa a stati finiti". Definizione formale di automa e di linguaggio accettato. Rappresentazione di un automa tramite grafo delle transizioni. Esempi.
Esercizi assegnati:
Determinare un automa finito per ciascuno dei seguenti linguaggi:
Parole sull'alfabeto Σ ={a,b} che terminano per abba
Parole sull'alfabeto Σ ={a,b} che iniziano per bb
Parole sull'alfabeto Σ ={a,b} che contengono come fattore abba
Parole sull'alfabeto Σ ={0,1} che corrispondono a numeri in binario che sono multipli di 5.
Parole sull'alfabeto Σ ={a,b} il cui quarto elemento da destra sia a.
Parole sull'alfabeto Σ ={a,b} il cui quinto elemento da destra sia a.

MAR 20/3/18 9-11 L7 La struttura di ripetizione do ...while . Equivalenza tra le due strutture di ripetizione introdotte. Operatori di incremento e decremento ++, --. Operatori di assegnamento +=, -=, *=. La ripetizione definita: la struttura for . Esempi. Equivalenza tra le strutture di ripetizione introdotte.
Correzione di alcuni esercizi del Laboratorio 2. Lucidi.

MAR 20/3/18 14-16 L8 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 .
Lucidi.
LABORATORIO 4: Esercizi Proposti

GIO 22/3/18 14-16 L9 La struttura di selezione switch . Esempi.
Correzione di alcuni esercizi del Laboratorio 3 Lucidi.
LABORATORIO 5: Esercizi Proposti

GIO 22/3/18 11-13 I3 Automa deterministico per il linguaggio delle parole il cui quarto simbolo a partire da destra e' una a. Proposizione: L'automa deterministico per il linguaggio delle parole il cui n-esimo simbolo da destra e' una a ha almeno 2^n stati. Dimostrazione.
Automa finito non deterministico: definizione ed esempi. Definizione della funzione di transizione estesa e di linguaggio accettato. Definizione di automi equivalenti. Teorema di equivalenza tra automi finiti non deterministici e deterministici.
Esercizi assegnati:
Determinare un automa finito non deterministico per ciascuno dei seguenti linguaggi e poi determinizzarlo applicando la costruzione per sottoinsiemi:
Linguaggio sull'alfabeto {a,b} di tutte le parole che terminano per abba.
Linguaggio sull'alfabeto {a,b} di tutte le parole che contengono sia aa che bb.

MAR 27/3/18 9-11 L10 Definizione di funzioni nei programmi in C. Sintassi. Meccanismo del passaggio dei parametri e variabili locali alle funzioni. Esempio "quadratiVari.c". Lucidi.
LABORATORIO 6: Esercizi Proposti

MAR 27/3/18 14-16 L11 Funzioni della libreria matematica. Generatore di numeri casuali. Esempi: dado1.c, dado2.c,lancidado.c.
Calcolo di una funzione funzione definita come limite di una serie. Esempio dell'approssimazione della radice quadrata. Esempi: apprRadice1.c, apprRadice2.c.
Correzione di alcuni esercizi del Laboratorio 4 e 5. Lucidi.

29/3/18 e 3/4/18 vacanze di Pasqua

GIO 5/04/18 9-11 L12 Parametri e variabili locali di una funzione. Stack delle chiamate di funzione. Funzioni ricorsive. Esempi. La torre di hanoi.
Lucidi.
LABORATORIO 7: Esercizi Proposti

GIO 5/04/18 11-13 I4 Teorema di equivalenza tra automi finiti non deterministici e deterministici. Costruzione per stati raggiungibili. Automa finito con epsilon-transizioni. Definizioni ed esempi. Teorema di equivalenza tra automi con epsilon-transizioni e automi finiti deterministici. Esempi.Esempio dell'automa che riconosce il linguaggio delle parole di lunghezza pari che terminano per aa oppure di lunghezza dispari che terminano per bb.

MAR 10/04/18 9-11 L13 L'algoritmo ricorsivo soluzione della torre di Hanoi. Dimostrazione della correttezza e della complessita'. Analisi del codice in C.
. Il gioco "Indovina il numero". Strategia di soluzione con la tecnica divide et impera . Dimostrazione della correttezza e della complessita'.
Lucidi.
LABORATORIO 8: Esercizi Proposti

MAR 10/04/18 14-16 L14 Definizione di variabili puntatore. Esempi. Operatori & e *. Simulare il passaggio di parametri a funzioni per riferimento tramite puntatori. Esempi. Cenni su aritmetica dei puntatori.
( Non sono disponibili lucidi perche' la lezione e' stata svolta alla lavagna. )

GIO 12/04/18 9-11 L15
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.
Lucidi.
LABORATORIO 9: Esercizi Proposti

GIO 12/04/18 11-13 I5 Definizione formale delle espressioni regolari e dei linguaggi ad esse associati. Esempi. Teorema di Kleene (equivalenza famiglia linguaggi definiti da espressioni regolari e riconosciuti da automi finiti). Costruzione esplicita dell'automa finito con epsilon-transizioni equivalente ad una data espressione regolare. Costruzione esplicita dell'espressione regolare corrispondente ad un DFA con la tecnica di eliminazione degli stati. Esempi.
Esercizi assegnati:
Determinare un'espressione regolare per ciascuno dei seguenti linguaggi sull'alfabeto Σ ={a,b}:
Linguaggio di tutte le parole che terminano per aba
Linguaggio di tutte le parole che iniziano per bb
Linguaggio di tutte le parole che contengono come fattore aba
Linguaggio di tutte le parole il cui quarto elemento da destra sia a.
Linguaggio di tutte le parole che contengono sia aa che bb.
Linguaggio di tutte le parole che contengono un numero pari di a.
Linguaggio di tutte le parole che non contengono bab.
Linguaggio di tutte le parole che non contengono aa e bb.
Linguaggio di tutte le parole che non contengono piu' di due b consecutive.
Linguaggio di tutte le parole in cui ogni aa precede bb.

MAR 17/4/2018 9-11 L16 Correzione dettagliata dell'esercizio del Laboratorio 9.
Cenni su principi generali su analisi complessita' degli algoritmi. Notazione asintotica per le funzioni. Confronti su diverse funzioni viste come tempo di esecuzione di algoritmi. Problema dell'ordinamento. Algoritmi di ordinamento su vettori: selectionSort, bubbleSort, insertionSort. Valutazione della complessita' di tempo.
Lucidi.

MAR 17/04/2018 14-16 L17 Algoritmi di ordinamento su vettori: selectionSort, bubbleSort, insertionSort. Valutazione della complessita' di tempo. Caso migliore e caso peggiore.
Lucidi.

GIO 19/04/2018 9-11 L18 Definizione di lower bound di un problema Calcolo del lower bound per il sorting.
La tecnica algoritmica del divide et impera e una sua applicazione al problema dell'ordinamento: l'algoritmo MergeSort . Descrizione informale e pseudocodice e calcolo dei confronti effettuati. L'algoritmo QuickSort . Descrizione informale e pseudocodice.
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. Lucidi.
LABORATORIO 10: Esercizi Proposti

GIO 19/04/2018 11-13 I6 Correzione degli esercizi della settimana precedente. Costruzione esplicita dell'espressione regolare corrispondente ad un DFA con la tecnica di eliminazione degli stati. Esempi.
Il pumping lemma per i linguaggi regolari. Enunciato e valutazioni informali sul suo significato. Esempio di applicazione del pumping lemma per dimostrare che il linguaggio delle parole del tipo a^n b^n non e' regolare.
MAR 24/04/18 9-11 L19 Stringhe come array di char. Immissione e stampa di stringhe. Esempi. La libreria strinf.h.
Matrici bidimensionali in C. Proprieta' ed esempi. Inizializzazioni con valori random e stampa di matrici utilizzando funzioni che gestiscono array unidimensionali. Lucidi.
LABORATORIO 11: Esercizi Proposti

MAR 24/04/18 14-16 L20 Richiami sui puntatori e loro utilizzo per leggere/scrivere sulle variabili.
Aritmetica dei puntatori: puntatori e array. Puntatori e stringhe. Funzioni malloc e free. Esempi.

GIO 26/04/18 9-11 TUTORATO DI PROGRAMMAZIONE : svolgimento di una precedente prova d'esame

MAR 3/5/18 9-11 L21 Correzione alla lavagna dell'esercizio per il calcolo della MaxSum proposto al laboratorio 11. Analisi della correttezza e complessita' degli algorimi corrispondenti.
Strutture dati astratte: "lista","pila" e "coda". Implementazioni in C tramite array. Lucidi.
LABORATORIO 13: Esercizi Proposti

GIO 3/5/18 11-13 I7 Dimostrazione del Pumping Lemma. Dimostrazione che il linguaggio delle parole di lunghezza un quadrato non e' regolare. Dimostrazione che il linguaggio delle parole di lunghezza un primo non e' regolare. Proprieta' di chiusura dei linguaggi regolari rispetto alle operazioni booleane, di concatenazione e star, di reverse e immagine via omomorfismo. Cenni sulle dimostrazioni e costruzione degli automi corrispondenti.

MAR 8/5/18 9-11 L22 Correzione alla lavagna dell'esercizio della bandiera proposto al laboratorio 11.
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". [mazzoDiCarte.cpp].

LABORATORIO 14: Esercizi Proposti

MAR 8/5/18 14-16 L23 Strutture autoreferenzianti per creare strutture dati dinamiche. Definizione di un nodo-lista. Funzione di inizializzazione di una lista contenente dei valori random in due versioni: una in cui i nodi vengono inseriti sempre all'inizio e l'altra in cui vengono inseriti sempre alla fine. Stampa di una lista.

GIO 10/5/18 9-11 L24 Operatori malloc e free per la gestione di una lista con strutture autoreferenzianti. Definizione di una lista.
Operazioni definite su una lista: Inserimento di un elemento (in testa/in coda/), Cancellazione di un elemento, Test per "lista vuota". Implementazioni mediante strutture collegate. Implementazione delle funzioni in C con la lista passata sia per valore che per riferimento. (codice L24eselistanew.cpp) Lucidi.

GIO 10/5/18 11-13 I8 Definizione di grammatica generica, derivazioni di parole e linguaggio generato. Gerarchia di Chomsky: grammatiche di tipo 0,1,2,3.
Esempi di grammatiche regolari (tipo 3) e context-free (tipo 2). Esempio della grammatica che genera il linguaggio a^nb^n e della grammatica che genera le parole palindrome.

Esercizio 1: Determinare una grammatica context-free per il linguaggio sull'alfabeto Σ ={a,b} delle parole che contengono lo stesso numero di a e di b. Esempio: aababbab.
Esercizio 2: Determinare una grammatica context-free per il linguaggio sull'alfabeto Σ ={[,],x} delle parole corrispondenti ad espressioni ben formate di parentesi quadre e variabile x. Esempio: [[x][x]][x].

MAR 15/05/18 9-11 L25 Operazioni di cancellazione e di inserimento in ordine in una lista. Strutture dati astratte "pila" e "coda". Implementazioni in C. Passaggio di strutture collegate (liste-pile-code) a funzioni.(codici L25esePilanew.c e L25eseCodanew.c
Esempi di utilizzo della struttura dati pila. Valutazione valore di verita' di semplici formule booleane. (codice L25formulaBooleanaconPila.c)
Forma postfissa per le espressioni aritmetiche. Valutazione di espressioni aritmetiche in forma postfissa usando una pila. Trasformazione di una espressione aritmetica da forma infissa a forma postfissa. Lucidi.

MAR 15/05/18 14-16 TUTORATO DI PROGRAMMAZIONE : svolgimento di una precedente prova d'esame

GIO 17/5/18 9-11 L26 Gestione dei file in C. Gestione di un file ad accesso sequenziale: apertura, chiusura, lettura e scrittura. Esempi.(codici L26file1.c, L26file2.c, L26filecopia.c) Lucidi.
LABORATORIO 17: Esercizi Proposti

GIO 17/5/18 11-13 I9 Correzione degli esercizi. Alberi di derivazione. Grammatica context-free per le espressioni aritmetiche.Descrizione informale di un automa a pila.

MAR 22/05/18 9-11 L27

MAR 22/05/18 14-16 L28

GIO 24/5/18 9-11 L29

GIO 24/5/18 11-13 I10

MAR 29/05/18 9-11 L30

MAR 29/05/18 14-16 TUTORATO DI PROGRAMMAZIONE :

GIO 31/05/2018 9-12 PREAPPELLO per la prova di LABORATORIO
Questo e' il testo

Data	Ora	Argomento
MAR 6/3/18	9-11	L1 Presentazione del corso. Introduzione all'informatica e centralità del concetto di algoritmo. Lucidi. Lettura di approfondimento.
Mar 6/3/18	14-16	L2 Il primo (classico!) programma in C: scrivere un messaggio sullo schermo. Il concetto di variabile in un programma. Identificatori per le variabili. Il secondo programma: "sommare due numeri interi e scrivere il risultato sullo schermo. Il terzo programma (variante): "Richiedere due numeri interi all'utente e stampare sullo schermo la loro somma". LABORATORIO 1: Esercizi Proposti
GIO 8/3/18	9-11	L3 Cenni sulla struttura di un computer. Lo schema di Von Neumann. Cenni sul file system: alcune istruzioni per la gestione dei files da finestra di sistema in unix e windows Le fasi di compilazione ed esecuzione di un programma in C. Iniziare a scrivere un programma: direttive del preprocessore, e funzione main. Sintassi per gli identificatori e per la dichiarazione di variabili. Istruzione di assegnamento. Esempio: Scambiare il valore di due variabili. Lucidi.
GIO 8/3/18	11-13	I1 Presentazione della parte di Teoria dei linguaggi. Brevi cenni storici sull'inizio dell'Informatica Teorica. Linguaggi formali: alfabeto, parola, linguaggio. Esempi. I problemi decisionali visti come un test di appartenenza di una data parola a un dato linguaggio. Definizione formale delle operazioni di concatenazione e star tra parole e tra linguaggi. Esempi.
MAR 13/3/18	9-11	L4 Rappresentazione dei dati in C. I 5 tipi elementari `char, int, float, double` e i modificatori `short, long, long long, signed, unsigned` . Rappresentazione numeri in sistema binario, (decimale) e esadecimale. Occupazione in memoria dei vari tipi di dati. Problemi di approssimazione nella rappresentazione dei numeri reali. Operatore unario `sizeof( )` . Lucidi.
MAR 13/3/18	14-16	L5 Espressioni aritmetiche e logiche. Operatori aritmetici, condizionali e logici in C. La programmazione strutturata e il controllo del flusso di un programma. Il Teorema di Bohm e Jacopini. La struttura di selezione `if` e la struttura di ripetizione `while` . Lucidi. LABORATORIO 2: Esercizi Proposti
GIO 15/3/18	09-11	L6 La struttura di selezione `if ...else` . Esempi di utilizzo di strutture `if ...else` nidificate. Il problema del dangling else (else appeso). Problema: trovare il max tra 3 numeri utilizzando 2 confronti. Problema: ordinare 3 numeri utilizzando 3 confronti. Lucidi. LABORATORIO 3: Esercizi Proposti
GIO 15/3/18	11-13	I2 Presentazione del modello "automa a stati finiti". Definizione formale di automa e di linguaggio accettato. Rappresentazione di un automa tramite grafo delle transizioni. Esempi. Esercizi assegnati: Determinare un automa finito per ciascuno dei seguenti linguaggi: Parole sull'alfabeto Σ ={a,b} che terminano per abba Parole sull'alfabeto Σ ={a,b} che iniziano per bb Parole sull'alfabeto Σ ={a,b} che contengono come fattore abba Parole sull'alfabeto Σ ={0,1} che corrispondono a numeri in binario che sono multipli di 5. Parole sull'alfabeto Σ ={a,b} il cui quarto elemento da destra sia a. Parole sull'alfabeto Σ ={a,b} il cui quinto elemento da destra sia a.
MAR 20/3/18	9-11	L7 La struttura di ripetizione `do ...while` . Equivalenza tra le due strutture di ripetizione introdotte. Operatori di incremento e decremento ++, --. Operatori di assegnamento +=, -=, *=. La ripetizione definita: la struttura `for` . Esempi. Equivalenza tra le strutture di ripetizione introdotte. Correzione di alcuni esercizi del Laboratorio 2. Lucidi.
MAR 20/3/18	14-16	L8 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` . Lucidi. LABORATORIO 4: Esercizi Proposti
GIO 22/3/18	14-16	L9 La struttura di selezione `switch` . Esempi. Correzione di alcuni esercizi del Laboratorio 3 Lucidi. LABORATORIO 5: Esercizi Proposti
GIO 22/3/18	11-13	I3 Automa deterministico per il linguaggio delle parole il cui quarto simbolo a partire da destra e' una a. Proposizione: L'automa deterministico per il linguaggio delle parole il cui n-esimo simbolo da destra e' una a ha almeno 2^n stati. Dimostrazione. Automa finito non deterministico: definizione ed esempi. Definizione della funzione di transizione estesa e di linguaggio accettato. Definizione di automi equivalenti. Teorema di equivalenza tra automi finiti non deterministici e deterministici. Esercizi assegnati: Determinare un automa finito non deterministico per ciascuno dei seguenti linguaggi e poi determinizzarlo applicando la costruzione per sottoinsiemi: Linguaggio sull'alfabeto {a,b} di tutte le parole che terminano per abba. Linguaggio sull'alfabeto {a,b} di tutte le parole che contengono sia aa che bb.
MAR 27/3/18	9-11	L10 Definizione di funzioni nei programmi in C. Sintassi. Meccanismo del passaggio dei parametri e variabili locali alle funzioni. Esempio "quadratiVari.c". Lucidi. LABORATORIO 6: Esercizi Proposti
MAR 27/3/18	14-16	L11 Funzioni della libreria matematica. Generatore di numeri casuali. Esempi: dado1.c, dado2.c,lancidado.c. Calcolo di una funzione funzione definita come limite di una serie. Esempio dell'approssimazione della radice quadrata. Esempi: apprRadice1.c, apprRadice2.c. Correzione di alcuni esercizi del Laboratorio 4 e 5. Lucidi.
29/3/18 e 3/4/18		vacanze di Pasqua
GIO 5/04/18	9-11	L12 Parametri e variabili locali di una funzione. Stack delle chiamate di funzione. Funzioni ricorsive. Esempi. La torre di hanoi. Lucidi. LABORATORIO 7: Esercizi Proposti
GIO 5/04/18	11-13	I4 Teorema di equivalenza tra automi finiti non deterministici e deterministici. Costruzione per stati raggiungibili. Automa finito con epsilon-transizioni. Definizioni ed esempi. Teorema di equivalenza tra automi con epsilon-transizioni e automi finiti deterministici. Esempi.Esempio dell'automa che riconosce il linguaggio delle parole di lunghezza pari che terminano per aa oppure di lunghezza dispari che terminano per bb.
MAR 10/04/18	9-11	L13 L'algoritmo ricorsivo soluzione della torre di Hanoi. Dimostrazione della correttezza e della complessita'. Analisi del codice in C. . Il gioco "Indovina il numero". Strategia di soluzione con la tecnica divide et impera . Dimostrazione della correttezza e della complessita'. Lucidi. LABORATORIO 8: Esercizi Proposti
MAR 10/04/18	14-16	L14 Definizione di variabili puntatore. Esempi. Operatori & e . Simulare il passaggio di parametri a funzioni per riferimento tramite puntatori. Esempi. Cenni su aritmetica dei puntatori. ( Non sono disponibili lucidi perche' la lezione e' stata svolta alla lavagna.* )
GIO 12/04/18	9-11	L15 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. Lucidi. LABORATORIO 9: Esercizi Proposti
GIO 12/04/18	11-13	I5 Definizione formale delle espressioni regolari e dei linguaggi ad esse associati. Esempi. Teorema di Kleene (equivalenza famiglia linguaggi definiti da espressioni regolari e riconosciuti da automi finiti). Costruzione esplicita dell'automa finito con epsilon-transizioni equivalente ad una data espressione regolare. Costruzione esplicita dell'espressione regolare corrispondente ad un DFA con la tecnica di eliminazione degli stati. Esempi. Esercizi assegnati: Determinare un'espressione regolare per ciascuno dei seguenti linguaggi sull'alfabeto Σ ={a,b}: Linguaggio di tutte le parole che terminano per aba Linguaggio di tutte le parole che iniziano per bb Linguaggio di tutte le parole che contengono come fattore aba Linguaggio di tutte le parole il cui quarto elemento da destra sia a. Linguaggio di tutte le parole che contengono sia aa che bb. Linguaggio di tutte le parole che contengono un numero pari di a. Linguaggio di tutte le parole che non contengono bab. Linguaggio di tutte le parole che non contengono aa e bb. Linguaggio di tutte le parole che non contengono piu' di due b consecutive. Linguaggio di tutte le parole in cui ogni aa precede bb.
MAR 17/4/2018	9-11	L16 Correzione dettagliata dell'esercizio del Laboratorio 9. Cenni su principi generali su analisi complessita' degli algoritmi. Notazione asintotica per le funzioni. Confronti su diverse funzioni viste come tempo di esecuzione di algoritmi. Problema dell'ordinamento. Algoritmi di ordinamento su vettori: selectionSort, bubbleSort, insertionSort. Valutazione della complessita' di tempo. Lucidi.
MAR 17/04/2018	14-16	L17 Algoritmi di ordinamento su vettori: selectionSort, bubbleSort, insertionSort. Valutazione della complessita' di tempo. Caso migliore e caso peggiore. Lucidi.
GIO 19/04/2018	9-11	L18 Definizione di lower bound di un problema Calcolo del lower bound per il sorting. La tecnica algoritmica del divide et impera e una sua applicazione al problema dell'ordinamento: l'algoritmo MergeSort . Descrizione informale e pseudocodice e calcolo dei confronti effettuati. L'algoritmo QuickSort . Descrizione informale e pseudocodice. 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. Lucidi. LABORATORIO 10: Esercizi Proposti
GIO 19/04/2018	11-13	I6 Correzione degli esercizi della settimana precedente. Costruzione esplicita dell'espressione regolare corrispondente ad un DFA con la tecnica di eliminazione degli stati. Esempi. Il pumping lemma per i linguaggi regolari. Enunciato e valutazioni informali sul suo significato. Esempio di applicazione del pumping lemma per dimostrare che il linguaggio delle parole del tipo a^n b^n non e' regolare.
MAR 24/04/18	9-11	L19 Stringhe come array di char. Immissione e stampa di stringhe. Esempi. La libreria strinf.h. Matrici bidimensionali in C. Proprieta' ed esempi. Inizializzazioni con valori random e stampa di matrici utilizzando funzioni che gestiscono array unidimensionali. Lucidi. LABORATORIO 11: Esercizi Proposti
MAR 24/04/18	14-16	L20 Richiami sui puntatori e loro utilizzo per leggere/scrivere sulle variabili. Aritmetica dei puntatori: puntatori e array. Puntatori e stringhe. Funzioni `malloc` e `free`. Esempi.
GIO 26/04/18	9-11	TUTORATO DI PROGRAMMAZIONE : svolgimento di una precedente prova d'esame
MAR 3/5/18	9-11	L21 Correzione alla lavagna dell'esercizio per il calcolo della MaxSum proposto al laboratorio 11. Analisi della correttezza e complessita' degli algorimi corrispondenti. Strutture dati astratte: "lista","pila" e "coda". Implementazioni in C tramite array. Lucidi. LABORATORIO 13: Esercizi Proposti
GIO 3/5/18	11-13	I7 Dimostrazione del Pumping Lemma. Dimostrazione che il linguaggio delle parole di lunghezza un quadrato non e' regolare. Dimostrazione che il linguaggio delle parole di lunghezza un primo non e' regolare. Proprieta' di chiusura dei linguaggi regolari rispetto alle operazioni booleane, di concatenazione e star, di reverse e immagine via omomorfismo. Cenni sulle dimostrazioni e costruzione degli automi corrispondenti.
MAR 8/5/18	9-11	L22 Correzione alla lavagna dell'esercizio della bandiera proposto al laboratorio 11. 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". [mazzoDiCarte.cpp]. LABORATORIO 14: Esercizi Proposti
MAR 8/5/18	14-16	L23 Strutture autoreferenzianti per creare strutture dati dinamiche. Definizione di un nodo-lista. Funzione di inizializzazione di una lista contenente dei valori random in due versioni: una in cui i nodi vengono inseriti sempre all'inizio e l'altra in cui vengono inseriti sempre alla fine. Stampa di una lista.
GIO 10/5/18	9-11	L24 Operatori malloc e free per la gestione di una lista con strutture autoreferenzianti. Definizione di una lista. Operazioni definite su una lista: Inserimento di un elemento (in testa/in coda/), Cancellazione di un elemento, Test per "lista vuota". Implementazioni mediante strutture collegate. Implementazione delle funzioni in C con la lista passata sia per valore che per riferimento. (codice L24eselistanew.cpp) Lucidi.
GIO 10/5/18	11-13	I8 Definizione di grammatica generica, derivazioni di parole e linguaggio generato. Gerarchia di Chomsky: grammatiche di tipo 0,1,2,3. Esempi di grammatiche regolari (tipo 3) e context-free (tipo 2). Esempio della grammatica che genera il linguaggio a^nb^n e della grammatica che genera le parole palindrome. Esercizio 1: Determinare una grammatica context-free per il linguaggio sull'alfabeto Σ ={a,b}* delle parole che contengono lo stesso numero di a e di b.* Esempio: aababbab. Esercizio 2: Determinare una grammatica context-free per il linguaggio sull'alfabeto Σ ={[,],x}* delle parole corrispondenti ad espressioni ben formate di parentesi quadre e variabile x*. Esempio: [[x][x]][x].
MAR 15/05/18	9-11	L25 Operazioni di cancellazione e di inserimento in ordine in una lista. Strutture dati astratte "pila" e "coda". Implementazioni in C. Passaggio di strutture collegate (liste-pile-code) a funzioni.(codici L25esePilanew.c e L25eseCodanew.c Esempi di utilizzo della struttura dati pila. Valutazione valore di verita' di semplici formule booleane. (codice L25formulaBooleanaconPila.c) Forma postfissa per le espressioni aritmetiche. Valutazione di espressioni aritmetiche in forma postfissa usando una pila. Trasformazione di una espressione aritmetica da forma infissa a forma postfissa. Lucidi.
MAR 15/05/18	14-16	TUTORATO DI PROGRAMMAZIONE : svolgimento di una precedente prova d'esame
GIO 17/5/18	9-11	L26 Gestione dei file in C. Gestione di un file ad accesso sequenziale: apertura, chiusura, lettura e scrittura. Esempi.(codici L26file1.c, L26file2.c, L26filecopia.c) Lucidi. LABORATORIO 17: Esercizi Proposti
GIO 17/5/18	11-13	I9 Correzione degli esercizi. Alberi di derivazione. Grammatica context-free per le espressioni aritmetiche.Descrizione informale di un automa a pila.
MAR 22/05/18	9-11	L27
MAR 22/05/18	14-16	L28
GIO 24/5/18	9-11	L29
GIO 24/5/18	11-13	I10
MAR 29/05/18	9-11	L30
MAR 29/05/18	14-16	TUTORATO DI PROGRAMMAZIONE :
GIO 31/05/2018	9-12	PREAPPELLO per la prova di LABORATORIO Questo e' il testo

Laboratorio di Programmazione & Informatica 1 A.A. 2017-2018

Diario delle lezioni

Laboratorio di Programmazione & Informatica 1
A.A. 2017-2018