Il Contributo italiano alla storia del Pensiero: Scienze (2013)
Algebra, geometria, indivisibili
Enrico Giusti
Primi progressi nell’algebra
Dopo un periodo di gestazione lungo tre secoli, l’algebra è la prima disciplina in cui nel Cinquecento si registrano sostanziali [...] non è possibile scrivere l’equazione generale, e si dovrà quindi esprimere la soluzione non con una formula ma con un algoritmo. Dice Bombelli:
Havendosi da agguagliare potenze a tanti e numero, partasi il tutto per la quantità delle potenze, poi si ...
Leggi Tutto
Finito
Antonio Machì
(XV, p. 399)
Matematica del finito
Diversi filoni della ricerca matematica che mostrano particolare vitalità si possono ricondurre all'interesse per i problemi del finito. L'analisi [...] richiedono un numero di operazioni dell'ordine di n³1pn² log n, dove n è il grado del polinomio; se p è grande, gli algoritmi più efficaci hanno una complessità (v. informatica, App. V) dell'ordine di n²(log p)³ log r, dove r è il numero dei fattori ...
Leggi Tutto
La civilta islamica: antiche e nuove tradizioni in matematica. L'algebra e il suo ruolo unificante
Roshdi Rashed
L'algebra e il suo ruolo unificante
La seconda metà del VII sec. vede il costituirsi [...] ' per la risoluzione approssimata delle equazioni. Dopo aver determinato la seconda cifra, che è la prima di y, si ripete l'algoritmo sull'equazione in y per trovare una terza cifra, e si continua così finché non si ottiene la radice, che nei casi ...
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, [...] risolvibili in tempo polinomiale (ma la dimostrazione non è costruttiva, per cui nella maggior parte dei casi non viene fornito alcun algoritmo).
Tuttavia questo non è l'unico modo in cui un grafo può avere una struttura profonda che non si rivela a ...
Leggi Tutto
continuo 1
contìnuo1 [agg. Der. del lat. continuus, da continere "tenere unito", comp. di cum "insieme" e tenere, e quindi "non interrotto"] [ALG] Applicazione c.: applicazione definita su uno spazio [...] scritto in uno e un solo modo come:
indicando con [x] la parte intera di x, la successione ai si costruisce con il seguente algoritmo:
Il numero a è razionale se e solo se per un certo j si ha aj=∞, ossia la frazione c. si tronca. La frazione ...
Leggi Tutto
Selezione di 7 problemi matematici proposti nel 2000 dal Clay Mathematics Institute (CMI) di Cambridge, Massachusetts, che ha stanziato per la risoluzione di ognuno di essi un premio di 1 milione di dollari. [...] relazione tra le classi di complessità computazionale P, cui appartengono i problemi che possono essere risolti con un algoritmo deterministico in un tempo polinomiale, e NP, cui appartengono i problemi che possono essere verificati (ma non risolti ...
Leggi Tutto
Combinatoria
Peter J. Cameron
Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri non rappresenta una branca separata dalle altre ma le pervade tutte, poiché [...] di un ciclo hamiltoniano in un grafo) sono in NP. Nel caso ‒ improbabile ‒ di una soluzione positiva, vi sarebbero algoritmi veloci per tutti questi problemi.
Tendenze e problemi
Per avere una misura delle connessioni tra la combinatoria e altre ...
Leggi Tutto
anello di polinomi
Luca Tomassini
Sia F un campo, ovvero un corpo commutativo. Si definisce anello di polinomi F[x] in una indeterminata x l’insieme dei simboli a0+a1x+...+anxn, dove n è un intero non [...] della teoria degli anelli commutativi. In primo luogo esso è un anello euclideo, con grado definito da δ, come stabilito dall’esistenza di un algoritmo di divisione (o euclideo): dati i polinomi p(x) e q(x), con q(x)≠0, esistono due polinomi t(x) e r ...
Leggi Tutto
L'a. l. costituisce uno strumento matematico di importanza fondamentale in ogni disciplina scientifica. Essa costituisce sia un efficace linguaggio comune con cui formulare problemi di natura diversa, [...] che la complessità della risoluzione di un sistema n × n è asintoticamente la stessa della moltiplicazione di matrici n × n e diede un algoritmo con costo dell'ordine di nω con ω=log27⟨2,81. L'estremo inferiore τ dei valori di ω per cui è possibile ...
Leggi Tutto
isomorfismo
Luca Tomassini
Corrispondenza o relazione tra enti matematici o sistemi di enti matematici che esprime l’identità delle loro strutture in un senso opportuno. Un isomorfismo in una categoria [...] le sue classi di equivalenza per isomorfismo. A questo riguardo, ricordiamo il cosiddetto problema dell’isomorfismo: determinare un algoritmo che permetta di stabilire se due sistemi algebrici definiti ricorsivamente siano o meno isomorfi.
→ Algebra ...
Leggi Tutto
algoritmo
(ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. – 1....