La Matematica Nella Seconda Stagione
Teoria della complessità computazionaleIn informatica, la teoria della complessità algoritmica o teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. I problemi vengono così classificati in differenti classi di complessità, a seconda di quanto il migliore algoritmo di risoluzione noto sia efficiente.
Algoritmi di potatura
La potatura alfa-beta è un algoritmo di ricerca che riduce drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algorimo minimax. Viene comunemente usata nei programmi di gioco automatico per computer, per giochi a turni a due o più giocatori (Tris, Go, Scacchi ecc.), e consiste nel terminare la valutazione di una possibile mossa non appena viene dimostrato che è comunque peggiore di una già valutata in precedenza: è una ottimizzazione sicura, che non modifica il risultato finale dell'algoritmo a cui viene applicata.
Effetto Doppler
L'effetto Doppler è un cambiamento apparente della frequenza o della lunghezza d'onda di un'onda percepita da un osservatore che si trova in movimento rispetto alla sorgente delle onde. Per quelle onde che si trasmettono in un mezzo, come le onde sonore, la velocità dell'osservatore e dell'emettitore vanno considerate in relazione a quella del mezzo in cui sono trasmesse le onde. L'effetto Doppler totale può quindi derivare dal moto di entrambi, ed ognuno di essi è analizzato separatamente.
Teoria del caos
La teoria del caos è un settore della teoria matematica dei sistemi dinamici che si occupa dei cosiddetti sistemi caotici.
Un sistema dinamico si dice caotico se presenta le seguenti caratteristiche:
- Sensibilità alle condizioni iniziali, ovvero a variazioni infinitesime delle condizioni al contorno (o, genericamente, degli ingressi) corrispondono variazioni finite in uscita. Come esempio banale: il fumo di più fiammiferi accesi in condizioni macroscopicamente molto simili (pressione, temperatura, correnti d'aria) segue traiettorie di volta in volta molto differenti.
-Imprevedibilità, cioè non si può prevedere l'andamento del sistema in anticipo.
-Le orbite nello spazio delle fasi restano confinate, cioè il sistema non evolve verso l'infinito per nessuna variabile. Si parla in questo caso di Attrattori.
Problema del commesso viaggiatore
Il problema del commesso viaggiatore, o TSP (dall'inglese Traveling Salesman Problem) è un problema di teoria dei grafi, uno dei casi di studio tipici dell'informatica teorica e della teoria della complessità.
Il nome nasce dalla sua più tipica rappresentazione: data una rete di città, connesse tramite delle strade, trovare il percorso di minore distanza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta. Espresso nei termini della teoria dei grafi è così formulato: dato un grafo completo pesato, trovare il ciclo hamiltoniano con peso minore. La rete di città può essere rappresentata come un grafo in cui le città sono i nodi, le strade gli archi e le distanze i pesi sugli archi. Può essere dimostrato che specificare o meno il ritorno alla città di partenza non cambia la complessità computazionale del problema. Il problema è di considerevole importanza pratica, al di là delle ovvie applicazioni nella logistica e nei trasporti. Un esempio classico è la costruzione di circuiti stampati, nella pianificazione del percorso del trapano per creare i fori nella piastra. Nelle applicazioni di foratura o di rifinitura automatica eseguite da robot, le "città" sono pezzi da rifinire o fori (anche di varie dimensioni) da praticare, e il "costo di viaggio" include i tempi morti (ad esempio il tempo che il robot impiega, se necessario per cambiare la punta con cui lavora).