Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] come utilizzare frammenti del DNA per risolvere efficientemente un'istanza del complesso problema teorico della ricerca di un camminohamiltoniano in un grafo orientato, problema che è NP-completo e quindi ritenuto di difficile soluzione nei modelli ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1991-2000
1991-2000
1991
Il sistema operativo Linux. Uno studente finlandese, Linus Torvalds, sviluppa il sistema operativo Linux. Il sistema può essere distribuito, [...] DNA, e di fare in modo che ogni molecola di DNA 'generi' un cammino nel grafo; poiché le molecole a disposizione sono moltissime, è praticamente certo che se un camminohamiltoniano esiste, esso è generato da almeno una molecola. Resta quindi solo da ...
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 [...] Un g. che ammette un ciclo hamiltoniano è detto hamiltoniano (fig. 3L). Condizione necessaria e non orientato, sia d(i, j) il numero minimo di archi necessario per costruire un cammino da i a j. Si dice diametro del g. la quantità D=max d(i, ...
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, [...] fu la risoluzione del problema dell’esistenza di un cammino che attraversasse i ponti della città di Königsberg una sola problemi intrattabili (tra cui quello dell’esistenza di un ciclo hamiltoniano in un grafo) sono in NP. Nel caso – improbabile ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1951-1960
1951-1960
1951
Sui gruppi di omotopia e di omologia. In una serie di articoli (Homologie singulière des espaces fibrés) Jean-Pierre Serre fornisce [...] seguente risultato, che mostra come l'integrabilità di un sistema hamiltoniano nell'intorno di una posizione di equilibrio sia un caso eccezionale al disordine cristallino, quando esso produce un cammino libero medio inferiore alla lunghezza d'onda ...
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, [...] problema delle collegiali senza la richiesta che le ragazze debbano camminare in fila per tre in cinque righe). Kirkman dimostrò problemi intrattabili (tra cui quello dell'esistenza di un ciclo hamiltoniano in un grafo) sono in NP. Nel caso - ...
Leggi Tutto
potenziale
potenziale [agg. e s.m. Der. del lat. potentialis, da potentia "potenza"] [LSF] (a) In contrapp. ad attuale, di ciò che ha la capacità di esplicarsi in qualcosa, ma non attuandosi ancora. [...] il p. di forze di scambio (→ scambio). ◆ [PRB] P. di un cammino aleatorio: v. cammini aleatori: I 464 f. ◆ [ALG] P. di un campo vettoriale: nella è che il livello fondamentale dell'operatore di Hamilton per n particelle (o l'estremo inferiore dello ...
Leggi Tutto