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, [...] è Σ*, ovvero A calcola una funzione f da Σ* su Σ*. Indicando con ℕ l'insiemedeinumerinaturali e notando che Σ* è ovviamente numerabile, sotto un'arbitraria numerazione delle sue stringhe si può affermare che f è una funzione da ℕ su ℕ, o da ...
Leggi Tutto
induzione
induzióne [Der. del lat. inductio -onis, dal part. pass. inductus di inducere "indurre" (→ induttivo)] [FAF] Procedimento logico, opposto a quello della deduzione, per cui dall'osservazione [...] che elementi diversi da quelli detti appartengano a I (o godano di P). Per es., è definito per i. l'insiemedeinumerinaturali, in cui elemento base è lo zero e operazione definitoria è quella di passaggio al successore. ◆ [FAF] Dimostrazione per i ...
Leggi Tutto
infinito
infinito [agg. e s.m. Der. del lat. infinitus, comp. di in- neg. e del part. pass. finitus di finire "limitare", da finis "confine"] [LSF] Oltre che nei signif. matematici (per i quali v. oltre), [...] limite, cioè come numerosità o potenza di un insieme: rientrano in questo concetto l'i. numerabile (cioè la potenza dell'insiemedeinumerinaturali), l'i. continuo (la potenza del-l'insiemedeinumeri reali, dei punti di una retta, ecc.). ◆ [ANM] I ...
Leggi Tutto
potenza
potènza [Der. del lat. potentia, dall'agg. potens -entis "potente", part. pres. di posse "potere"] [LSF] (a) Generic., capacità di produrre grandi effetti. (b) Specific., l'energia che viene [...] reali, indicata con i simb. א₁ ("aleph uno") e 2א0 ("due alla aleph zero"). ◆ [MCS] P. del numerabile: la p. dell'insiemedeinumerinaturali, indicata tradizionalmente con il simb. א₀ ("aleph zero"). ◆ [ELT] [INF] P. di calcolo: per un calcolatore ...
Leggi Tutto
computabile
computàbile [agg. Der. dell'ingl. computable, che è dal lat. computabilis "che si può calcolare", "di cui si può o si deve tenere conto", già reso con l'it. calcolabile] [ALG] [FAF] [INF] [...] Di una variabile (per es., l'insiemedeinumerinaturali) che si può calcolare effettivamente, cioè per la quale esiste un procedimento che permette di determinarne i valori o, in altri termini, le grandezze che possono essere calcolate con un ...
Leggi Tutto
numerabilenumeràbile [agg. e s.m. Der. del lat. numerabilis, da numerus "numero"] [LSF] Che può essere numerato, cioè contraddistinto (in base a un criterio certo) con un numero, oppure che può essere [...] che possa essere messo in corrispondenza biunivoca con l'insiemedeinumerinaturali, come capita per i numeri razionali, algebrici e, in altro campo, per l'insiemedei punti che abbiano coordinate intere e appartenenti a una retta, a un piano ...
Leggi Tutto
Insieme delle scienze che studiano in modo ipotetico-deduttivo entità astratte come i numeri e le misure: la m. pura studia i problemi matematici indipendentemente dalla loro utilizzazione pratica; alla [...] la m. è la scienza razionale deinumeri (aritmetica, intesa come scienza della rappresentato da alcune grandi opere d’insieme, apparse a cavallo tra Settecento fossero immagine, sia pure idealizzata, di enti naturali, tanto che la m. fu a lungo ...
Leggi Tutto
Diritto
Diritto privato
Fenomeno squisitamente giuridico per il quale un soggetto subentra ad altro soggetto in un complesso di rapporti giuridici patrimoniali ovvero in un rapporto giuridico patrimoniale [...] Secondo una definizione più rigorosa, una s. è una funzione che associa a ogni numeronaturale n un elemento an di un certo insieme (per es., dell’insiemedeinumeri reali). La comune natura degli elementi può variare; più frequentemente si trovano s ...
Leggi Tutto
L'Universo matematico
John D. Barrow
(Astronomy Centre, University of Sussex, Brighton, Gran Bretagna)
Parte di questo saggio è stata pubblicata sotto il titolo Perché il mondo è matematico? Roma-Bari, [...] dai numerinaturali? Che cosa costituisce un passo costruttivo? Perché alcune costruzioni sono più utili e meglio applicabili al mondo reale rispetto ad altre? Perché non abbiamo intuizioni degli insiemi infiniti? Come si spiega l'utilità dei ...
Leggi Tutto
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...
numerabile
numeràbile agg. e s. m. [dal lat. numerabĭlis]. – Che può essere numerato, cioè distinto con numeri, oppure calcolato esattamente: ci darà la quantità esatta delle ore e minuti ..., se la frequenza fusse da noi n. (Galilei). In...