Diario delle lezioni

A.A. 2023/2024

Trovate in questa pagina il dettaglio degli argomenti svolti; il pdf delle slides utilizzate è qui.

Lunedì 26 Febbraio 2024 - Lezioni 1-2

Introduzione

  • Informazioni sul corso.
  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

Giovedì 29 Febbraio 2024 - Lezioni 3-4-5

Notazione asintotica

  • Definizione e significato degli insiemi O, Ω e Θ
  • Algebra della notazione asintotica
  • Metodo del limite
  • Esempi

Lunedì 4 Marzo 2024 - Lezioni 6-7

Valutazione del costo computazionale (1)

  • Pseudocodice
  • Valutazione del costo computazionale di un algoritmo
  • Un primo esempio
  • 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

Giovedì 7 Marzo 2024 - Lezioni 8-9-10

Valutazione del costo computazionale (2)

  • Esercizi svolti

Il problema della ricerca

  • ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
  • ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio

Lunedì 11 Marzo 2024 - Lezioni 11-12

Ricorsione (1)

  • funzioni matematiche ricorsive
  • algoritmi ricorsivi
  • fattoriale: pseudocodice iterativo e ricorsivo;
  • ricerca sequenziale: pseudocodice ricorsivo;
  • ricerca binaria: pseudocodice ricorsivo;
  • equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)
  • esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un array, minimo in un array, array palindromo): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza.

Giovedì 14 Marzo 2024 - Lezioni 13-14-15

Ricorsione (2)

  • esempi di algoritmi ricorsivi (stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Soluzioni delle equazioni di ricorrenza (1)

  • metodi risolutivi (1):
    • metodo iterativo
    • metodo di sostituzione;
    • metodo dell'albero.

Lunedì 18 Marzo 2024 - Lezioni 16-17

Soluzioni delle equazioni di ricorrenza (2)

  • metodi risolutivi (2):
    • metodo principale
  • esempi di soluzione di equazioni di ricorrenza (1)

Giovedì 21 Marzo 2024 - Lezioni 18-19-20

Soluzioni delle equazioni di ricorrenza (3)

  • esempi di soluzione di equazioni di ricorrenza (2)

Il problema dell'ordinamento (1)

  • algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;

Lunedì 24 Marzo 2024 - Lezioni 21-22

Soluzioni delle equazioni di ricorrenza (4)

  • esempi di soluzione di equazioni di ricorrenza (3)

Il problema dell'ordinamento (2)

  • albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti

Giovedì 28 Marzo 2024 e Lunedì 1 Aprile 2024 vacanze Pasquali

Giovedì 4 Aprile 2023 - Lezioni 23-24-25

Il problema dell'ordinamento (3)

  • algoritmi efficienti (1):
    • paradigma del Divide et Impera
    • merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
    • cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
    • quick sort (idea e pseudocodice)
    • pseudocodice della funzione Partiziona
    • un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)

AnniPrecedenti


This topic: Intro_algo/AD > WebHome > DiarioDelleLezioni
Topic revision: r77 - 2024-03-26 - TizianaCalamoneri
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback