pátek 21. května 2010

Python a slovník

Nedařilo se mi do slovníku (dictionary) vložit víc než několik desítek milionů položek. Přitom paměti bylo víc než dost. Proto jsem napsal následující skript na zjištěná maximálního počtu položek, které lze do slovníku uložit.

i = 0
d = {}
try:
while True:
d[i] = i
i = i + 1
except MemoryError:
print i

Výsledný počet je 44739242. V hexadecimální soustavě je to 2AAAAAA, což vypadá podezřele. Upozornění: Skript může způsobit pád některých programů.

Řešení problému:

class Dict2:
def __init__(self):
self.dicts = [{}]
def value(self, k):
for dict in self.dicts:
if k in dict:
return dict[k]
def isIn(self):
for dict in self.dicts:
if k in dict:
return True
return False
def insert(self, k, d):
for dict in self.dicts:
if k in dict:
dict[k] = d
return
try:
self.dicts[0][k] = d
except MemoryError:
self.dicts.insert(0, {})
self.dicts[0][k] = d

i = 0
d = Dict2()
try:
while True:
d.insert(i, i)
i = i + 1
except MemoryError:
print i

středa 19. května 2010

Funkcionální úplnost

V binární logice lze z operátoru NAND nebo NOR sestrojit libovolný jiný operátor, což lze snadno dokázat. Důkaz je uveden v každé knize typu "logik für frauzimmer". Že to jsou jediné operátory, které samotné tvoří funkcionálně úplnou množinu operátorů, lze také dokázat poměrně snadno.

Definice. Funkce f je n-Shefferovská (nebo Shefferova), jestliže lze z ní konečným způsobem složit libovolnou funkci g:\ A_n \times A_n \mapsto A_n, kde A_n = \{0, 1, \dots, n-1\}.

Věta. Jestliže existuje existuje množina \emptyset \not= B \subset A_n taková, že pro funkci f platí \left(\forall x, y \in B\right)\ f(x, y) \in B, pak funkce f není n-Shefferovská.
Důkaz. Pokud předpoklad tvrzení platí, pak nelze žádným způsobem z funkce f složit funkci, která by pro nějaké x, y \in B nabývala hodnoty z neprázdné množiny A_n \setminus B. Proto funkce f nemůže být n-Shefferovská.

Důsledek. Jestliže pro některé x \in A_n platí f(x, x) = x, pak funkce f není n-Shefferovská.

Binárních operátorů na množině A_2 je jen 16. Ovšem ty, pro které platí f(x, x) \not= x, jsou jen čtyři. Dva z nich jsou však jenom unární operátory, které nemohou být 2-Shefferovské. Proto existují jen dvě 2-Shefferovské funkce.

Zajímavá je otázka: Kolik je obecně n-Shefferovskáých funkcí? Žádný vzorec se mi nepodařilo ani vymyslet, ani nalézt. Zdá se, že existuje pro každé konečné n alespoň jedna. V oxfordském matematickém slovníku jsem nalezl tento předpis pro n-Shefferovskou funkci:

f(x, y) = \left(\max\{x, y\} + 1\right)\ \mathrm{mod}\ n.

Říkají jí "Wenn funkce", což bude asi nějaké nedorozumění. Důkaz, že se skutečně jedná o n-Shefferovskou funkci jsem zatím nenašel. Pro žádné nekonečné n žádná n-Shefferovská funkce neexistuje, protože funkcí g:\ N \times N \mapsto N je nespočetně mnoho, kdežto konečným způsobem lze složit jen spočetně mnoho funkcí.

středa 12. května 2010

Matematika je především drzost

Nowhere, then, on our real line—not at zero, nor to its left nor to its right, not sheltered among the rationals, nor masquerading as an irrational—can there be any number which is the square root of negative one. It is at this point that a deep quality of the mathematical art emerges—let’s call it the Alcibiades Humor. For Alcibiades was the infant terrible of ancient Athenian life at the time of Socrates: handsome and willful, outrageous and heroic, arrogant and playful, disrupter of dis course and envoy of passion to the feast of reason. Plutarch tells us that even as a boy, dicing in the street, he dared an angry carter to run him over—and of course the carter turned back. The Alcibiades Humor in mathematics is just this hubris, this refusal to stop playing when all seems lost.
Robert + Ellen Kaplan – The art of the infinity

Číslo, které je druhou odmocninou z mínus jedné, tedy nemůže být nikde na naší číselné ose – ne v nule, ne nalevo ani napravo od ní, nemůže se ukrývat mezi racionálními čísly, ani se maskovat jako číslo iracionální. Právě v tuto chvíli se vynoří hluboká kvalita matematického umění – nazvěme ji Alkibiadovým humorem. Protože Alkibiadés byl enfant terrible života ve starověkých Athénách v době Sókratově: krásný a tvrdohlavý, skandální a hrdinský, arogantní a hravý narušitel rozmluv a vyslanec vášně na hostině rozumu. Plútarchos nám říká, že když hrál, ještě jako chlapec, na ulici v kostky, vyzval rozzlobeného vozku, aby ho přejel – a vozka samozřejmě svůj vůz obrátil. Alkibiadův humor v matematice je právě tahle arogance, tohle odmítnutí přestat hrát, když se zdá být vše ztraceno.
Robert Kaplan, Ellen Kaplanová – Umění nekonečna