Corso di Informatica 1 (IN110)

Le lezioni

Diario delle lezioni dell'anno accademico 2010/2011

Le attività didattiche (lezioni, esercitazioni, tutorato) relative al corso di IN110 - Informatica 1 (Fondamenti) per l'anno accademico 2010/2011 sono terminate. Il ricevimento studenti rimane attivo tutti i venerdì dalle 9:00 alle 10:00 nella stanza 207. Per le date degli appelli d'esame si faccia riferimento alle pagine esami e bacheca di questo sito web.

Le lezioni si sono tenute nel primo semestre con il seguente orario:

• martedì ore 9:00-11:00 (lezione: aula B3 - Liverani);
• martedì ore 14:00-16:00 (tutorato: laboratorio).
• mercoledì ore 9:00-11:00 (lezione: aula B3 - Liverani);
• giovedì ore 9:00-11:00 e 14:00-15:00 (esercitazione: laboratorio - Piroso);

Lezione n. 1 - martedì 21 settembre 2010

• Presentazione del corso: argomenti che tratteremo, orario delle lezioni, orario delle esercitazioni, orario di ricevimento, modalità di esame (scarica il documento: “Presentazione del corso di Informatica 1”).
• Introduzione alla progettazione di algoritmi: un approccio intuitivo mediante alcuni esempi elementari.

Lezione n. 2 - mercoledì 22 settembre 2010

• Esecutore, algoritmi, linguaggi imperativi/procedurali: caratteristiche di un calcolatore elettronico, compiti del programmatore, capacità del calcolatore/esecutore; algoritmi; le istruzioni fondamentali di un linguaggio di programmazione imperativo/procedurale; esempi di pseudo-codifica di algoritmi per la soluzione di problemi elementari (sommatoria, minimo comune multiplo fra due interi).

Esercitazione n. 1 - giovedì 23 settembre 2010

• Introduzione all'utilizzo del sistema operativo Linux: finalità e caratteristiche di un sistema operativo, multitasking, multiutenza, console, terminali ed emulatori di terminale; la shell dei comandi UNIX, login/logout, operazioni elementari su file e directory. Sono disponibili delle dispense introduttive all'uso del sistema operativo UNIX/Linux e dei comandi della shell.

Lezione n. 3 - venerdì 24 settembre 2010

• Algoritmi, diagrammi di flusso, programmazione strutturata: rappresentazione di algoritmi mediante diagrammi di flusso, strutture algoritmiche di tipo sequenziale, iterativo, condizionale; regole della programmazione strutturata, cenni sul Teorema Fondamentale della Programmazione Strutturata di Jacopini e Böhm; esempi: sommatoria, ricerca del massimo fra 2, 3 e n numeri (scarica il documento: “Algoritmi e diagrammi di flusso”).

Lezione n. 4 - martedì 28 settembre 2010

• Algoritmi, pseudo-codice e diagrammi di flusso: esempi di algoritmi per la risoluzione di problemi elementari, pseudo-codifica degli algoritmi e rappresentazione mediante diagrammi di flusso: calcolo del fattoriale di un intero n>0, stabilire se n>0 è pari; dati due interi x,y>0 stabilire se y divide x; calcolare il quoziente e il resto della divisione intera x/y; dato un intero n>2 stabilire se è primo.

Lezione n. 5 - mercoledì 29 settembre 2010

• Calcolabilità e modelli di calcolo: problemi calcolabili e non calcolabili, alcuni esempi; modelli di calcolo astratti: la macchina di Turing, la macchina di Von Neumann; cenni sul problema della fermata, cenni sulla Tesi di Church-Turing (scarica il documento: “Appunti sui modelli di calcolo”).
• Linguaggi di programmazione: linguaggi artificiali, linguaggi di programmazione di alto livello, linguaggio macchina; processo di traduzione del codice da linguaggio di programmazione di alto livello (sorgente) a linguaggio macchina (eseguibile).

