Informatica, terzo canale,
|
Obiettivi | Programma | Materiale didattico |
Orario delle lezioni | Ricevimento studenti | Modalità d'esame |
Diario delle lezioni |
I tutor del corso, Andrea Cadoli e Francesco Teodori, hanno cresto un gruppo Telegram dedicato agli studenti per risolvere problemi legati all'installazione e all'uso del software, e alla soluzione dei problemi proposti.
Al gruppo non partecipa alcun docente, e i tutor potranno comunicare ai docenti il contenuto delle richieste ricevute solo se necessario, e comunque in forma anonima.
Il gruppo per il terzo canale è su
https://t.me/+gHynhfkpDhxjNTU0
Per commenti e segnalazioni,
contatta il docente all'indirizzo
paoloQUIUNPUNTOfranciosaQUIUNACHIOCCIOLAuniroma1QUIUNPUNTOit
Vengono presentati alcuni algoritmi fondamentali per problemi di ordinamento, ricerca e selezione, alcuni problemi numerici, evidenziandone le caratteristiche di efficienza attraverso l'analisi di complessità asintotica.
Vengono descritti i principali metodi di codifica dell'informazione.
Alla fine del corso lo studente sarà in grado di:
Componenti di un sistema di elaborazione: hardware, software, principali unità periferiche. Interazione con un sistema operativo basato su finestre. Il sistema operativo: funzioni principali, gestione dei processi, gestione della memoria, file system. Concetto di cartella, documento, applicazione/programma.
Rappresentazione dell'informazione: codifica di informazioni numeriche - sistemi di numerazione posizionali, codifica binaria, ottale, esadecimale, conversioni di base. Rappresentazione di numeri interi negativi. Rappresentazione in virgola mobile. Codifica di caratteri.
Concetto di algoritmo. Esempi di algoritmi in linguaggio naturale. Generalità sui linguaggi di programmazione, compilatori.
Programmazione in linguaggio Python: uso dell'interprete interattivo, ambienti di programmazione, preparazione di script in linguaggio Python. Costrutti essenziali del linguaggio: variabili, espressioni. Assegnazioni, metodi di input/output, istruzioni di selezione, ed iterazione. Sequenze, slicing di sequenze. Definizione di funzioni, parametri. Accesso a file e scrittura su file. Consultazione della documentazione Python. Principi di programmazione orientata agli oggetti.
Algoritmi fondamentali: Ricerca sequenziale, ricerca dicotomica su un vettore ordinato. Ordinamento: selection sort, merge sort, quick sort, bubble sort. Algoritmo di Euclide per la ricerca del Massimo Comun Divisore (MCD). Algoritmo per la ricerca del k-esimo elemento. Algoritmi di base su matrici.
Introduzione alla complessità computazionale: concetto di complessità di un algoritmo, notazioni asintotiche. Equazioni di ricorrenza e metodi per la loro soluzione. Complessità computazionale degli algoritmi studiati.
La votazione deriva dalla media dei voti riportati nella prova di programmazione e nella prova scritta, integrata eventualmente dall'esito del colloquio. È necessario riportare la sufficienza sia nella prova di programmazione che nella prova scritta. Il colloquio è richiesto a discrezione del docente.
È possibile sostenere le prove di teoria e di programmazione in appelli diversi. Il risultato di ciascuna delle prove viene mantenuto valido per tutto l'anno accademico (per il 2022-2023, fino all'appello di Gennaio 2024 compreso).
Se uno studente si presenta a un appello per sostenere una prova perde comunque il voto eventualmente conseguito in un appello precedente per la stessa prova, anche se decide di non consegnare l'elaborato.
19 Settembre 2022 | 20 Settembre 2022 | 22 Settembre 2022 (lab) |
26 Settembre 2022 sospesa per elezioni politiche |
27 Settembre 2022 | 29 Settembre 2022 (lab) |
3 Ottobre 2022 | 4 Ottobre 2022 | 6 Ottobre 2022 (lab) |
10 Ottobre 2022 | 11 Ottobre 2022 | 13 Ottobre 2022 (lab) |
17 Ottobre 2022 | 18 Ottobre 2022 | 20 Ottobre 2022 (lab) |
24 Ottobre 2022 | 25 Ottobre 2022 | 27 Ottobre 2022 (lab) |
31 Ottobre 2022 sospensione |
1 Novembre 2022 festività |
3 Novembre 2022 (lab) |
7 Novembre 2022 | 8 Novembre 2022 | 10 Novembre 2022 (lab) |
14 Novembre 2022 sospensione |
15 Novembre 2022 | 17 Novembre 2022 (lab) |
21 Novembre 2022 | 22 Novembre 2022 | 23 Novembre 2022 lab on-line |
aula II 24 Novembre 2022 |
28 Novembre 2022 | 29 Novembre 2022 | 1 Dicembre 2022 (lab) |
5 Dicembre 2022 | 6 Dicembre 2022 | tutoring on-line 9 Dicembre 2022 ore 10-12 https://meet.google.com/fmu-kfon-bxn |
12 Dicembre 2022 | 13 Dicembre 2022 | 15 Dicembre 2022 (lab) con simulazione esame |
19 Dicembre 2022 |
Per commenti e segnalazioni,
contatta il docente all'indirizzo
paoloQUIUNPUNTOfranciosaQUIUNACHIOCCIOLAuniroma1QUIUNPUNTOit
19 Settembre 2022 | |
---|---|
Argomenti |
|
torna all'elenco delle lezioni
20 Settembre 2022 | |
---|---|
Argomenti |
|
torna all'elenco delle lezioni
22 Settembre 2022 - lab | |
---|---|
Argomenti |
Cenni sulla struttura di un file system gerarchico: dischi logici, files, cartelle
Uso della shell Linux (o Terminale in Mac OS, o Prompt dei comandi in Windows) Navigazione nel file system: comando Uso dell'interprete Python 3 in modalità interattiva Operatori aritmetici, espressioni, variabili, assegnazioni Esempi di semplici problemi risolubili in modalità interattiva La funzione |
torna all'elenco delle lezioni
27 Settembre 2022 | |
---|---|
Argomenti |
Script vs. modalità interattiva, uso dell'ambiente Thonny, uso del debugger Funzioni Espressioni, precedenza tra operatori, valutazione di una espressione: albero sintattico Istruzione di assegnazione, binding nome - valore Regole per la definizione di identificatori, parole riservate Funzioni di conversione Stringhe, operatori su stringhe Errori sintattici, errori semantici, eccezioni Uso di funzioni matematiche con |
Materiale |
Un tutorial per l'installazione di Python3 in ambiente Windows è disponibile su https://www.youtube.com/watch?v=ij1HTDpVTBI (a cura del prof Massimo Lauria) |
Esercizi proposti |
Verificare, utilizzando l'interprete Python 3, qual è il massimo valore Verificare, utilizzando l'interprete Python 3, qual è il massimo valore Verificare qual è il comportamento dell'interprete in presenza di due operatori adiacenti dello stesso tipo: p.es. Sperimentare la differenza tra l'operatore Esprimere 8430 secondi in ore, minuti e secondi. Generalizzare il problema precedente immettendo da tastiera il numero di secondi. Calcolare quanti secondi sono 3 ore, 5 minuti e 18 secondi Generalizzare il problema precedente immettendo da tastiera il numero di ore, minuti e secondi. Trovare la lunghezza dell'ipotenusa di un triangolo rettangolo i cui cateti misurano rispettivamente 18.6 metri e 15 metri Generalizzare il problema precedente immettendo da tastiera le misure dei cateti. |
torna all'elenco delle lezioni
29 Settembre 2022 (lab) | |
---|---|
Argomenti |
Invocazione di metodi e uso del valore restituito Generazione di numeri pseudocasuali con Semplici programmi con Introduzione all'istruzione Operatori di confronto |
Esercizi proposti |
torna all'elenco delle lezioni
3 Ottobre 2022 | |
---|---|
Argomenti |
Istruzione Espressioni boolean, le costanti Indentazione del codice Istruzione Operatori logici Istruzione |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
4 Ottobre 2022 | |
---|---|
Argomenti |
Il problema dell'ordinamento per confronti: numero minimo di confronti per ordinare n numeri Chiamata di funzioni. Significato in una espressione.
Funzioni vuote, funzioni che restituiscono valori. Parametri ed argomenti. Funzioni di conversione. Definizione di funzioni con |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
6 Ottobre 2022 (lab) | |
---|---|
Argomenti |
Assegnazione con modifica: Esercizi sulla definizione di funzioni |
Esercizi proposti |
torna all'elenco delle lezioni
10 Ottobre 2022 | |
---|---|
Argomenti |
Stack di attivazione delle funzioni. Variabili locali.
Passaggio dei parametri. Assenza di effetti collaterali su parametri semplici. L'istruzione di ciclo Esercizi sull'uso di cicli e istruzioni condizionali |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
11 Ottobre 2022 | |
---|---|
Argomenti |
Esempi di definizione di funzioni con cicli. |
torna all'elenco delle lezioni
13 Ottobre 2022 (lab) | |
---|---|
Argomenti |
Uso di variabili boolean per il controllo di cicli Istruzione Esercizi sull'uso di cicli e istruzioni condizionali |
Esercizi proposti |
torna all'elenco delle lezioni
17 Ottobre 2022 | |
---|---|
Argomenti |
Istruzione Uso del Semplici programmi con cicli Esempi di programmi con cicli e istruzioni di selezione |
Listati ed esercizi proposti |
Somme di quadratiScrivere un programma che, dato in input un numero naturale n, stampa tutte le coppie di naturali x, y tali che x^2 + y^2 = z^2, con x, y, z ≤ n. Per n = 20 le soluzioni dovrebbero essere le seguenti: 3^2 + 4^2 = 5^2 5^2 + 12^2 = 13^2 6^2 + 8^2 = 10^2 8^2 + 15^2 = 17^2 9^2 + 12^2 = 15^2 12^2 + 16^2 = 20^2 Soluzione: cercaTernePitagoriche.py |
torna all'elenco delle lezioni
18 Ottobre 2022 | |
---|---|
Argomenti |
Algoritmo per approssimare uno zero di una funzione continua ricercaZero.py Esempi di programmi con cicli multipli e istruzioni di selezione Introduzione alle stringhe. Indicizzazione, funzione |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
20 Ottobre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercizi su stringhe, cicli. Slicing, metodi Istruzione Differenza tra:
Passaggio dei parametri con nome, parametri opzionali |
Listati ed esercizi proposti |
torna all'elenco delle lezioni
24 Ottobre 2022 | |
---|---|
Argomenti |
Esercizi su cicli, istruzioni condizionali, stringhe Liste Accesso e modifica di elementi di una lista. Scansione di liste con I metodi Costruzione di liste |
Listati ed esercizi proposti |
|
Materiale |
La prossima esercitazione si svolgerà secondo le modalità descritte nel video del prof. Massimo Lauria disponibile a questo link |
torna all'elenco delle lezioni
25 Ottobre 2022 | |
---|---|
Argomenti |
Esercizi su liste I metodi Implementazione della ricerca sequenziale su lista Liste disomogenee. Verifica del tipo degli elementi di una lista con la funzione |
Listati ed esercizi proposti |
Esercizi di base su liste:
Data in input una sequenza di interi che rappresentano frequenze:
Soluzione: frequenze.py |
torna all'elenco delle lezioni
27 Ottobre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercizi su liste. |
Listati ed esercizi proposti | Esercitazione 6 (soluzioni in soluzioni6.zip) |
torna all'elenco delle lezioni
3 Novembre 2022 (laboratorio) | |
---|---|
Argomenti |
Ricerca del massimo valore o della sua posizione in una lista non ordinata. Funzioni che creano liste Funzioni che modificano liste Esercizi su liste |
Listati ed esercizi proposti | Esercitazione 7 (soluzioni in soluzioni7.zip) |
torna all'elenco delle lezioni
7 Novembre 2022 | |
---|---|
Argomenti |
Algoritmo di ordinamento per selezione selectionSort.py Liste di liste per la rappresentazione di matrici. Esercizi su liste di liste:
|
torna all'elenco delle lezioni
8 Novembre 2022 | |
---|---|
Argomenti |
Introduzione alla ricorsione. Esempio di algoritmo ricorsivo per il calcolo del fattoriale
Esempio di algoritmo iterativo per il calcolo del fattoriale
Esempio di algoritmo ricorsivo per il calcolo di un elemento della sequenza di Fibonacci
Somma dei numeri contenuti in una lista di liste di liste ...
|
Riferimenti al testo | Cormen, Leiserson, Rivest oppure dispense a cura del prof. Massimo Lauria |
Listati proposti |
|
torna all'elenco delle lezioni
10 Novembre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercizi su liste bidimensionali. |
Listati ed esercizi proposti | Esercitazione 8 (soluzioni in soluzioni8.zip) |
torna all'elenco delle lezioni
15 Novembre 2022 | |
---|---|
Argomenti |
Ricerca binaria su liste ordinate. Complessità della ricerca binaria Algoritmo di ordinamento insertion sort Animazione di algoritmi di ordinamento visibile su https://www.toptal.com/developers/sorting-algorithms |
Riferimenti al testo | Cormen, Leiserson, Rivest oppure dispense a cura del prof. Massimo Lauria |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
17 Novembre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercizi su liste e liste bidimensionali. |
Listati ed esercizi proposti | Esercitazione 9 (soluzioni in soluzioni9.zip) |
torna all'elenco delle lezioni
21 Novembre 2022 | |
---|---|
Argomenti |
Algoritmo di ordinamento a bolle - Bubble Sort (codice Bubble sort semplice) e suoi miglioramenti (codice Bubble sort migliorato) Bubble Sort con flag per verifica ordinamento codice Bubble sort con flag Analisi della prestazioni del bubble sort Introduzione alla complessità computazionale Le notazioni asintotiche O(), Ω(), Θ() Complessità computazionale di: insertion sort, bubble sort, selection sort |
Link utili |
|
torna all'elenco delle lezioni
22 Novembre 2022 | |
---|---|
Argomenti |
Uso dele notazioni asintotiche O(), Ω(), Θ() Esempi di classi di funzioni Esercizio: calcolo dei numeri primi con il crivello di Eratostene Il paradigma divide et impera. Somma di una sequenza applicando il paradigma divide et impera
Introduzione all'algoritmo di ordinamento per fusione (merge sort) |
Riferimenti al testo |
dispense del corso, oppure Cormen, Leiserson, Rivest |
torna all'elenco delle lezioni
23 Novembre 2022 (laboratorio) | |
---|---|
Link |
La lezione si svolgerà on-line sulla piattaforma Zoom al link |
Argomenti |
Esercizi su stringhe di caratteri e liste. |
Listati ed esercizi proposti | Esercitazione 10 (soluzioni in soluzioni10.zip) |
torna all'elenco delle lezioni
24 Novembre 2022 | |
---|---|
Argomenti |
Algoritmo di ordinamento per fusione - Merge Sort (codice merge sort) Analisi della prestazioni del merge sort Confronto con la complessità minima possibile (lower bound) per il problema dell'ordinamento basato su confronti Algoritmo MCD di Euclide:
|
Link utili | Animazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms |
torna all'elenco delle lezioni
28 Novembre 2022 | |
---|---|
Argomenti |
Algoritmo di ordinamento Quick Sort (quickSort.py) Analisi della prestazioni del quick sort nel caso migliore e nel caso peggiore. Animazione del Quick Sort (quickSortAnimato.py), eseguire in Python3 |
Riferimenti al testo |
dispense del corso, oppure Cormen, Leiserson, Rivest |
Link utili | Aminazione di algoritmi di ordinamento https://www.toptal.com/developers/sorting-algorithms |
torna all'elenco delle lezioni
29 Novembre 2022 | |
---|---|
Argomenti |
Analisi della complessità computazionale di algoritmi ricorsivi.
Algoritmo per il calcolo del k-esimo elemento: selection.py Analisi di complessità dell'algoritmo per il k-esimo elemento Animazione del k-esimo elemento (selectionAnimato.py), eseguire in Python3 |
Listati ed esercizi proposti | Un elenco di esercizi di programmazione è disponible qui |
Riferimenti al testo |
dispense del corso, oppure Cormen, Leiserson, Rivest |
torna all'elenco delle lezioni
1 Dicembre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercitazione su matrici. |
Listati ed esercizi proposti | Esercitazione 11 (soluzioni in soluzioni11.zip) |
torna all'elenco delle lezioni
5 Dicembre 2022 | |
---|---|
Argomenti |
Lettura e scrittura di file di testo. Funzioni Metodi Ciclo |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
6 Dicembre 2022 | |
---|---|
Argomenti |
Dizionari: definizione, indicizzazione, scansione con ciclo |
Listati ed esercizi proposti |
Scrivere le seguenti funzioni, che hanno tutte come parametri un dizionario esami in cui ogni chiave è il titolo di un insegnamento e il corrispondente valore è il voto riportato, e un secondo dizionario crediti in cui ogni chiave è il titolo di un insegnamento e il corrispondente valore è il numero di crediti.
|
torna all'elenco delle lezioni
12 Dicembre 2022 | |
---|---|
Argomenti |
Codifica dell'informazione:
|
torna all'elenco delle lezioni
13 Dicembre 2022 | |
---|---|
Argomenti |
|
torna all'elenco delle lezioni
15 Dicembre 2022 (laboratorio) | |
---|---|
Argomenti |
Esercitazione su files e dizionari. |
Listati ed esercizi proposti |
|
torna all'elenco delle lezioni
19 Dicembre 2022 | |
---|---|
Argomenti |
Esercizi di teoria e programmazione |