25 Febbraio 2025
- Introduzione al corso:
iscrizioni, modalità di esame.
- Presentazione del libro di testo
(CLRS).
- Obiettivi del corso: paradigmi
algoritmici e algoritmi per problemi notevoli.
- Ricapitolazione:
prerequisiti da ripassare (App. A e B e Capp. 1, 2 e 3 del CLRS).
- Definizione di problema, istanza,
taglia di un'istanza e algoritmo che risolve un problema.
- Esempi di specifica di problemi computazionali: somma di interi, raggiungibilità su grafi diretti.
- Esempi di specifica di problemi computazionali: ordinamento.
27 Febbraio 2025
- Analisi di un algoritmo: correttezza e complessità
- Complessità in tempo di un algoritmo su
una singola istanza. Metriche riassuntive di complessità: caso peggiore, migliore, medio .
Il paradigma Divide-and-Conquer.
- Proprietà di sottostruttura
|