Esercitazione n. 2 - giovedì 30 settembre 2010

• Utilizzo del filesystem Linux: struttura del filesystem di una macchina Linux/UNIX, comandi per muoversi nel filesystem, creazione, cancellazione e spostamento di file e directory, permessi di accesso ai file, visualizzazione del contenuto di file.
• Accesso al server del laboratorio: terminali, emulatori di terminale e accesso da remoto ad un server Linux/UNIX per sessioni di lavoro interattive; emulatori di terminale e utilizzo del comando ssh in ambiente Linux e Windows per l'accesso al server del laboratorio dalla rete Internet. Sono disponibili degli appunti per l'uso del laboratorio e l'accesso da remoto al server.

Lezione n. 6 - martedì 5 ottobre 2010

• Linguaggi di programmazione: linguaggi di programmazione di alto livello per la codifica di algoritmi, linguaggio macchina per la codifica di programmi eseguibili, processo di traduzione (compilazione e interpretazione) dal “codice sorgente” al programma “eseguibile”; classificazione dei linguaggi di programmazione, esempi (scarica il documento: “Appunti sui linguaggi di programmazione”).
• Rappresentazione delle informazioni: codifica decimale e binaria di numeri interi positivi; struttura della memoria, bit, byte; rappresentazione di numeri interi “grandi“, mediante parole ottenute concatenando più byte, rappresentazione di numeri interi relativi, rappresentazione di numeri razionali (floating point), rappresentazione di caratteri alfanumerici (scarica il documento: “Appunti sulla rappresentazione delle informazioni in memoria”).

Lezione n. 7 - mercoledì 6 ottobre 2010

• Introduzione al linguaggio C: struttura e sintassi generale di un programma C, la funzione main, inclusione di librerie, le funzioni di input/output printf e scanf, definizione di variabili, assegnazione di valori alle variabili; la struttura di controllo condizionale if... else..., esempi; le strutture di controllo iterative while... e for..., esempi (scarica il documento: “Appunti sul linguaggio C”).

Esercitazione n. 3 - giovedì 7 ottobre 2010

• Compilazione di programmi in C: processo di editing, compilazione, debugging, esecuzione di un programma scritto in linguaggio C; uso del compilatore GCC.
• Esercizi introduttivi: letti due numeri naturali n e k stampare i primi n multipli di k; letti due naturali n e k stampa la sommatoria k + k² + k³ + ... + kⁿ (documento con i testi e le soluzioni degli esercizi: esercitazione01.pdf).

Lezione n. 8 - martedì 12 ottobre 2010

• Tipi di dato elementari: dichiarazione delle variabili in linguaggio C; i tipi di dato int, long, short e unsigned per la rappresentazione di numeri interi, il tipo float per le variabili in virgola mobile (floating point), char per la memorizzazione di singoli caratteri.
• Operatori e cast: operatori aritmetici, operatori di confronto, connettori logici; il cast, esempi; funzioni matematiche di libreria, inclusione dell'header file math.h e della libreria di funzioni matematiche con l'opzione “-lm” del compilatore C.
• Strutture di controllo: ancora sulle istruzioni per l'implementazione delle strutture algoritmiche condizionali (istruzioni if-else) e iterative (istruzioni while, do-while e for); esempi.

Lezione n. 9 - martedì 19 ottobre 2010

• Array: array monodimensionali (vettori) e multidimensionali (matrici), dichiarazione di array, allocazione in memoria di un array; definizione di costanti con la direttiva del precompilatore “#define”; esempi con vettori e matrici.

Lezione n. 10 - mercoledì 20 ottobre 2010

• Esercizi sugli array: riepilogo sulla definizione e l'utilizzo di array; esempi in linguaggio C.
• Stringhe di caratteri: definizione di stringhe di caratteri alfanumerici come array di tipo char; istruzioni per la lettura e la visualizzazione di stringhe, rappresentazione di stringhe in memoria, il carattere “\0” di terminazione di una stringa; equivalenza tra caratteri alfanumerici (tipo char) e il codice ASCII corrispondente (tipo int); esempi su stringhe (stampa di una parola al contrario, trasformazione di caratteri da minuscoli a maiuscoli e viceversa).

