Link al canale Moodle e-learning

https://matematicafisica.el.uniroma3.it/course/view.php?id=224

Link al canale Microsoft Teams del Corso:

https://teams.microsoft.com/l/team/19%3a2e48b7b09eb44c509e75cc020de6e617%40thread.tacv2/conversations?groupId=258a8026-477e-4000-b9c8-85cfb30e5ed9&tenantId=ffb4df68-f464-458c-a546-00fb3af66f6a

Link al blocco appunti delle esercitazione (chiedere la password al docente, Elia Onofri)

https://uniroma3-my.sharepoint.com/:o:/g/personal/eonofri_os_uniroma3_it/Er6hM-TGiVhIjCpQl8llk-8Bp5-SgJSin4EmXhhyCTpreg?e=Kk9n9B

Diario delle lezioni, delle esercitazioni e dei tutorati:

• Lezione #1 - Lunedì 21 Settembre ore 10-14. Presentazione del corso (scarica le slides). Un approccio intuitivo alla progettazione di algoritmi mediante alcuni esempi elementari: "calcolare e stampare i primi 10 multipli di un intero positivo X"

• Lezione #2 - Martedì 22 Settembre, ore 11-14. Esecutore e algoritmi: problema e istanza di un problema, caratteristiche dell'esecutore, compiti del progettista degli algoritmi, capacità del calcolatore/esecutore; algoritmi; esempi di pseudo-codifica di algoritmi per la soluzione di problemi elementari: calcolare primi k multipli di n; trovare il massimo (o il minimo) elemento in una sequenza di n numeri interi (Scarica esempi visti a lezione). Linguaggi imperativi. Algoritmi, diagrammi di flusso, programmazione strutturata: linguaggi imperativi, istruzioni fondamentali di un linguaggio imperativo, rappresentazione di algoritmi mediante diagrammi di flusso, strutture algoritmiche di tipo sequenziale, iterativa, condizionale; regole della programmazione strutturata, cenni sul Teorema Fondamentale della Programmazione Strutturata di Jacopini e Böhm; esempi (scarica il documento: “Algoritmi e diagrammi di flusso”).

• Lezione #3 - Venerdì 25 Settembre, ore 10-12. Algoritmi, diagrammi di flusso, programmazione strutturata. A) Calcolare la sommatoria dei primi n naturali. Calcolare la sommatoria dei primi N interi usando solo la formula della sommatoria di Gauss (1+2+3+...+N)=(N*(N+1)/2). B) Trovare se esiste la radice quadrata di un numero naturale (cioè, dato un intero n>0, stabilire se esiste un intero i tale che n=i*i). C) Fissato un intervallo [a,b] con b>a>0 e data una sequenza di n>0 numeri interi , per ogni numero della sequenza, stabilire se appartiene o meno all'intervallo fissato. (Scarica esempi visti a lezione).

• Lezione #4 - Lunedì 28 Settembre, ore 10-14. 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. 1) Stabilire se n>0 è pari. 2) Dati due interi x>y>0 stabilire se y divide x. Calcolare il quoziente e il resto della divisione intera x/y. 3) Calcolare il Minimo Comune Multiplo di due interi positivi x ed y. 4) Data una sequenza di n numeri X1,X2,...,Xn stabilire se è ordinata in senso strettamente crescente, cioè per ogni i<n deve valere Xi<Xi+1. 5). Allgortimo di Euclide per il calcolo del Massimo Comun Divisore di due interi X ed Y. Dato un intero N>1, stabilire se è un numero primo. Calcolare e stampare i primi N multipli di un intero K>0 facendo solo uso della operazione di successore (succ: N-->N+1). (scarica gli esempi visti a lezione ed il documento “Algoritmi e diagrammi di flusso”).

• Lezione #5 - Martedì 29 Settembre, ore 11-14. Linguaggi di programmazione: classificazion dei linguaggi in base al paradigma di programmazione, alcuni esempi; linguaggi di programmazione di basso livello e di alto livello, linguaggio macchina; processo di traduzione del codice da linguaggio di programmazione di alto livello (codice sorgente) a linguaggio macchina (codice binario eseguibile), esecuzione del programma; interpreti e compilatori. Esempi di programmi in C e Python. (scarica il documento: “Appunti sui linguaggi di programmazione”). Modelli di Calcolo: macchine di Turing, il problema dell'arresto delle Macchine di Turing, problemi (matematici) non decidibili algoritmicamente. Cenni sulla Tesi di Church-Turing. Un esempio di algoritmo del quale non si conosce una dimostrazione della sua terminazione per ogni numero naturale n (scarica il documento: “Appunti sui modelli di calcolo").

