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

Teoria della complessità computazionale

Indice 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.

30 relazioni: Algoritmo, Algoritmo di ordinamento, Classe di complessità, Classi di complessità P e NP, Computabilità, Computazione, Computer, Crittografia, Funzione monotona, Glossario delle classi di complessità, Grafo, Informatica, Insieme, Isomorfismo, Lingua inglese, Linguaggio formale, Macchina di Turing, Macchina RAM, Matematica, O-grande, Problema del commesso viaggiatore, Problemi per il millennio, Soddisfacibilità booleana, Teorema dello speedup di Blum, Teoria della calcolabilità, Teoria della complessità algoritmica, Teoria della computazione, Tesi di Church-Turing, Test di primalità, 1971.

Algoritmo

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

Nuovo!!: Teoria della complessità computazionale e Algoritmo · Mostra di più »

Algoritmo di ordinamento

Un algoritmo di ordinamento (sorting algorithm) è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue.

Nuovo!!: Teoria della complessità computazionale e Algoritmo di ordinamento · Mostra di più »

Classe di complessità

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

Nuovo!!: Teoria della complessità computazionale e Classe di complessità · Mostra di più »

Classi di complessità P e NP

Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.

Nuovo!!: Teoria della complessità computazionale e Classi di complessità P e NP · Mostra di più »

Computabilità

La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi.

Nuovo!!: Teoria della complessità computazionale e Computabilità · Mostra di più »

Computazione

Il termine computazione deriva dal latino computare che significa sia "contare" sia "tagliare" e ha diversi significati nella lingua italiana.

Nuovo!!: Teoria della complessità computazionale e Computazione · Mostra di più »

Computer

Un computer (pronuncia italiana), in italiano anche elaboratore (vedi «aspetti linguistici»), è una macchina automatizzata in grado di eseguire complessi calcoli matematici ed eventualmente altri tipi di elaborazioni dati.

Nuovo!!: Teoria della complessità computazionale e Computer · Mostra di più »

Crittografia

La crittografia (dall'unione di due parole greche: κρυπτóς che significa "nascosto", e γραφία che significa "scrittura") è la branca della crittologia che tratta delle "scritture nascoste", ovvero dei metodi per rendere un messaggio "offuscato" in modo da non essere comprensibile/intelligibile a persone non autorizzate a leggerlo.

Nuovo!!: Teoria della complessità computazionale e Crittografia · Mostra di più »

Funzione monotona

In matematica, una funzione monotòna è una funzione che mantiene l'ordinamento tra insiemi ordinati.

Nuovo!!: Teoria della complessità computazionale e Funzione monotona · Mostra di più »

Glossario delle classi di complessità

Questa pagina presenta un glossario delle classi di complessità, insiemi concernenti la teoria della complessità computazionale.

Nuovo!!: Teoria della complessità computazionale e Glossario delle classi di complessità · Mostra di più »

Grafo

Grafo (non orientato) con 6 nodi e 5 archi I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi.

Nuovo!!: Teoria della complessità computazionale e Grafo · Mostra di più »

Informatica

L'informatica è la scienza applicata che si occupa del trattamento dell'informazione mediante procedure automatizzate.

Nuovo!!: Teoria della complessità computazionale e Informatica · Mostra di più »

Insieme

In matematica, un raggruppamento di oggetti rappresenta un insieme se esiste un criterio oggettivo che permette di decidere univocamente se un qualunque oggetto fa parte o no del raggruppamento.

Nuovo!!: Teoria della complessità computazionale e Insieme · Mostra di più »

Isomorfismo

In matematica, in particolare in algebra astratta, un isomorfismo (dal greco ἴσος, isos, che significa uguale, e μορφή, morphé, che significa forma) è un'applicazione biunivoca fra oggetti matematici tale che l'applicazione e la sua inversa siano omomorfismi.

Nuovo!!: Teoria della complessità computazionale e Isomorfismo · Mostra di più »

Lingua inglese

L'inglese (nome nativo English) è una lingua indoeuropea appartenente al ramo occidentale delle lingue germaniche, assieme all'olandese, all'alto e basso tedesco, al fiammingo e al frisone.

Nuovo!!: Teoria della complessità computazionale e Lingua inglese · Mostra di più »

Linguaggio formale

Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.

Nuovo!!: Teoria della complessità computazionale e Linguaggio formale · 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!!: Teoria della complessità computazionale e Macchina di Turing · Mostra di più »

Macchina RAM

Il modello della macchina RAM è uno strumento classico per l'analisi delle procedure sequenziali.

Nuovo!!: Teoria della complessità computazionale e Macchina RAM · Mostra di più »

Matematica

La matematica (dal greco μάθημα (máthema), traducibile con i termini "scienza", "conoscenza" o "apprendimento"; μαθηματικός (mathematikós) significa "incline ad apprendere") è la disciplina che studia le quantità (i numeri), lo spazio,.

Nuovo!!: Teoria della complessità computazionale e Matematica · Mostra di più »

O-grande

La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni.

Nuovo!!: Teoria della complessità computazionale e O-grande · Mostra di più »

Problema del commesso viaggiatore

Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling.

Nuovo!!: Teoria della complessità computazionale e Problema del commesso viaggiatore · Mostra di più »

Problemi per il millennio

I problemi per il millennio (Millennium problems) sono stati posti all'attenzione dei matematici dall'Istituto matematico Clay.

Nuovo!!: Teoria della complessità computazionale e Problemi per il millennio · Mostra di più »

Soddisfacibilità booleana

La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.

Nuovo!!: Teoria della complessità computazionale e Soddisfacibilità booleana · Mostra di più »

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.

Nuovo!!: Teoria della complessità computazionale e Teorema dello speedup di Blum · 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!!: Teoria della complessità computazionale e Teoria della calcolabilità · Mostra di più »

Teoria della complessità algoritmica

La teoria della complessità algoritmica o Teoria algoritmica della complessità si occupa dello studio della complessità descrittiva degli algoritmi e non delle risorse computazionali (memoria occupata e tempo di calcolo) necessarie ad eseguirli.

Nuovo!!: Teoria della complessità computazionale e Teoria della complessità algoritmica · Mostra di più »

Teoria della computazione

La teoria della computazione è quella branca della matematica che si preoccupa di definire quali proprietà possiede uno specifico linguaggio formale.

Nuovo!!: Teoria della complessità computazionale e Teoria della computazione · Mostra di più »

Tesi di Church-Turing

Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: "se un problema è umanamente calcolabile, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo (cioè di calcolarlo)." Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.

Nuovo!!: Teoria della complessità computazionale e Tesi di Church-Turing · Mostra di più »

Test di primalità

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo.

Nuovo!!: Teoria della complessità computazionale e Test di primalità · Mostra di più »

1971

Nessuna descrizione.

Nuovo!!: Teoria della complessità computazionale e 1971 · Mostra di più »

Riorienta qui:

Complessità computazionale, Complessità degli algoritmi, Onere computazionale.

UscenteArrivo
Ehi! Siamo su Facebook ora! »