Esercitazione n. 4 - giovedì 21 ottobre 2010

• Esercizi sugli array: operazioni sugli array: intersezione, differenza, inversione (documento con i testi e le soluzioni degli esercizi: esercitazione02.pdf).
• Comandi della shell UNIX: il comando chmod per la modifica dei permessi di accesso ad un file e il comando scp per la copia (sicura) di file da un host ad un altro attraverso una connessione di rete.

Lezione n. 11 - martedì 26 ottobre 2010

• Definizione di funzioni: definizione di funzioni in un programma C, nome della funzione, valore restituito dalla funzione, parametri, variabili locali, esempi.
• Passaggio dei parametri: passaggio di parametri per valore e per indirizzo ad una funzione, gli operatori “&” e “*”, esempi.

Lezione n. 12 - mercoledì 27 ottobre 2010

• Passaggio di array a funzioni: passaggio di un array (dell'indirizzo di memoria del primo elemento dell'array) ad una funzione; aritmetica sui puntatori; esempi con la notazione vettoriale e con l'uso esplicito di puntatori; le funzioni per l'acquisizione in input e la stampa di un vettore e di una matrice.

Esercitazione n. 5 - giovedì 28 ottobre 2010

• Esercizi sugli array: verifica della simmetria di una stringa, frequenza degli elementi in un array, colonna di una matrice con il maggior numero di elementi dispari (documento con i testi e le soluzioni degli esercizi: esercitazione03.pdf).
• Soluzione di un compito d'esonero: esercizi di preparazione al compito d'esonero, soluzione di un compito d'esonero degli anni precedenti.

Lezione n. 13 - martedì 9 novembre 2010

• Crivello di Eratostene: richiami sull'uso dei vettori, algoritmo del Crivello di Eratostene per il calcolo dei numeri primi minori di n, esempi, codifica in linguaggio C.
• Funzioni ricorsive: definizione di funzioni ricorsive, differenze ed analogie con procedure iterative, esempi (funzione fattoriale definita in modalità iterativa e ricorsiva).
• Problema dell'ordinamento (sort): definizione del problema dell'ordinamento di un insieme di dati, esempi.
• Algoritmo Selection Sort: strategia risolutiva del problema di ordinamento adottata dall'algoritmo di ordinamento per selezione, pseudo-codifica dell'algoritmo Selection Sort, esempi, calcolo intuitivo del numero di operazioni svolte dall'algoritmo per risolvere un'istanza del problema di dimensione n.

Lezione n. 14 - mercoledì 10 novembre 2010

• Algoritmo Selection Sort: ancora sull'algoritmo Selection Sort, pseudo-codifica, codifica in linguaggio C, esempi, calcolo del numero di operazioni fondamentali eseguite per risolvere un'istanza del problema.
• Complessità computazionale di un algoritmo: problema, istanza di un problema, “dimensione” dell'istanza di un problema; complessità computazionale di un algoritmo come funzione che esprime una stima del numero di operazioni eseguite dall'algoritmo in funzione della dimensione dell'istanza del problema; la notazione “O grande”, esempi di classi di complessità.

Esercitazione n. 5 - giovedì 11 novembre 2010

• Generazione di numeri casuali: numeri pseudo-casuali, la funzione rand(), la funzione srand() e la funzione time(), generazione di numeri casuali compresi tra h e k, esempi.
• Esercizi su vettori di caratteri e su matrici: array di numeri casuali, riconoscimento di stringhe, trasformazione di stringhe in caratteri maiuscoli (documento con i testi e le soluzioni degli esercizi: esercitazione04.pdf).

Lezione n. 15 - martedì 16 novembre 2010

