Fondamenti di Informatica 1

I lucidi delle lezioni sono disponibili in formato Acrobat PDF, che ne consente la visualizzazione e la stampa su qualsiasi computer e su qualsiasi stampante senza perdita di qualità.

File	Descrizione
-Presentazione corso	Considerazione generali sul corso
1-Introduzione	Introduzione all'Informatica. Architetture a rete. Internet e servizi di rete.
2-Hardware e Software	Generalità sull'elaboratore, hardware e software, memorie di massa, sistemi operativi.
3-Architetture	La struttura interna di un elaboratore e l'architettura di Von Neumann. Ciclo fetch/decode/execute. ALU, unità di controllo, registri. Memoria centrale e indirizzamento. Periferiche. Gerarchie di memorie e memorie cache.
4-Algoritmi e Computabilità	Il concetto di algoritmo e sue proprietà. Algoritmi equivalenti. Automa esecutore. Modelli matematici e gerarchia di macchine la Macchina di Turing. Esempio di programma con la TM. Problema risolubile, funzione computabile, computabilità. Funzioni non computabili l'halt della TM. Insiemi ricorsivamente enumerabili e insiemi ricorsivi. Insiemi ricorsivi e linguaggi di programmazione.
5-Progetto del Software e Linguaggi	Progetto e sviluppo del software metodologie. Linguaggi di alto livello, linguaggi come sistema matematico. Sintassi e sematica. Linguaggi e grammatiche concetto di grammatica, notazione BNF e EBNF. Alberi sintattici e diagrammi sintattici. Grammatiche, Linguaggi e Macchine per riconoscere linguaggi. Classificazione di Chomsky.
6-Linguaggio macchina	Un semplice linguaggio macchina di esempio codice operativo, operandi, tipi di indirizzamento. Micro-istruzioni. Esempio di programma in l.m. Il linguaggio assembler e l'assemblatore. Traduzione dei linguaggi di alto livello in linguaggio macchina compilatori e interpreti.
7-Introduzione al C	Progetto e Linguaggio. Linguaggi di computazione e linguaggi di coordinazione. Il linguaggio C. Il concetto di espressione. Espressioni in C espressioni aritmetiche, logiche, relazionali, condizionali. Il concetto di variabile, L-Value e R-Value. Espressioni con variabili. Espressione di assegnamento ed effetti collaterali. Associatività e priorità degli operatori. Grammatica delle espressioni aritmetiche alberi di derivazione. Costanti in C. Esempi di programmi C basati su espressioni. Il concetto di istruzione e di controllo. Teorema di Jacopini-Bohm. Istruzioni di composizione (blocco), di scelta e di iterazione. Esempi ed esercizi.
-Tipi in C	Tipi di dato astratto. Classificazione dei tipi di dato. Tipi predefiniti int, char, float, double e loro varianti. Compatibilità fra tipi di dato. Regole di conversione implicita. Compatibilità di tipo e assegnamento. Tipi definiti dall'utente typedef. Tipi enumerativi. Il tipo boolean. Equivalenza fra tipi equivalenza nominale ed equivalenza strutturale. Unicità e ordine di definizione degli identificatori.
9-Progetti e Preprocessore C	Compilazione e collegamento. Il concetto di progetto. Progetti in Rhide e in Turbo C++. Il pre-processore C motivazioni e sintassi. Esempio uso di gcc per vedere la fase di pre-processing. Le macro semplici, parametriche, con effetti collaterali.
1-Funzioni in C	Architetture multi-componente. Il modello cliente/servitore. Costruzione di componenti software funzioni e procedure. Comunicazione fra componenti passaggio dei parametri. Dichiarazione e definizione di funzioni e procedure. Passaggio dei parametri per valore e per riferimento. Esempi. Funzioni e macro, analogie e differenze.
11-Progetti su più file	Progetti su più file. Compilazione e collegamento. Il concetto di header file. Esempi. Problemi header file con definizioni di tipo. Inclusione multipla. Uso delle direttive al preprocessore per risolvere problemi di inclusioni multipla.
12-Variabili globali	Variabili globali definizione. Esempi e problemi in progetti con inclusione multipla. Dichiarazione di variabili globali. Globalità e protezione variabili statiche. Esercizi.
13-Ricorsione	Ricorsione. Definizione di funzioni ricorsive. Esempi. Ricorsione lineare e non lineare. Ricorsione tail. Iterazione e ricorsione analogie e differenze. Esercizi.
14-Record di attivazione	Il modello a run-time della macchine virtuale C. Record di attivazione delle funzioni. Passaggio per valore e per riferimento. Link dinamico. Esempi ed esercizi.
15-Puntatori	Realizzazione in C del passaggio per riferimento la visibilità della macchina sottostante. Gli operatori di estrazione di indirizzo e dereferenziamento. Puntatori definizione ed esempi. Uso di puntatori in procedure con parametri da passare per riferimento.
16-Tipi strutturati	Tipi strutturati vettori e strutture. Vettori il concetto, l'uso, la realizzazione in C il passaggio dei vettori come parametri a funzioni. Stringhe di caratteri. Esempi ed esercizi. Strutture concetto, uso, esempi.
17-Libreria di I/O	Coordinazione e computazione la libreria di I/O standard. Funzioni per l'I/O a carattere, a linee, formattato. Le specifiche di formato. Esempi ed esercizi. Cenni alle altre librerie standard del C.
Numeri	La rappresentazione dei numeri.
1-Esercizi vari	Esercizi vari in C su molti aspetti fin qui visti.
19-Conversioni	Esercizi di codifica degli algoritmi di conversione numero/stringa/numero per numeri interi senza segno e con segno.
2-Esercizi record di attivazione	Ulteriori esercizi sui record di attivazione.
21-Allocazione dinamica	Allocazione dinamica della memoria malloc() e free(). Vettori dinamici. Esercizi.
22-Progetto di un ADT	Progetto di un tipo di dato astratto definizione, operazioni primitive e non primitive, categorizzazione delle operazioni costruttori, selettori, trasformatori. Il caso dell'ADT complex passo per passo. Cambio di rappresentazione e impatto sul progetto.
23-Complessità	Complessità di un algoritmo delimitazioni superiori e inferiori al comportamento asintotico. Complessità di un problema. Istruzione dominante. Esempi.
24-Algoritmi di ordinamento e ricerca	Algoritmi di ordinamento naive sort, bubble sort, insert sort, quick sort, shell sort e valutazione comparativa di complessità. Algoritmi di ricerca ricerca binaria. Esempi ed esercizi.
25-Gestione dei file	Gestione dei file in C apertura, chiusura. File di testo e file binari. Primitive di I/O da file di testo. Esempi. Primitive di I/O da file binari esempi. Riflessioni su analogie e differenze fra file di testo e file binari, con particolare riferimento alle conversioni numeriche.
26-Matrici e tabelle	Matrici sparse. Tabelle con funzioni di accesso. Tabelle hash.
27-Liste	Il concetto di lista. Realizzazione sequenziale e collegata. Implementazione tramite vettori e tramite strutture dinamiche. L'ADT lista primitive fondamentali e funzioni derivate. Discussione e implementazione sia in modo ricorsivo che in modo iterativo.
2-Esercizio liste	Esercizio d'esame completo sulle liste.
29-Altri tipi di liste	Liste bidirezionali e multiple
3-Stack e code	Altre strutture dati stack e code (circolari), intese sia come ADT sia come singole astrazioni di dato. Implementazioni con vettori e con liste. Il tema della genericità il costrutto union e i puntatori void. Uso dei void per creare funzioni generiche e per costruire contenitori generici.
31-Esercizio l'ADT insieme	Il tipo di dato astratto "insieme" costruito mediante vettore caratteristico e mediante liste.
32-Grafi e alberi	Grafi definizione, proprietà. Alberi definizione, proprietà, primitive. Alberi binari e loro peculiarità. Alberi binari di ricerca. Esempi.
33-Esercizio alberi	Esercizio d'esame completo sugli alberi.
34-Compiti d'esame	Due compiti d'esame discussi e risolti passo passo.

Fondamenti di Informatica 1

Lucidi delle Lezioni