Lezioni 1-2: martedì 25 febbraio 2020
Presentazione del corso Introduzione
Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
Esercitazione: mercoledì 26 febbraio 2020: ANNULLATA Lezioni 3-4: venerdì 28 febbraio 2020
Notazione asintotica (1)
Definizione e significato degli insiemi O, Ω e Θ.
Esempi.
Algebra della notazione asintotica.
Esempi.
metodo del limite.
Valutazione del costo computazionale di un algoritmo.
Pseudocodice.
Un primo esempio: costo computazionale di un programma che trova il massimo in un vettore
Esercizi assegnati:
Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
Calcolare l'ordine asintotico stretto di alcune funzioni assegnate
Lezioni 5-6: martedì 3 marzo 2020
Notazione asintotica (2)
Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
somma dei primi n interi
valutazione di un polinomio in un punto
Il problema della ricerca
ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
ricerca dicotomica e suo costo computazionale nel caso migliore, peggiore e medio
Esercitazioni 1-2: mercoledì 4 marzo 2020
Problemi, classi di Problemi, Soluzioni [ L1, sezioni 1 e 2 ]
TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D1, sezione 2 ]
Indagini su un programma iterativo [ L1, sez. 2.1 ]:
Precondizioni, Postcondizioni, invarianti di ciclo.
Terminazione di un ciclo: funzione di terminazione.
Esempi:
funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D1, sez. 3 ].
funzione che calcola il predecessore. Specifica come contratto.
Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.
Sperimentazioni: Disp. D1, sez. 2.1.
Venerdì 6 Marzo 2020: Lezioni sospese per emergenza Coronavirus
Dal 10 marzo sono iniziate le lezioni a distanza. Fino al loro termine il calendario delle lezioni, le informazioni per l'accesso ed il relativo materiale didattico sono pubblicati in una apposita pagina:Pagina delle lezioni a distanza