2019 – 5AA

DIARIO DELLE LEZIONI

LIBRO DI TESTO

Paolo Camagni, Riccardo NikolassyINFOM@T 3 – HOEPLI


Algoritmi di calcolo numerico

Calcolo approssimato della radice quadrata

  1. Cenni sul calcolo numerico
  2. Calcolo della radice quadrata
  3. — Metodo scolastico, confronto
  4. Metodo alternativo di Newton

Generare numeri pseudocasuali

  1. Processi deterministici e pseudocasuali
  2. Numeri pseudocasuali (in Python)
  3. Algoritmi che generano le sequenze
  4. — Centro del quadrato
  5. Linear Congruential Generator (LCG)

Calcolo di π
Integrazione con il metodo Monte Carlo

  1. La ricerca di pi greco
  2. Il metodo di Archimede
  3. Il metodo Liu Hui e Zu Chongzhi
  4. Gregory, Leibniz e Eulero
  5. Qualche formula recente
  6. Ricordiamo i primi 14 decimali
  7. Il metodo Monte Carlo
  8. Calcolo di pi greco
  9. Integrazione numerica con il metodo Monte Carlo
  10. Il problema della moneta di Buffon

Il numero e (di Eulero)

  1. Generalità
  2. Calcolo del numero e
  3. Ricordare il numero e

Calcolo approssimato della radice di una equazione
Metodo di bisezione

  1. Generalità
  2. Metodo di bisezione

Calcolo approssimato delle aree

  1. Generalità
  2. — Funzioni di Geogebra
  3. Metodo dei rettangoli
  4. Metodo dei trapezi
  5. Metodo di Cavalieri-Simpson

Applicazioni tecnico-scientifiche

Algoritmi crittografici

Anagrammi
Permutazioni lessicografiche

  1. Premessa
  2. Permutazioni semplici
  3. Permutazioni con ripetizione
  4. Anagrammi e permutazioni lessicografiche

Speranza matematica
Gioco d’azzardo

  1. Premessa
  2. Speranza matematica e gioco equo
  3. Testa o croce
  4. Il gioco del Craps
  5. La legge dei grandi numeri

Teoria della computabilità

Analisi degli algoritmi

  1. Introduzione
  2. Definizioni
  3. Parametri di qualità di un algoritmo
  4. Il modello di costo per il calcolo del tempo di esecuzione
  5. Calcolo della complessità in funzione del passo base

Complessità asintotica e notazione O-grande

  1. Complessità asintotica
  2. Notazione O-grande
  3. Algebra degli O-grandi
  4. Equivalenza tra algoritmi
  5. Classi di complessità degli algoritmi
  6. Istruzione dominante

La complessità dei problemi

  1. Algoritmi e problemi
  2. Problemi computabili ma intrattabili
  3. Problemi polinomiali ed esponenziali
  4. La classe NP
  5. La classe P coincide con la classe NP?
  6. La classe NPC o NP-completa
  7. Risolvere i problemi intrattabili

MATERIALI DIDATTICI