• Lezione #6 - Venerdì 2 Ottobre, ore 10-12. Rappresentazione delle informazioni: Teorema della rappresentazione posizionale dei numeri in una base; codifica dei numeri naturali in base 10, in base 2, in base ottale ed in base esadecimale; cenni alla rappresentazione dei numeri in virgola mobile (float points) (scarica il documento: “Appunti sulla codifica delle informazioni”).

• Lezione #7 - Lunedì, 5 Ottobre, ore 10-14. 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 locali e globali, assegnazione di valori alle variabili, allocazione delle variabili in memoria e operatore “&”, esempi; la struttura di controllo condizionale "if (condizione) {blocco istruzioni} else {blocco istruzioni}"; le stutture di controllo iterativo (for(istruz. iniz. ; cond. finale ; incremento){blocco istruzioni}, while (condizione) {blocco istruzioni}, do {blocco istruzioni} while (condizione)). Scarica: il documento: “Appunti sul linguaggio C” e gli esempi visti a lezione (file compresso .zip).

• Lezione #8 - Esercitazione #0 - Martedì, 6 Ottobre, ore 11-14 (in Laboratorio ed aula M3): Introduzione all'uso del laboratorio informatico: struttura del laboratorio e della sua rete, accesso alle postazioni di lavoro, accesso al server mediante il protocollo SSH, accesso al server mediante connessioni Internet dall'esterno (scarica il documento: “Accesso alle risorse del laboratorio informatico del Dipartimento di Matematica” e le slide sull'uso del laboratorio informatico; si suggerisce di prendere visione anche del documento “UNIX: introduzione elementare” per una migliore comprensione dell'uso della shell del sistema operativo UNIX/Linux). Programmazione in C: scrittura di un programma in linguaggio C, compilazione, debugging ed esecuzione. Turni degli studenti ammessi al laboratorio.

• Lezione #9 - Venerdì 9 Ottobre, ore 12-14. Introduzione al linguaggio C: operatori aritmetici, operatori aritmetici in forma compatta, operatori di confronto, espressioni logiche, connettivi logici "not, and, or, xor, implicazione", tavole di verità dei connettivi logici, valutazione di espressioni booleane, esempi. L'operatore cast. Esempi di programmi C: 1) Fissato un intervallo di interi [a,b] stampare tutti i numeri pari compresi nell'intervallo; 2) letta una sequenza di n>1 numeri interi, stampare la loro somma e la media; 3) leggere una sequenza di numeri e stabilire se sono ordinati in senso strettamente crescente ("<"). Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C.

• Lezione #10 - Lunedì 12 Ottobre, ore 10-14. Esempi di programmi in C: 1) Letto un numero reale b (base) ed un intero n>=0 (esponente), calcolare e stampare la "potenza ottenuta elevando b ad n" (b^n). 2) letto un intero n>1, stabilire se è primo. 3) Letti due interi a, b, memorizza (alloca) in a il max ed in b il min dei due interi letti. Scrivere la versione built-in dell'algoritmo e la versione con chiamata di una funzione esterna che scambia i valori quando a<b, usando le variabili puntatori a variabili di tipo intero (operatori unari *(.) ed &()). 4) Usando il metodo dicotomico (o divide et impera), indovinare nel minor numero possibile di mosse/tentativi, un numero scelto dall'utente nell'intervallo {1,2,3,...,n}. Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C. Scarica il documento di Introduzione alla progettazione di algoritmi e programmi scritti in C.

• Esercitazione #1 - Martedì 13/10, ore 11-14. 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 + materiale visto in laboratorio).

• Lezione #11 - Venerdì 16 Ottobre, ore 10-12. Programmi in C: funzioni ricorsive, variabili puntatori, operatori unari &(.) ed *(.). Es.1) Scrivere la versione iterativa e la versione funzionale dell'algoritmo che calcola il fattoriale di un intero n>0 (Definizone iterativa: n!=1*2*3*...*n. Definizione induttiva: n!=n*(n-1)! se n>1, altrimenti n!=1). 2) algoritmo ricorsivo del massimo comune divisore di due interi MCD(a,b) e del minimo comune multiplo di due interi m.c.m.(a,b). Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C.

• Lezione #12 - Lunedì 19 Ottobre, ore 10-12. Array (definizione ed allocazione di memoria): array monodimensionali (vettori), dichiarazione di array, allocazione in memoria di un array. Esempi: 1) Letto un array di n<=100 numeri reali, stampa il max ed il min. 2) Letto un array di n numeri reali, stampa solo i numeri che sono >= della media degli n numeri. 3) stampa gli indirizzi di memoria di tutte la variabili allocate in un array; 4) leggere e stampare un array di interi mediante chiamata di due funzioni esterne alla main part del programma (leggi_array e stampa_array). Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C.

• Tutorato #1 - Lunedì 19/10 (ore 12-14). Scarica gli esercizi svolti in laboratorio: tutorato_01.

• Esercitazione #2 - Martedì 20/10, ore 11-14. Esercizi sugli array: operazioni sugli array: intersezione, differenza, inversione (Scarica il documento con i testi e le soluzioni degli esercizi: esercitazione02.pdf + il materiale visto in laboratorio).

• Lezione #13 - Venerdì 23 Ottobre, ore 10-12. Stringhe di caratteri: rappresentazione di stringhe di caratteri come array, il carattere nullo “\0” di terminazione di una stringa, le funzioni printf e scanf con le stringhe. Esempi: 1) Letta in input una stringa di caratteri, trasformare le lettere minuscole in lettere maiuscole. 2) Letta una stringa, stabilire se è palindroma. Esercizi su array di interi: 1) leggi un array di interi ed invertilo senza usare altri array;2) letti due array di interi, A e B, calcolare e stampare la loro intersezione e differenza (A-B). Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C.

• Lezione #14 - Lunedì 26/10, ore 10-12 (su Teams). Array multidimensionali: array di array (definizione ed allocazione di memoria di matrici). Esempi: 1) leggere e stampare una matrice di N-righe x M-colonne di numeri reali (float A[N][M]). 2) Leggere una matrice quadrata NxN di numeri reali e stampare la diagonale principale e quella secondaria. 3) Leggere una matrice quadrata di NxN reali e allocare le diagonali principale e secondaria, rispettivamente, nella prima e nella seconda riga di una nuova matrice float B[2][N]. Scarica gli esempi visti a lezione: algoritmi e sorgenti programmi C.

• Tutorato #2 - Lunedì 26/10, ore 12-14. Scarica gli esercizi svolti in laboratorio: tutorato_3(a)

• Esercitazione #3 - Martedì 27/10. Esercizi sulle stringhe e sulle matrici: Letta una parola S, stabilire se S è palindroma (ossia se è simmetrica); acquisire in input un array A di n numeri interi minori di 100; per ogni elemento di A stampare il numero di volte che compare nel vettore; letta in input una matrice A di n × m numeri interi, stampa la colonna con il maggior numero di elementi dispari (Scarica il documento con i testi e le soluzioni degli esercizi: esercitazione03.pdf ed il materiale visto in laboratorio).

• LEZIONE #15 - Venerdì 30/10 ore 10-12 (su Teams). Numeri pseudo-casuali: generazione di sequenze di numeri pseudo-casuali, le funzioni srand e rand, esempi per la generazione di numeri interi pseudo-casuali nell'intervallo [a, b]. Esempi: 1) Generare n numeri interi pseudo-casuali. 2) Generare un array di numeri interi casuali nell'intervallo [a,b] (estremi inclusi). 3) Generare una stringa di caratteri casuali maiuscoli (e minuscoli). 4) Generare un array di n<=100 numeri interi casuali <100 senza ripetizioni (un intero x, t.c., 0<=x<100, può occorrere al massimo una volta nell'array). (Scarica le slides ed i sorgenti programmi C esempi in C visti a lezione).

• Lezione #16 - Lunedì 2 Novembre, ore 10-12 (su Teams). Esercizio n.1. Scrivere il diagramma a blocchi, lo pseudo-codice ed il programma C corrispondente al Crivello di Eratostene il quale dato n>0 pemette di calcolare tutti i numeri primi compresi tra 2 ed n. Esercizio n.2: Leggere e stampare un array di array di array di interi tutti della stessa dimensione n (cioè, un "cubo" di numeri interi). Scarica le slides viste a lezione e i sorgenti C degli esercizi .

• Tutorato #3 - Lunedì 2 Novembre, ore 12-14. Scarica il testo 3(b).

• Esercitazione #4 - Martedì 3 Novembre, ore 11-14. Esercizi su vettori di caratteri e su matrici: array di numeri casuali, riconoscimento di stringhe, trasformazione di stringhe in caratteri maiuscoli. (Scarica il testo dell'esercitazione04.pdf ed il materiale visto in laboratorio).