• Algoritmo Insertion Sort: strategia risolutiva dell'algoritmo Insertion Sort, pseudo-codifica, codifica in linguaggio C, esempi, calcolo del numero di operazioni fondamentali eseguite per risolvere un'istanza del problema, nel caso migliore e nel caso peggiore, complessità dell'algoritmo.
• Algoritmo Bubble Sort: strategia risolutiva dell'algoritmo Bubble Sort, pseudo-codifica dell'algoritmo, esempi.

Lezione n. 16 - mercoledì 17 novembre 2010

• Algoritmo Bubble Sort: riepilogo della pseudo-codifica, calcolo della complessità computazionale, codifica in linguaggio C, esempi.
• Algoritmo Quick Sort: strategia risolutiva “divite et impera” dell'algoritmo Quick Sort, pseudo-codifica dell'algoritmo, esempi, complessità nel caso migliore e nel caso peggiore.

Esercitazione n. 6 - giovedì 18 novembre 2010

• Esercizi su array e matrici: inserimento degli elementi di un vettore al centro di un altro vettore; percorso su una matrice di numeri interi (documento con i testi e le soluzioni degli esercizi: esercitazione05.pdf).

Lezione n. 17 - martedì 23 novembre 2010

• Algoritmo Quick Sort: riepilogo della pseudo-codifica, calcolo della complessità computazionale, codifica in linguaggio C, esempi.
• Algoritmo Merge Sort: algoritmo per la “fusione” di due array già ordinati, strategia di tipo “divide et impera” adottata dall'algoritmo di ordinamento per fusione, pseudo-codifica dell'algoritmo Merge Sort, calcolo della complessità computazionale, esempi.

Lezione n. 18 - mercoledì 24 novembre 2010

• Algoritmo Merge Sort: riepilogo della pseudo-codifica, codifica in linguaggio C, esempi.
• Pile, code, code di priorità: strutture dati di tipo pila (stack), coda (queue) e coda di priorità, cenni sull'implementazione delle operazioni di inserimento ed estrazione di elementi in pile, code e code di priorità, esempi.
• Heap: la struttura dati di heap, caratteristiche della struttura dati, algoritmi per l'implementazione delle operazioni di inserimento di un elemento e di estrazione del massimo, calcolo della complessità computazionale, esempi.

Esercitazione n. 7 - giovedì 25 novembre 2010

• Esercizi su array e file: generazione di numeri casuali in ordine crescente; scrittura su file e utilizzo di GNUplot per la visualizzazione di grafici (documento con i testi e le soluzioni degli esercizi: esercitazione06.pdf).

Lezione n. 19 - martedì 30 novembre 2010

