Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] cui la macchina non si arresta mai. In linea teorica anche queste stringhe non sono accettate, tuttavia la teoriadellacomplessità esclude questo caso limitando lo studio alle macchine di Turing che si arrestano sempre, cui è propriamente assegnato ...
Leggi Tutto
Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, [...] stesso, se una soluzione proposta si può controllare in un numero polinomiale di passi). Il grande problema irrisolto dellateoriadellacomplessità chiede di sapere se P è uguale a NP. Si tratta di un problema importante per la combinatoria perché ...
Leggi Tutto
Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodi o vertici, e da un insieme di relazioni tra coppie di oggetti dette archi o spigoli. Per indicare un [...] studiò le reti di comunicazione; nel 1970-72 S.A. Cook, J. Edmonds e R.M. Karp costruirono le basi dellateoriadellacomplessità; nel 1979 L. Lovász dimostrò la congettura dei g. perfetti di Berge.
Lo sviluppo e la diffusione di queste metodologie ...
Leggi Tutto
La grande scienza. Combinatoria
Peter J. Cameron
Combinatoria
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri essa non rappresenta una branca separata, [...] lo stesso, se una soluzione proposta si può controllare in un numero polinomiale di passi). Il grande problema irrisolto dellateoriadellacomplessità chiede di sapere se P è uguale a NP. Il 24 maggio 2000 il Clay Mathematics Institute ha stilato un ...
Leggi Tutto
L'Eta dei Lumi: matematica. I metodi numerici
Peter Schreiber
I metodi numerici
Il XVII sec. è stato in generale un 'secolo geometrico'. A parte alcune considerazioni di carattere puramente numerico, [...] piuttosto rozzo; esso viene oggi generalizzato a problemi astratti e studiato a fondo dal punto di vista dellateoriadellacomplessità. Tutti i procedimenti conosciuti si basavano essenzialmente sulla rappresentazione geometrica del comportamento ...
Leggi Tutto
In matematica applicata, e in particolare nella teoriadelle decisioni, problemi di o., le questioni attinenti alla ricerca dei criteri di scelta tra diverse opzioni o di determinazione del valore di particolari [...] di questi risultati sono la modellazione degli algoritmi di simulate annealing come catene di Markov e la teoriadellacomplessità computazionale sviluppata per gli algoritmi di ricerca locale, che hanno permesso di studiare in modo più approfondito ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] 'inclusione di P in QP sia o meno stretta è uno dei tanti problemi aperti che costellano la teoriadellacomplessità computazionale.
Calcolo molecolare
Il paradigma di calcolo chiamato calcolo molecolare (o anche DNA computing) è stato introdotto in ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] EQ) sulla quale esiste un gran numero di studi in vista dei suoi collegamenti con la teoriadellacomplessità. Lo stesso può dirsi, in generale, dellateoria elementare dei grafi visti come strutture 〈D,R〉, dove R è una relazione binaria. I grafi ...
Leggi Tutto
Fondamenti della matematica e teoria algoritmica dell'informazione
Gregory J. Chaitin
Ciò che possiamo dimostrare intorno ai fondamenti della matematica usando i suoi stessi metodi costituisce la metamatematica, [...] qui citati per mostrare che Ω non è un'entità isolata, è parte di un'elegante teoriadell'informazione algoritmica e della casualità, una teoriadellacomplessità in termini di lunghezza di programma per U.
La matematica è quasi-empirica?
A nostro ...
Leggi Tutto
Il termine complessità è oggi frequentemente usato, in campo scientifico, in contesti diversi. In quello dell'informatica, dell'analisi numerica e dell'ottimizzazione, corrisponde alla caratteristica quantitativa [...] matematici coinvolti, alcuni dei quali, come la teoriadelle catastrofi o la geometria frattale, hanno ricevuto una notevole attenzione anche da parte dei mezzi di comunicazione di massa (v. caos e complessità, App. V, i, p. 490; catastrofi, teorema ...
Leggi Tutto
complessita
complessità s. f. [der. di complesso1]. – 1. L’esser complesso (nelle varie accezioni dei sign. 1 e 2 di quest’agg.): c. di una questione, di un ragionamento, di una costruzione teorica; c. di un atto giuridico; esaminare una situazione...
numero
nùmero s. m. [dal lat. numĕrus; cfr. novero]. – 1. Ciascuno degli enti astratti che rappresentano insiemi di unità, ordinati in una successione infinita (serie naturale dei n.) nella quale ogni elemento conta un’unità in più rispetto...