Logo
Unionpedia
Comunicazione
Disponibile su Google Play
Nuovo! Scarica Unionpedia sul tuo dispositivo Android™!
Scaricare
l'accesso più veloce di browser!
 

Teorema dello speedup di Blum

Indice Teorema dello speedup di Blum

Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili.

10 relazioni: Algoritmo, Classe di complessità, Funzione calcolabile, Funzione ricorsiva, Linguaggio di programmazione, Macchina di Turing, Manuel Blum, Teorema dello speedup, Teoria della calcolabilità, Teoria della complessità computazionale.

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.

Nuovo!!: Teorema dello speedup di Blum e Algoritmo · Mostra di più »

Classe di complessità

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.

Nuovo!!: Teorema dello speedup di Blum e Classe di complessità · Mostra di più »

Funzione calcolabile

Le funzioni calcolabili sono il principale oggetto di studio della teoria della calcolabilità.

Nuovo!!: Teorema dello speedup di Blum e Funzione calcolabile · Mostra di più »

Funzione ricorsiva

Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo.

Nuovo!!: Teorema dello speedup di Blum e Funzione ricorsiva · Mostra di più »

Linguaggio di programmazione

Un linguaggio di programmazione, in informatica, è un linguaggio formale che specifica un insieme di istruzioni che possono essere usate per produrre dati in output.

Nuovo!!: Teorema dello speedup di Blum e Linguaggio di programmazione · Mostra di più »

Macchina di Turing

In informatica una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.

Nuovo!!: Teorema dello speedup di Blum e Macchina di Turing · Mostra di più »

Manuel Blum

Nel 1995 ha ricevuto il premio Turing per il suo contributo nel campo della teoria della complessità computazionale e della crittografia.

Nuovo!!: Teorema dello speedup di Blum e Manuel Blum · Mostra di più »

Teorema dello speedup

Nella teoria della complessità computazionale un teorema dello speedup (in inglese speed-up significa velocizzare) è un teorema che considera alcuni algoritmi che risolvono determinati problemi e dimostra l'esistenza di algoritmi più efficienti per risolvere gli stessi problemi.

Nuovo!!: Teorema dello speedup di Blum e Teorema dello speedup · Mostra di più »

Teoria della calcolabilità

La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico.

Nuovo!!: Teorema dello speedup di Blum e Teoria della calcolabilità · Mostra di più »

Teoria della complessità computazionale

In informatica, la 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.

Nuovo!!: Teorema dello speedup di Blum e Teoria della complessità computazionale · Mostra di più »

UscenteArrivo
Ehi! Siamo su Facebook ora! »