• Lezione #17 - Venerdì 6 Novembre, ore 10-12 (su Teams). Allocazione dinamica della memoria: le funzioni sizeof e malloc della libreria stdlib.h del C; allocazione dinamica di un array, esempi. Strutture: definizione di strutture, la parola chiave struct, variabili di tipo struttura, puntatori a strutture, array di strutture. Scarica le slides viste a lezione e i sorgenti C dei programmi .

• Tutorato #4 - Lunedì 9 Novembre, ore 12-1 (Scarica il testo con gli esercizi) .

• Esercitazione #X - Martedì 10 Novembre, ore 11-14. Simulazione Esonero (Testo della prova con le soluzioni proposte + materiale visto in laboratorio).

• Primo Esonero: Mercoledì 11 Novembre 2020, ore 1030-1330, Aule M1 ed M3 (Scarica il testo con le soluzioni proposte).

• Lezione #18 - Lunedì 16/11, ore 10-12. 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, diagramma di flusso, codifica in linguaggio C, esempi. 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à. (Scarica le slides viste a lezione).

• Tutorato #5 - Lunedì 16/11 ore 12-14 (Scarica il testo con le soluzioni del tutorato_05).

• Esercitazione #5- Martedì 17/11. Esercizi su array: funzioni per la lettura e la scrittura di dati su file di testo, esercizio per la generazione di un file di dati da visualizzare graficamente con GNUplot; esercizi su array (documento con i testi e le soluzioni degli esercizi: esercitazione05.pdf + il materiale visto in laboratorio).

• Lezione #19 -Venerdì 20/11. Algoritmo Insertion Sort: strategia risolutiva dell'algoritmo Insertion Sort, pseudo-codifica, diagramma di flusso, 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, pseudo-codifica dell'algoritmo, calcolo della complessità computazionale, esempi (in questa pagina è disponibile la codifica in linguaggio C dell'algoritmo Bubble Sort). Scarica le slides viste a lezione.

• Lezione #20 - Lunedì 23/11. Algoritmo Quick Sort: strategia risolutiva “divite et impera” dell'algoritmo Quick Sort, profondità di un albero binario completo, pseudo-codifica dell'algoritmo, complessità nel caso migliore e nel caso peggiore. 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. ((Scarica le slides viste a lezione. Scarica la cartella compressa .ZIP contenente pseudo-codifica e codifica in linguaggio C degli algoritmi Quick Sort & Merge Sort).

• Tutorato #6 - Lunedì 23/11. (Scarica il testo con le soluzioni del tutorato_06).

• Esercitazione #6 - Martedì 24/11. Esercizi su array e matrici: esercizi su vettori 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: esercitazione06.pf). (Scarica il materiale visto in laboratorio).

• Lezione #21 - Venerdì 27/11. Code di priorità e Heap: la struttura dati di heap, caratteristiche della struttura dati, algoritmi per l'inserimento di un elemento e l'estrazione dell'elemento massimo, esempi. Algoritmo Heap Sort: strategia dell'algoritmo di ordinamento heap sort, pseudo codifica dell'algoritmo, esempi, calcolo della complessità computazionale (Scarica le slides e la la codifica in linguaggio C dell'algoritmo). Errata-corige: attenzione, nel testo di Liverani, a pagina 260, riga 5 del codice sostituire il simbolo ">" con "<". Da notare che l'algortimo è corretto anche senza le righe 14-16 perchè se i=n/2 allora 2i=n, ma H_n è diventata la nuova posizione disponibile dell'heap (H_0=n), quindi non ha senso il confronto H_i con H_2i=n.

• Lezione #22 - Lunedì 30/11. Strutture dati: definizione di strutture (nuovi tipi di dato) medi la parola chiave struct; variabili di tipo struttura, puntatori a strutture, array di strutture. Esempio: creare una lista di studenti con nome, età ed indirizzo composto da via e numero civico (scarica il codice C del programma). Introduzione alle liste: pile e code.

• Tutorato #7 - Lunedì 30/11. (Scarica il testo con le soluzioni del tutorato_07).

• Esecitazione #7 - Martedì 1 Dicembre. Esercizi sull'allocazione dinamica di vettori e matrici (scarica il file + il materiale visto in laboratorio).