• Algoritmo Heap Sort: la struttura dati di heap e le funzioni per l'inserimento di un elemento e l'estrazione del massimo; strategia dell'algoritmo di ordinamento merge sort, pseudo codifica dell'algoritmo, esempi, calcolo della complessità computazionale (vedi la codifica in linguaggio C dell'algoritmo). Appunti riepilogativi sugli algoritmi di ordinamento .
• Strutture e allocazione dinamica della memoria: l'istruzione struct per la definizione di strutture composte da più campi, array di strutture, esempi; allocazione della memoria mediante le funzioni malloc e sizeof, esempi.

Lezione n. 20 - mercoledì 1 dicembre 2010

• Liste: definizione di una struttura per la rappresentazione di una lista, utilizzo delle funzioni malloc e sizeof per l'allocazione degli elementi di una lista, funzione per la costruzione di una lista come una pila, funzione per la stampa degli elementi di una lista; funzione per la cancellazione di elementi di una lista, la funzione free, esempi.

Esercitazione n. 8 - giovedì 2 dicembre 2010

• Esercizi sulle liste: eliminzione di elementi di una lista, concatenazione di liste, fusione di liste ordinate (documento con i testi e le soluzioni degli esercizi: esercitazione07.pdf).

Lezione n. 21 - martedì 7 dicembre 2010

• Cenni sulla teoria dei grafi: definizione di grafo orientato e non orientato, cammino, cammino semplice, ciclo, cappio, grafo connesso, grafo fortemente connesso, albero, albero ricoprente, isomorfismo tra grafi (scarica il documento: “Appunti sulla teoria dei grafi”).
• Strutture dati per la rappresentazione di grafi e alberi: rappresentazione mediante matrici di adiacenza e mediante liste di adiacenza, esempi in linguaggio C, calcolo del massimo grado uscente dei vertici di un grafo G rappresentato mediante liste di adiacenza.

Esercitazione n. 9 - giovedì 9 dicembre 2010

• Esercizi sulle liste: compressione di sequenze numeriche con l'algoritmo RLE (Run Length Encoding), decompressione, sottoliste prive di intersezione (documento con i testi e le soluzioni degli esercizi: esercitazione08.pdf).

Lezione n. 22 - giovedì 9 dicembre 2010

• Visita in ampiezza di un grafo: il problema della visita di un grafo, la strategia della visita in ampiezza, l'algoritmo BFS (Breadth First Search), pseudo-codifica dell'algoritmo, calcolo della complessità computazionale, esempi.
• Applicazioni della visita in ampiezza di un grafo: verifica della connessione di un grafo, verifica della presenza di cicli, identificazione dei cammini di lunghezza minima per raggiungere i vertici di un grafo a partire da una sorgente fissata, caratteristiche degli alberi di visita prodotti dall'algoritmo BFS.

Lezione n. 23 - martedì 14 dicembre 2010

• Visita in ampiezza di un grafo: codifica in linguaggio C dell'algoritmo BFS; approfondimento sull'implementazione della struttura dati per la gestione di una coda e delle funzioni per compiere le operazioni di inserimento e di estrazione di un elemento; puntatori a puntatori.
• Visita in profondità di un grafo: strategia della visita in profondità di un grafo, pseudo codifica dell'algoritmo DFS (Depth First Search), calcolo della complessità, esempi; applicazioni dell'algoritmo DFS (verifica della connessione di un grafo non orientato, verifica della presenza di cicli, parsing di un'espressione aritmetica in notazione polacca inversa). Visualizza la codifica in linguaggio C dell'algoritmo DFS.

Lezione n. 24 - mercoledì 15 dicembre 2010

• Ordinamento topologico: ordinamento topologico dei vertici di un grafo orientato aciclico (DAG - Directed Acyclic Graph), applicazioni dell'ordinamento topologico, utilizzo dell'algoritmo DFS per il calcolo dell'ordinamento topologico.
• Cammini minimi con sorgente singola: descrizione del problema della ricerca di cammini minimi su un grafo con pesi non negativi assegnati agli spigoli, algoritmo di Dijkstra, pseudo-codifica dell'algoritmo, esempi, calcolo della complessità computazionale. Visualizza la codifica in linguaggio C dell'algoritmo di Dijkstra.

Esercitazione n. 10 - giovedì 16 dicembre 2010

• Esercizi sui grafi: calcolo del grado entrante dei vertici di un grafo orientato, costruzione del “grafo intervallo”, costruzione del grafo bibartito completo (documento con i testi e le soluzioni degli esercizi: esercitazione09.pdf).

Lezione n. 25 - lunedì 20 dicembre 2010

• Classi di complessità per problemi: problemi di decisione, di ricerca, di enumerazione e di ottimizzazione, complessità di un algoritmo e di un problema, la classe di complessità P dei problemi risolubili mediante un algoritmo di complessità polinomiale, la classe di complessità NP dei problemi la cui soluzione può essere verificata con un algoritmo di complessità polinomiale, riducibilità polinomiale di un problema ad un altro, problemi NP-completi, il problema “P=NP”, esempi di problemi NP-completi (vedi le dispense sulla complessità degli algoritmi e dei problemi).

Author: Marco Liverani - Last modified: Sunday November 27, 2011 - URI: http://www.mat.uniroma3.it/users/liverani/IN110/lezioni.shtml