Appunti Ricevimento Algoritmica

Macchine di Turing e tesi di Church definiscono i limiti della calcolabilità, equivalendo tra loro in potere espressivo. Le Macchine di Turing (MDT) sono modelli astratti che permettono la definizione rigorosa degli algoritmi. Una MDT si compone di stati, funzione di transizione e stati finali. Le tabelle ad accesso diretto sono limitate dalla dimensione del loro insieme chiave, rendendole inadatte per grandi quantità di dati; le tabelle hash, invece, utilizzano funzioni hashing per ridurre la dimensione delle chiavi, gestendo collisioni. Le funzioni hashing generano un numero intero che determina l'indice della tabella. La scansione lineare e quadra