• Lezione #23 - Venerdì 4 Dicembre 2020. Inserimento ("impilamento ed accodamento") di elementi (numeri interi) in una lista implementata come Pila e come Coda (vedi le slides su One-Note).

• Lezione #24 - Lunedì 7/12. Code e Pile con le liste (... continua): funzione per l'impilamento e accodamento di elementi; la cancellazione di elementi da una lista; funzione ricorsiva per la stampa "reverse" di una lista (Scarica la cartella compressa dei dei programmi C sulle liste visti a lezione).

• Esercitazione #8 - Mercoledì 5/12. 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 + il materiale visto in laboratorio).

• Lezione #25 - Venerdì 11/12. Cenni sulla teoria dei grafi: definizione di grafo orientato e non orientato, adiacenza, incidenza di un arco su un vertice, grado (entrante ed uscente) di un nodo; stella/link di un vertice; sottografo, grafo indotto, grafo completo, grafo bipartito, clique; definizione di cammino, cammino semplice, cammino chiuso, ciclo, grafo connesso, grafo orientato fortemente connesso, esempi; Teorema di Eulero-Poincarè sull'invarianza geometrica dei grafi; definizione di albero libero, albero radicato, Teorema di caratterizzazione degli alberi; spanning tree, esempi; cenni sulla rappresentazione di un grafo/albero mediante liste di adiacenza e matrici di adiacenza; menzione di alcuni fondamentali algoritmi sui grafi (scarica il documento: “Appunti sui grafi”).

Strutture dati per la rappresentazione di grafi e alberi: rappresentazione mediante matrici di adiacenza e mediante liste di adiacenza, esempi. Operazioni sulle liste di adiacenza di un grafo: codifica in C delle funzioni che implementano alcune operazioni di base sulle strutture dati di lista di adiacenza di un grafo: funzioni leggiGrafo, stampaGrafo, la funzione adiacenti(i,j) che verifica se due vertici (i, j) sono adiacenti, le funzioni gradoEntrante e gradoUscente per il calcolo del grado di un vertice del grafo e calcolo nodi sorgente e pozzo di un grafo. Codifica in C del programma che consente di leggere e stampare un grafo mediante matrici di adiacenza. (Scarica i sorgenti dei programmi C visti a lezione).

• Lezione #26 - Lunedì 14/12. Visita in ampiezza di un grafo: il problema della visita di un grafo G=(V,E), la strategia della visita in ampiezza, l'algoritmo BFS (Breadth First Search), pseudo-codifica dell'algoritmo, calcolo della complessità computazionale (O(|V|+|E|)), esempi, codifica in linguaggio C dell'algoritmo BFS. 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. (Scarica le slides viste a lezione corrette).

• Esercitazione #9 - Martedì 15/12: scarica testo e soluzioni della Esercitazione + il materiale visto in laboratorio.

• Lezione #27 - Venerdì 18/12. Visita in profondità di un grafo: strategia della visita in profondità di un grafo G=(V,E), pseudo codifica dell'algoritmo DFS (Depth First Search), calcolo della complessità O(|V|+|E|), esempi, codifica in linguaggio C dell'algoritmo DFS. Applicazioni della visita in profondità: Teorema delle Parentesi, Teorema dell'Ordinamento Topologico dei vertici di un grafo orientato aciclico DAG(Scarica le slides viste a lezione) .

ATTENZIONE! la prossima lezione si terrà martedì 22 alle ore 11 sul canale teams; l'esercitazione del 22 verrà anticipata a lunedì 21, ore 10-12.

• Esercitazione #10 - Lunedì 21/12. Esercizi sulle liste e sui grafi: costruzione di un "grafo intervallo", costruzione di un grafo completo bipartito, calcolo del grado entrante dei vertici di un grafo orientato (scarica il testo con gli esercizi).

• Tutorato #10 - Lunedì 21/12 (scarica il testo con gli esercizi).

• Lezione #28 - Martedì 22/12. Il problema del cammino minimo da una sorgente singola: descrizione del problema della ricerca dei cammini di peso minimo su un grafo con pesi non negativi assegnati agli spigoli, cenni preliminari sul “principio del rilassamento” adottato dall'algoritmo di E. W. Dijkstra . Algoritmo di Dijkstra: pseudo-codifica dell'algoritmo di Dijkstra per il calcolo dei cammini di peso minimo da una sorgente singola su un grafo: terminazione, correttezza ed analisi della complessità computazionale. (Scarica le slides viste a lezione + la codifica in linguaggio C dell'algoritmo.