Losowe kombinacje - optymalny hashswap.pl

Tym razem podam algorytm optymalny, klasyczny (nie mój! - mój jest tylko kod). Jest w zasadzie maksymalnie szybki, i minimalnie obciąża pamięć (modulo trywialności). Oto kod:

#!/usr/bin/perl
#
# hashswap.pl

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);    $m=$n+1;
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

for (1..$k)
{   $v = $_ + int(rand($m-$_));
    if(!($w=$h{$v}))  { $w = $v }
    if(!($s=$h{$_}))  { $s = $_ }
    $h{$_}=$w;    $h{$v}=$s        ### swap
}
no integer;
$endT = times();
use integer;

for (1..$k)  { print "  $h{$_}" }

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";

# Koniec programu

---

Algorytm zawiera się głównie w pierwszej pętli, której tekst składa się w sumie z 6 linijek. Gdy chce ktoś mierzyć czas dla wielkich parametrów, to linijki pomiędzy instrukcją:

        $endT = times();

oraz instrukcją print, może usunąć (lub zakomentować).

---

A teraz podam ten sam program, tyle że swap będzie dokonany w stylu wczesnego minikomputera PDP:

#!/usr/bin/perl
#
# pdpswap.pl

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);    $m=$n+1;
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

for (1..$k)
{   $v = $_ + int(rand($m-$_));
    if(!$h{$_})  { $h{$_} = $_ }
    if($v != $_)
    {   if(!$h{$v})  { $h{$v} = $v }
        $h{$v} ^= $h{$_} ^= $h{$v} ^= $h{$_}    ### swap
}   }

no integer;
$endT = times();
use integer;

for (1..$k)  { print "  $h{$_}" }

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";

# Koniec programu

Losowe kombinacje (w perlu)

@Przemysławie: moja kobyłka u płotu. Sam zastawiłem na siebie tę pułapkę napisania nieoptymalnego algorytmu. Stosuję w nim linked list dla reprezentacji wybranej losowo kombinacji. Podaję ją uporządkowaną. Wierzę, że w perlu ten algorytm nie zżera pamięci; gorzej byłoby w innych językach.

Algorytm (a), o którym wspomniał @Dziki Wezyr, jest lepszy, chyba optymalny. Oba losują kolejne elementy kombinacji bez zwracania.

Podaję poniżej program w perlu. Nie ma żadnych dodatków, jest w tym sensie minimalny. Można go wpakować w pętlę, dodać mu liczniki i pomiary czasu, itd.

---

#!/usr/bin/perl
#
# A non-optimal program.

use integer;

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$nxt[0] = $n+1;

for (0..$k-1)
{   $a = int(rand($n-$_));
    $b=0;
    while ($a >= $b)
    {   $b = $nxt[$last = $b];
        ++$a;
    }
    $nxt[$last] = $a;
    $nxt[$a] = $b
}

while(($a=$nxt[$c]) != $n+1)
{   print "  $a";
    $c=$a
}

print "\n\n"

---

---

Dla wygody sportowców (:-) uzupełnię kod o pomiar czasu liczenia kombinacji (bez brania pod uwagę czasu inputu użytkownika oraz drukowania wyniku). Oto program z zegarkiem:

---

#!/usr/bin/perl
#
# A non-optimal program.


print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

$nxt[0] = $n+1;

for (0..$k-1)
{   $a = int(rand($n-$_));
    $b=0;
    while ($a >= $b)
    {   $b = $nxt[$last = $b];
        ++$a;
    }
    $nxt[$last] = $a;
    $nxt[$a] = $b
}

no integer;
$endT = times();
use integer;

while(($a=$nxt[$c]) != $n+1)
{   print "  $a";
    $c=$a
}

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";

Test Greasemonkey TeX

Czy jeszcze cos' mam dodac'?

    [;2^4 - 4^2 \ne e^{\pi} - \pi^e;]

No i jak?

W preview nic dobrego sie/ nie pokazalo, wiec jest na razie niedobrze. Musze/ poczytac' dokumentacje/ Greasemonkey (o losie! :-).

Diakrytyki w TeX via klawiatura

Sprawdzę czy Greasemonkey TeX daje sobie radę z Polish Programmer Keyboard:

        [; Ą\ Ć\ Ę\ Ł\ Ń\ Ó\ Ś\ Ź\ Ż ;]


        [; ą\ ć\ ę\ ł\ ń\ ó\ ś\ ź\ ż ;]

No, jak tam? - hm..., średnio, czyli do kitu, lepiej tego unikać. Nie pokazało się Ą/ą, oraz zamiast Ę/ę widzę zwykłe E/e. Małe litery pokazały się u mnie jako duże.

Czy zostało coś jeszcze do powiedzenia? Oczywiście [;\TeX;] oraz [;LaTeX;] mają własne metody prezentowania diakrytyków (wygodniej jednak byłoby wstukiwać je jak w zwykłych tekstach).

Wielkie Liczby, Cz 2

Spis rzeczy

• Uwagi historyczne: styl logiczny i styl klasyczny


• Podejście koncepcyjne: arytmetyka, funkcje, kompozycja, operatory


• Zastosowania
  
  
  
  1. Potęga kompozycyjna
  
  
  2. Skromna przekątna
  
  
  
  

Uwagi historyczne: styl logiczny i styl klasyczny

Temat Wielkich Liczb wystąpił przy okazji teorii funkcji rekursywnych, stworzonej przez uczniów Hilberta (i samego mistrza też?): Wilhelma Ackermanna i Gabriella Sudana, oraz przez jedną z nawybitniejszych matematyczek wszech czasów, Rozsę Peter (nie była uczniem Hilberta). Właśnie ona zaproponowała, by temat funkcji rekursywnych traktować jako samodzielną teorię. Otóż Hilbert postawił problem istnienia rekursywnej funkcji, która nie byłaby pierwotnie rekursywną. Najpierw Sudan, a wkrótce i niezależnie Ackerman (nieco bardziej elegancko), podali takie funkcje. Skonstruowali funkcje rekursywne, które rosną szybciej niż jakakolwiek funkcja pierwotnie rekursywna. Używali 3 argumentów. Rozsa Peter zastąpiła 3 argumenty w funkcji Ackermanna przez 2. Ostatecznie funkcję tę uprościł Raphael Robinson, przez podanie elegantszych warunków początkowych. Tradycyjnie dalej nazywa się ją funkcją Ackermanna (czasem dodają nazwisko Peter). Uderza ekonomia ostatecznej definicji. Reprezentuje ona ciekawy, lecz nieco dziwny obiekt, który mi się podoba, ale odczuwam potrzebę także naturalniejszego podejścia, wykorzystującego konstrukcję przekątną, która musiała istnieć w Analizie Matematycznej chyba na długo przed Cantorem. Cantor stosował metodę przekątnej w teorii mnogości.

Metoda wspomnianych logików polegała na budowaniu wyrażenia, które w czasie rekurencji ogromniało, zawierając coraz więcej podwyrażeń, produkujących w czasie iteracji dalsze liczne podpodwyrażenia. Konstrukcja w końcu się zatrzymuje, bo każde wyrażenie ma parametry, które traktowane jako jeden parametr, stale maleje w leksykograicznym porządku. Porządek jest taki, że w dół można iść tylko skończenie wiele razy.

Wśród logików, zajmujących się rekursywnością i szybkością rośnięcia funkcji, liczy się między innymi Andrzej Gregorczyk.

Następcy wspomnianych wyżej matematyków dodali chyba niewiele, i nie wiem co było ich matematycznym celem (czy taki mieli). Wspomnę Knutha i Conway'a. Niektórzy skręcili w kierunku klasycznym. Widać też, że klasyczne podejście i logiczne są zbieżne.

Poniżej opiszę podejście klasyczne, ale koncepcyjnie jaśniej, niż jest to w spotkanej przeze mnie literaturze. Podkreślę i opiszę explicite ważne elementy konstrukcji, te które się koncepcyjnie liczą najbardziej.

UWAGA  Nietrudno, po mojej tu nitce dojść do kłębka informacji na dany temat, zawartego w wikipedii.

Podejście koncepcyjne: arytmetyka, funkcje, kompozycja, operatory

Budowanie wielkich liczb, a raczej szybko rosnących funkcji, związane jest na początku z działaniami arytmetycznymi: następnik  [;\nu(n) := n+1;],  dodawanie, mnożenie, wreszcie potęgowanie, na przykład:  [;\delta(n) := n^n;].  - to etap 1. Etap 2 polega na wprowadzeniu funkcji, zamiast izolowanych liczb. Jakoś należy przy definiowaniu funkcji operacje arytmetyczne iterować na wielką skalę; ale tak po prostu, to nie ma jak. Pomaga, na trzecim etapie, pojęcie kompozycji funkcji. Właśnie, jako etapm 3, wielokrotne iterowanie kompozycji pozwala przyspieszyć budowę szybko rosnących funkcji. Zajmijmy się tym etapem, czyli kompozycją.

Rozpatrujemy funkcje postaci  [;f\ g\ \dots : \mathbf Z^+\rightarrow\mathbf Z^+;],  zbioru nieujemnych liczb całkowitych  [;\mathbf Z^+ := \{0\ 1\ 2\ \dots\};]  w siebie. Kompozycją (albo superpozycją) dwóch funkcji  [;f\ g;]  nazywamy funkcję  ,  zdefiniowaną jak następuje:

               

Na przykład:

• [;(\nu\circ\nu)(n) = n+2;]


• [;(\delta\circ\delta)(n) = \left(n^n\right)^{n^n};]

Następnie zdefiniujmy potęgę  [;\bigcirc^n;]  dowolnej funkcji  [;f;]  względem kompozycji. Zaczynamy od funkcji identycznościowej  [;\iota : \mathbf Z^+\rightarrow\mathbf Z^+;],  danej wzorem:

                [;\iota(n) := n;]

Oczywiście:

                [;\iota\circ f = f \circ\iota = f;]

dla dowolnej funkcji  [;f : \mathbf Z^+\rightarrow\mathbf Z^+;].  Teraz już możemy przystąpić do definicji potęgi  [;\bigcirc^n;]:

                [;\bigcirc^0 f = \iota;]
                [;\bigcirc^n f = (\bigcirc^{n-1} f)\circ f = f\circ (\bigcirc^{n-1} f);]

dla dowolnego  [;n > 0;].  Na przykład  [;\bigcirc^3 f = f\circ f\circ f;].

W szczególności:

• [;\left(\bigcirc^3 \nu\right)\left(n\right) = n+3;]


• [;\left(\bigcirc^k \nu\right)\left(n\right) = n+k;]


• [;\left(\bigcirc^n \nu\right)\left(n\right) = 2\cdot n;]


• [;\left(\bigcirc^3 \delta\right)\left(n\right) = \left(\left(n^n\right)^{n^n}\right)^{\left(n^n\right)^{n^n}};]

Zauważmy, że akcent przesunął się z definiowania funkcji, czyli przyporządkowania liczbom liczb, na definiowanie operatorów, czyli na przyporządkowywanie funkcjom funkcji:

                [;\Omega : \hom(\mathbf Z^+\ \mathbf Z^+) \rightarrow \hom(\mathbf Z^+\ \mathbf Z^+);]

gdzie  [;\hom(\mathbf Z^+\ \mathbf Z^+);] oznacza zbiór wszystkich funkcji  [;\mathbf Z^+;]  w siebie. Operatorem jest na przykład potęga  [;\bigcirc^n;].

Wprowadzenie operatorów jest naszym czwartym etapem. Przypomnę je:

1. operacje arytmetyczne


2. fukcje


3. kompozycja funkcji


4. operatory

Teraz z kolei, dodam szybko, możnaby stosować kompozycję operatorów, i operatory operatorów, itd. Nie chce mi się tych konstrukcji uważać za nowe etapy. Zamiast tego raz na zawsze zauważmy, że operatory też są funkcjami (choć o innym zbiorze argumentów i wartości), więc dalsze kroki możemy koncepcyjnie uważać za znajome, za te same etapy, co już naszkicowane.

Możemy rozpatrywać także operatory dwóch zmiennych (ich zmienne przebiegają przez zbiór funkcji), jak na przykład  [;\Delta;],  gdzie:

                [;h = \Delta^g f;]

wtedy i tylko wtedy, gdy:

                [;h(n) =

\left(\bigcirc^{g(n)} f\right)(n);]

Innymi słowy:

                [;\left(\Delta^g f\right)(n) :=

\left(\bigcirc^{g(n)} f\right)(n);]

Z operatora dwuargumentowego możemy uzyskać szereg operatorów jednoargumentowych (podobnie jest z operacjami arytmetycznymi), jak na przykład operatory (jednej zmiennej)  [;\Delta^{\iota};]  oraz  [;\Theta;],  zdefiniowane następująco:

                [;\left(\Delta^{\iota} f\right)(n) := \left(\bigcirc^n f\right)(n);]
                [;\left(\Theta f\right)(n) :=

\left(\bigcirc^{f(n)} f\right)(n);]

Ten pierwszy jest regularniejszy, a drugi bardziej chciwy (daje szybciej szybciej rosnące funkcje).

Zastosowania

Potęga kompozycyjna

Zacznijmy od operatora potęgi kompozycyjnej:

1. [;\beta(n) := \left(\bigcirc^n \nu\right)\left(n\right) = 2\cdot n;]


2. [;\left(\bigcirc^k \beta\right)\left(n\right) = 2^k\cdot n;]


3. [;\gamma(n) := \left(\bigcirc^n \beta\right)\left(1\right) = 2^n;]


4. [;\left(\bigcirc^k \gamma\right)\left(n\right) = 2^{2^{\dots^{2^n}}};]   (k dwójek)


5. [;\Gamma(n) := \left(\bigcirc^n \gamma\right)\left(1\right) = 2^{2^{\dots^{2^2}}};]   (n dwójek)

Kolejne wartości  [;\Gamma(n);],  dla  [;n = 0\ 1\ \2\dots;],  wynoszą:

        [;1\quad 2\quad 4\quad 16\quad 65536\quad 2^{65536}\quad 2^{2^{65536}}\quad \dots;]

---

Wyłoniła się regularność. Możemy zdefiniować ciąg eleganckich, coraz szybszych funkcji  [;\beta_n;],  poczynając od  [;\beta;]:

• [;\beta_0:=\beta;]


• [;\beta_n (k) := \left(\bigcirc^k\beta_{n-1}\right)(1);]   dla   [;n>0;]

Tak więc  [;\gamma = \beta_1,\quad\Gamma=\beta_2;].  Następne funkcje  [;G:=\beta_3,\dots;]  będą już potworne czyli monstrualne.

Skromna przekątna

Pora na sprawdzenie skromnej przekątnej  [;\Delta^{\iota};]:

1. [;\left(\Delta^{\iota} \nu\right)(n) = \left(\bigcirc^n \nu\right)(n) = \beta(n) = 2\cdot n;]     czyli     [;\Delta^{\iota} \nu = \beta;]


2. [;\left(\Delta^{\iota} \beta\right)(n) = \left(\bigcirc^n \beta\right)(n) = n\cdot 2^n = n\cdot\gamma(n);]


3. [;\left(\Delta^{\iota} \beta\right)(n) = \gamma(n+k);]     dla     [;n=2^k;];   czyli:


4. [;\left(\Delta^{\iota} \beta\right)\circ\gamma = \gamma\circ(\gamma+\iota);]


5. [;\left(\Delta^{\iota} \gamma\right)(n) = \left(\bigcirc^n \gamma\right)(n) = 2^{2^{\dots^{2^n}}};]   (n dwójek)


6. [;\left(\Delta^{\iota} \gamma\right)(n) = \Gamma(n+k);]     dla     [;n=\Gamma(k);];   czyli:


7. [;\left(\Delta^{\iota} \gamma\right)\circ\Gamma = \Gamma\circ(\Gamma+\iota);]

Zachodzi ogólne twierdzenie:

TWIERDZENIE 0

                [;(\Delta^{\iota} \beta_n)\circ\beta_{n+1} = \beta_{n+1}\circ(\beta_{n+1}+\iota);]

dla dowolnego  [;n=0\ 1\ \dots;].

DOWÓD

        [;\left(\left(\Delta^{\iota} \beta_n\right)\circ\beta_{n+1}\right)(k) = \left(\Delta^{\iota} \beta_n\right)\left(\beta_{n+1}\left(k\right)\right);]

        [;=\left(\bigcirc^{\beta_{n+1}\left(k\right)} \beta_n\right)\left(\beta_{n+1}\left(k\right)\right) = \left(\bigcirc^{\beta_{n+1}\left(k\right)} \beta_n\right)\left(\left(\bigcirc^k\beta_n\right)\left(1\right)\right);]

        [;=\left(\bigcirc^{\beta_{n+1}\left(k\right)+k} \beta_n\right)\left(1\right) = \beta_{n+1}\left(\beta_{n+1}\left(k\right)+k\right);]

        [;=\left(\beta_{n+1}\circ\left(\beta_{n+1}+\iota\right)\right)\left(k\right);]

KONIEC DOWODU

Twierdzenie to pokazuje między innymi, że funkcja  [;\Delta^{\iota}\beta_n;]  jest nieco szybsza od  [;\beta_{n+1};].  Przy tym słowo nieco należy rozumieć w sensie koncepcyjnym, bo naiwnie to o wiele.

Wielkie Liczby, Cz 1

Zaczynam zawsze serie notek od Cz 0 (i na niej na ogół kończę). Czyżbym teraz rozpoczął od Cz 1, a nie Cz 0? Ależ skąd! Cz 0 dałem na buzza bezpośrednio. Podałem w niej najprostsze funkcje, że tak powiem - bezpośrednie, dosyć szybko rosnące. Bo nie chodzi tak naprawdę o wielkie liczby, lecz o szybko rosnące funkcje. W szczególności wspomniałem silnię, [;n!;], oraz potęgę [;\Delta(n):=n^n;]. Ta ostatnia oczywiście rośnie znacznie szybciej. Jednak silnia dopuszcza prostszą definicję rekurencyjną:

• [;0!:=1;]


• [;\forall_{n>0}\quad n!:=n\cdot(n-1)!;]

Dla  [;\Delta(n);]  nie widzę równie prostej definicji rekurencyjnej, w której występowałaby tylko jedna zmienna. Gdyby jednak pogodzić się z potęgowaniem, to można wprowadzić znacznie szybciej rosnącą funkcję  [;\nabla(n);]  dla  [;n=1\ 2\ ...;],  jakby silnię eksponencjalną:

• [;\nabla(1):=1;]


• [;\forall_{n>0}\quad \nabla(n):=n^{\nabla(n-1)};]

- wizualnie:

    [;1\quad 2^1\quad 3^{2^1}\quad 4^{3^{2^1}}\quad 5^{4^{3^{2^1}}}\quad\dots;]

czyli

    [;1\quad 2\quad 9\quad 262144\quad 5^{262144}\quad\dots;]

Matematycy nie są tak chciwi. Na ogół wolą prostotę, na przykład wieżę dwójkową  [;w(n);],  gdzie

• [;w(0):=1;]


• [;\forall_{n>0}\quad w(n):=2^{w(n-1));]

- wizualnie

    [;1\quad 2\quad 2^2\quad 2^{2^2}\quad 2^{2^{2^2}}\quad 2^{2^{2^{2^2}}}\dots;]

czyli

    [;1\quad 2\quad 4\quad 16\quad 65536\quad 2^{65536}\quad\dots;]

---

Chodziłem do 8 klasy razem z Julkiem Burginem, który podarował mi wtedy piękne polskie wydanie "Kalejdoskopu Matematycznego", Hugona Steinhausa. Steinhaus definiuje w nim ogromne liczby obrazowo (oryginalna była właśnie obrazowość, bo temat był poważnie rozwinięty wcześniej, przez logików, w kontekście teorii funkcji rekursywnych i obliczalności). Zaczyna Steinhaus od  [;n;]  narysowanego w trójkącie, co definiuje, jako  [;n^n;].  Ja jednak piszę [;\Delta(n);]. Następnie definiuje/rysuje Steinhaus  [;n;]  wewnątrz kwadratu, co - Steinhaus mówi nam - oznacza to samo, co  [;n;]  narysowane w  [;n;]  trójkątach (dostajemy trójkątną cebulę). Będę tu pisał  [;\square(n);]. Zatem

• [;\square(2) = \Delta(\Delta(2)) = \Delta(4) = 256;]


• [;\square(3) = \Delta(\Delta(\Delta(3))) = \Delta(\Delta(27)) = \left(27^{27}\right)^{27^{27}};]


• itd. :-)

Widzimy, że funkcja  [;\square(n);]  rośnie całkiem żwawo. Steinhaus na tym nie poprzestaje. Mógłby z kolei wprowadzić n w pięciokącie, potem w sześciokącie, ... Zlenił się, i poprzestal na następnym kroku, jako, że chodziło mu tylko o edukację wstępną i rozrywkę. Zatem nie mówi o pięciokącie, lecz o kółku/okręgu. Tak więc definuje  [;n;]  w kółku, jako  [;n;]  narysowane w  [;n;]  kwadratach. Będę pisał  [;\bigcirc(n);].  Na przykład:

    [;\bigcirc(2) = \square(\square(2)) = \square(256) = \dots;]

koszmar! :-) Mamy bowiem  256  w  256  trójkątach, czyli  [;256^{256}=65536;]  w  255  trójkątach, czyli  [;65536^{65536};]  w  254  trójkątach, itd. itd. itd. ...

Hipokryzja nowoczesnego niewolnictwa

W starożytności właściciele niewolników co najwyżej byli dumni, całkiem otwarcie, z posiadania niewolników, czyli ludzi, którzy musieli na nich pracować. Nic pięknego, ale przynajmniej posiadacze niewolników sprawę stawiali otwarcie.

Kiedyś państwa były własnością króli (z grubsza mówiąc). Król nie ściągał podatku dla biednych lub dla dobra powszechnego, lecz bez kłamania ściągał podatki dla siebie.

Dziś biurokratyczna hołota, zniewalająca społeczeństwo, ocieka hiprokryzją. Oni ściągają podatki jakoby nie dla dalszego, jeszcze silniejszego podporządkowania sobie społeczeństwa, o nie, skądże - oni muszą zawsze bełkotać o "wyższych i szlachetnych" celach, jak pomoc biednym, edukacja, nauka, opieka zdrowotna... Przy tym niszczą każdą z tych dziedzin, skazując na nędzę i zależność od rządu jak najwięcej oduczonych od pracowania ludzi (takich najłatwiej kontrolować, i tak głupków zwanymi "liberałami" głupków).

Biurokratyczny system tworzy fortuny z niczego, z czystego złodziejstwa finansowego, a ludzie męczą się, cierpią. Przykładem jest sforsowana przez Billa Clintona super machlojka pożyczek bankowych na domy, która była bodajże bezpośrednim, może wręcz głównym powodem obecnego kryzysu gospodarczego.

Gdyby chodziło o zabranie pieniędzy bogatym, i danie tych pieniędzy biednym, na edukację, itd, to dlaczego koniecznie trzeba te pieniądze najpierw dać rządowi ??? !!! Dlaczego jedyna metoda pomagania ludziom musi (według zasmarkanych "liberalów") zawsze prowadzić poprzez podatki na biurokrację, dlaczego? Dlaczego nie chcą się nauczyć z doświaczenia wielu dziesięcioleci? Skąd taki brak wyobraźni, takie ograniczenie i otumanienie? Odpowiedź jest prosta. Bo wcale nie są zainteresowanie w celach, które hipokrytycznie głoszą. Są zainteresowani wyłącznie w kontrolowaniu czyli zniewalaniu bliźnich. Taka jest prawda OBIEKTYWNA.

Przecież bogaci mogliby, i tak by czynili, pod presją społeczną wydawać te pieniądze bezpośrednio na jedzenie i mieszkania dla biednych, na stypendia dla studentów, na laboratoria szkolne i akademickie, ... Instytucje by to publicznie kwitowały. Z łatwością znaleźliby się zapaleńcy, którzy by te publiczne informacje z Internetu zebrali, zorganizowali w przejrzyste tabele, ... i z powrotem opublikowali w Internecie. Bez żadnej marnacji na urząd podatkowy i parlamentarzystów (:-) efekt byłby stokroć lepszy, bo nie pasłoby się raka biurokracji. Prawdopodobnie przekazaliby bogaci na zbożne cele o wiele więcej niż w sumie na podatki i na filantropię. Prześcigaliby się. Staraliny się być na czele filantropistów. Bowiem nie musieliby wydawać tyle na prawników i ksiegowych. Przede wszystkim dlatego, że zamiast bawić-chrzanić się z urzędem podatkowym, wielu ambitnie bawiłoby się właśnie w filantropię.

Przecież w Kongresie Amerykańskim Demokraci narzekają, że bogaci często na podatki wydają ... ZERO. Że płacą mniejszy procent od klasy średniej. Oczywiście że tak. To ich zabawa. Od tego maja prawników. Od tego mają też między innymi demokratycznych parlamentarzystów, żeby im się - bogatym - krzywda nie stała.

---

Co jakiś czas rząd niby próbuje się zredukować. To tak jakby rak co jakiś czas robił sobie po brzegach minichemoterapię i lokalne operacje chirurgiczne. Jak pisałem na Poland-L w 1990 roku, jedyna metoda na raka biurokracji, to odciąć dopływ krwii, zamożyć, czyli pozbawić podatków. Wszystko co niby dla ludzi robi rząd, ludzie mogą sto razy lepiej robić sami. Gdy na przykład chodzi o ubezpieczenia lekarskie, to przecież i tak ludzie ludzi ubezpieczają. Więc sami powinni to robić, bez rządu i bez wielkich firm ubezpieczeniowych, bez marnowania ponad 95% swoich pieniędzy na raka biurokratycznego, bez niszczenia jakże ważnej relacji z lekarzami. Gdy chodzi o edukacje, to Obama chce wydać biliony dolarów nie na polepszenie nauczanie (o czym zielonego pojęcia nie ma), lecz na rozbudowany system oceny efektywności edukacji, by biurokratycznie i skomplikowanie bawić się w przelewanie pieniędzy pomiędzy stanami. Uczniom i rodzcom potrzebna jest edukacja, a nie ocena skuteczności edukacji przez biurokratów. Wszystko jedno biliony ich dolarów - rodziców, i innych obywateli - pojdzie na biurokrację wypełniającą formularze oceniające "efektywność", potrzebną wyłącznie biurokracji, a nie uczniom. To jest bardzo skuteczny sposób okradania społeczeństwa.

W każdej dziedzinie życia społecznego ludzie mogą i powinni organizować się sami, bez rządowego raka, który każde działanie ludzi zatruwa. Zamiast wkładać być obrotnym (wiedzieć w których stać rządowych kolejkach po to i sio i wszystko), zamiast kręcić i oszukiwać i kraść w systemie biurokratycznym, to powinni rząd odsunąć, kroczek po kroczku, i działać samodzielnie, jak dojrzali ludzie dorośli, a nie jak Homo Sovieticus.

Gdy pracodawca nie wie czego chce

Sporo mówi się o tym, że kontrakt pomiędzy pracodawcą i konsultantem pracującym na zasadzie "flat fee" (lub nawet w ogóle :-) powinien dokładnie określić co konsultant ma osiągnąć dla pracodawcy. Niezła zasada, choć widywałem okazyjnie opłakane skutki. Wielka firma i mała zaczynają jako przyjaciele, a kończą jako wrogowie, z obopólnymi pretensjami.

Tak czy inaczej, bywa, że potencjalny pracodawca wie z grubsza o co mu chodzi, ale nie na tyle, żeby spisać dokładny kontrakt, wyliczający etapy, itp. Tak na przykład jest, gdy firma potrzebuje oryginalnego hardware'u. Specjalnością firmy są powiedzmy zastosowania takiego hardware'u, ale nie samo jego tworzenie napoziomie inżynieryjnym, nawet gdy ma koncepcyjny opis nowego schematu. Co wtedy? Przecież biznes jakoś powinien iść naprzód. A tu nawet umowy nie ma jak spisać.

Właściciel firmy z Santa Bardbara (sam był chyba inżynierem lub fizykiem z wykształcenia; stroną techniczną już się wiele nie zajmował detalicznie, ale chyba znał się dobrze) miał odpowiedź: proponował pierwszy etap, niezależny. Pracodawca płacił za ten pierwszy etap, ale mógł na tym współpracę zakończyć, a owoc pierwszego etapu należał już do niego. Pierwszy etap polegał właśnie na ustaleniu dokładnego planu działania. Ponieważ pracodawca za ten plan płacił, to mógł potem firmie konsultanckiej podziękować, a plan wykorzystać we współpracy z inną firmą, która by ten plan wykonała może taniej. Wszyscy na tym zyskiwali. Projekt szedł naprzód. Nikt wiele nie ryzykował, nikt nie pracował za darmo, ani nie płacił za nic.

Rozbijanie problemu na etapy jest jedną z zasad Sztuki Uzgadniania. Niby zasada odwieczna, oczywista, trywialna, każdy wie... Ale warto o niej pamiętać w sytuacjach zdawałoby się konfliktowych lub bez wyjścia. Czasem w praktyce zasada ta nie przychodzi stronom do głowy. Warto pamiętać, że stosowanie tej i innych prostych zasad Sztuki Uzgadniania wymaga twórczego myślenia, wymaga wyobraźni, fantazji. Szkoda, że ludzie wolą przegłosować sprawę, załatwić wszystko na siłę (legalnie, czyli prawem kaduka!), ku frustracji większości i radości złodziei. Nie tyle ludzie wolą, co sobie inaczej nie wyobrażają.

Softaware, itd.

Spis rzeczy

• Software


• Jak nie zarobiłem


• Podejście do programnowania

Software

Ostatnio toczy się w buzzie wiee...eelka dyskusja o oprogramowaniu. Głos zabierają wielcy programiści i managerowie, więc mi tam trochę nawet niezręcznie się odzywać. Jakbym, jak w muzyce, rzępolił na gitarze, gdy tam zebrali się prawdziwi kompozytorzy-wykonawcy i koneserzy. Co prawda rzępoliłem czasem (zawsze! :-) tony, których wcześniej nie słyszałem, lub zdawałem sobie z nich sprawę ledwo mgliście, więc ciągle jakby improwizowałem. ... Mógłbym opowiadać bez końca, ale nie o mnie chodzi.

Myślę, że szanowne, doborowe towarzystwo mogłoby skolekcjonować listę wybitnych software'owych artystów.

Z pewnością rej w niej będą wodzić między innymi lub głównie autorzy języków komputerowych. Jednak samo stworzenie języka nie powinno wystarczyć, to inna kategoria. Powinni także wykazać się eleganckimi próbkami kodu. Z pewnością tak będzie prawie za każdym razem. Jednak nic mi nie wiadomo o takich próbkach w przypadku twórcy pięknego języka Forth - Charles H. Moore'a. Nie zrobił na mnie miłego wrażenia, gdy go spotkałem osobiście, słuchałem jego odczytu. Co prawda nie jestem pewny, czy czasem o wiele więcej uznania nie należy się Elizabeth D. Rather, która z Forth uczyniła dojrzały język, zamiast kupy macros. Czy ktoś z Was orientuje się dokładniej? (Przyjaźniłem się z entuzjastą i super-ekspertem Fortha, Dr Ting. Warto popatrzeć, co on pisze; co prawda był wpatrzony w Moore'a jak w obraz).

Z drugiej strony nie znam próbek Larry Walla, twórcy Perla, ale widzę aż nadto, że jest artystą.

Jak nie zarobiłem

Historii pod takim tytułem mógłbym podać więcej. W danym wypadku z pewnym kolegą-managerem pracowałem wcześniej przez około rok, jako konsultant, ale na więcej niż pełny wymiar godzin (jednak nigdy nie więcej niż 12h na dobę, z reguły 12h, i 7 dni w tygodniu :-); tak było przez jakieś 9 miesięcy, po czym pewien projekt wykonałem na zasadzie "flat rate"). Teraz chciał mnie zatrudnić znowu. Ponieważ trochę się go obawiałem, to zażyczyłem sobie, żeby kontrakt dokładnie opiewał co mam zrobić. Tymczasem on uparł się, żeby wstawić frazę o "best effort". Czyli, że będę pracował ze wszystkich sił, najlepiej jak tylko potrafię. Nawet pewien miły człowiek pomagał nam jako pośrednik, bardzo cierpliwie i rozsądnie. Firma tego człowieka dostałaby część projektu. Pracowałem z tym właścicielem firmy harmonijnie w przeszłości, nawet kilka dni u niego mieszkałem, w Santa Barbara (pięknie tam, i mimo południowego położenia - ciut chłodno, chłodniej niż w Silicon Valley). Nic z umowy z moim kolegą nie wyszło. Obaj, manager i ja, zaparliśmy się. Koniec.

Po czasie myślę, że mogłem wtedy podjąć jedną więcej próbę dogadania się. Należało projekt, nie taki znowu mały, rozbić na części, i ustalić harmonogram płacenia. Po każdej części musiałby mi zapłacić, i dopiero potem przystąpiłbym do następnej. (Poniewać wszystko długo trwało w ogromnej firmie managera, to prawdopodobnie wypłaciłby mi z góry więcej :-). Wtedy nie bałbym się frazy "best effort". Rozumiałoby się, że każda strona mogłaby zakończyć współpracę po dowolnym etapie, gdyby po którymś etapie była z drugiej strony niezadowolona.

Dlaczego mój kolega tak się uparł? Przecież znał mnie, wiedział, że pracuję intensywnie. Czasem w nocy robiliśmy sobie przerwę na drinka, udawaliśmy się do baru lub restauracji. Po czym on się rozkładał, jechał do domu, a ja wracałem do pracy. Nie miałoby sensu dla mnie zepsuć sobie dobrą opinię. Myślę, że zależało mu na słodkim uczuciu kontrolowaniu drugiego. Gdy poznaliśmy się, on był na samym dole drabiny managerskiej w swojej firmie. W czasie wspólpracy piął się w górę. Im wyżej był, tym trudniej było wspólpracować. Na początku co powiedziałem technicznie, tak było. Z czasem zaczął się "konsultować" z innymi, a w przypadku pewnego mojego większego pomysłu ponadto chciał nawet zwołać większe zebranie, żeby niby wszyscy razem by zdecydowali - bez sensu!

Potem miałem niepotrzebną mi, gorzką satysfakcję. Mój kolega do pracy, którą miałem wykonać, wynajął niewielką, ale całą zawodową firmę software'ową. Przez pewien czas był z nich zadowolony. Prawdziwi unixowcy, znają narzędzia, napisali śliczny kod, profesjonalnie, piękne indentacje, przyjemnie patrzeć. Tyle że kod dreptał w miejscu, nigdy niczego nie byl w stanie wyliczyć, bo zajmowało mu wieki i milenia. Projekt upadł.Nawet domyślałem się dlaczego ich oprogramnowanie ślamarzyło się, gdy moje kody fruwały. Prawdopodobnie używali unixowe narzędzia do tworzenia języków. Taki trade-off, bo łatwo się pisze, szybko, rekursyjnie, niewiele się samemu myśli, niewiele się samemu rozumie, bo OGÓLNY kod SAM wszystko wie za człowieka. Tylko, że kiedy kod wie wszystko, to nic nie wie o szybkości, zero. A w ambitnych, złożonych sytuacjach bez szybkości nie ma się niczego, nie ma o czym mówić, bo na wyniki programu trzeba czekać w grób-mogile po wieki. U mnie nazwa funkcji od razu funkcję wykonuje. U tych korzystaczy z narzędzi, gdy w programie występuje nazwa funkcji z zastosowania, to ich kompiler musi najpier tę funkcję rozpoznać, musi dokonać parsingu. U mnie użytkownik, wcale sobie z tego nie zdając sprawy :-), sam parsował machinalnie, a kompiler języka i komputer tylko program egzekwował. Przy symulacjach zawsze stosowałem ten bezpośredni styl. (Myślę, że wtedy programy użytkownika jest też bez porównania łatwiej użytkownikowi debuggować).


Kiedyś (nieco później), kiedy patrzyłem na budynek pewnej firmy biologicznej z okna mojego mieszkania - akurat miałem taki widok w niedalekiej oddali) to się uśmiechałem. Bowiem dla siebie, prywatnie, napisałem kod dla aminokwasów, i przyjemnie było patrzeć jak lata. A oni kod, robiący to samo, reklamowali, a nawet udostępniali publice. Zabawy z ich kodem było niewiele, bo ich marnując wiele czasu byl w stanie czasem rozwiązywać łancuchy długości do 5, może 7 symboli (chyyba nie :-). Myślę, że zgadłem powód, dla którego ich kod nie działał. Chodziło o optymizację. Wprowadza się w niej pewne wagi. Głowę dam, że oni "genialnie" (:-) rozpatrywali także wagi ujemne, nie rozumiejąc, że wtedy powstają nieskończone pętle. Zamiast czynić pewne wagi ujemnymi, należało zwiększyć pozostałe. Wtedy algorytm (programowanie dynamiczne) działałby jak ta lala.

Podejście do programnowania

Kolejne dzieci uczyłem jak programować gry w BASICu dla młodszych dzieci. Nie pamiętam, czy nauczyłem także najmłodszą, bo ona już nie miała komu programować. A przede wszystkim, mówiąc serio, sytuacja życiowa się zmieniała. W każdym razie jej brat, sam szkrab, programował dla niej od ręki, kiedy się nudziła. Program pytal ją jak ma na imię, potem zwracał się do niej po imieniu. Ona miała pomyśleć sobie liczbę, a program liczbę zgadywał, dzieląc przedział na pół, pytając ją czy już, czy też ma iść w górę lub w dół. Dziecku było przyjemnie grać.

Podobny porogram napisał mój kolega w pracy, inżynier-manager, dla swojej córki. Program robił na ekranie wrażenie niesprzątneitej hali fabrycznej w porwnaniu ze schludnym, wygodnym mieszkanie. Nic koledze nie powiedziałem, nie miałem serca, gdy przecież tak się dla swojego dziecka postarał (w pracy byłem dla niego znacznie ostrzejszy, mimo że był formalnie moim bosem). Oczywiście poprawiłbym mu programik, ale przecież nie mogłem ingerować w życie rodzinne kolegi, itd.

To jest moja odpowiedź - przynajmniej metafora - na pytanie o znaczenie zwrotu "życia programowaniem". Bo nie chodzi akurat o "user interface", tylko o podejście w każdym wymiarze. (W środku kod mojego szkraba-syna też ładniej wyglądał, niż kolegi. Dlatego może po latach syn, prawie bez formalnego wykształcenia, dawał odczyty na konferencjach, i bardzo ładnie zarabiał, ucząc w firmach programowania).

Obniżanie poziomu i niszczenie dyskusji

W celu przeanalizowania powodów obniżania poziomu i niszczenia dyskusji zdecydowałem się na ich formalny podział. Zakładam przy tym ustalony zasób informacji i wiedzy (tych aspektów nie dyskutuję tutaj).

Każdy może proponować swoją własną klasyfikację pułapek dyskusyjnych. Tego typu konstrukcje nie są prawdziwe lub nieprawdziwe lecz korzystne dla analizowania lub mało korzystne (lub wręcz szkodliwe, bo zbyt mętne, itp).

Zajmowało się w przeszłości podobnymi sprawami sporo znanych ludzi, zwłaszcza filozofów. Jeżeli ich pominąć, to wspomnę, że też zastanawiałem się nad tym tematem od dziesiątków lat.

Mam nadzieję, że moja klasyfikacja jest pożyteczna dla zrozumienia mechanizmów niszczących dyskusje. Powody istnieją dwa:

1. miękkość umysłu


2. zła wola

Podkreślam, że jest to formalna klasyfikacja, że znaczenie złej woli sprowadza się do dyskutowania na poziomie niższym, niżby na to wskazywała jakość mózgu dyskutanta. Czyli tak właśnie definuję złą wolę.

Podział jest delikatny, dynamiczny. Na przykład, opowiadanie się za fałszywą alternatywą na początku dyskusji prawdopodobnie oznacza miękkość umysłu dyskutanta - brak wyobraźni lub ciasny umysł (nie otwarty na nieznane mu możliwości, mimo że powinien taką opcję dopuszczać). Natomiast dalsze upieranie się przy fałszywej alternatywie, gdy w dyskusji przedstawione nowe opcje, jest już złą wolą.

Poziom dyskusji zawsze zależy od totalnego zasobu (kompletności) informacji i wiedzy wszystkich uczestników dyskusji razem. Tego nie włączam do mojej analizy. Natomiast ignorowanie przez dyskutanta nowej dla niego informacji/wiedzy, przedstawionej w dyskusji przez innego dyskutanta, podpada pod złą wolę lub miękkość umysłu.

UWAGA  To jest tylko wstępna notka, kropla w oceanie. Gdy, o ile, pojawią się dalsze, to w tytule niniejszej notki dodam na koniec swoje standardowe "Cz 0".

Wyrażenia i twierdzenia analityczno-geometryczne

Niech  [;\mathbf C;] będzie ciałem (płaszczyzną) liczb zespolonych. Odległością euklidesową  [;d(v\ w);]  pomiędzy dwoma punktami  [;v\ w;\in\mathbf C;]  nazywamy moduł ich różnicy czyli

                [;d(v\ w)\ :=\ |w-v|;]

gdzie

                [;|z| := \sqrt{z\cdot\bar z};]

dla dowolnego  [;z\in\mathbf C;]. W nocie Dwa podejścia do geometrii - logiczne i grupowe. Cz 0. obiekty i twierdzenia geometryczne zostały (nieściśle) zdefiniowane jako te, które wyrażają się wyłącznie poprzez odległości, a nie poprzez współrzędne lub operacje algebraiczne. Pewne wyrażenia analityczne dają się jednak przedstawić równoważnie jako geometryczne. Twierdzenia analityczno-geometryczne, o geometrycznym charakterze pewnych wyrażeń analitycznych, pozwalają stosować w geometrii metody analityczne (algebraiczne). Przykładem może służyć pojęcie środka algebraicznego, czyli relacja pomiędzy trzema punktami  [;\mu\ v\ w\in\mathbf C;]:

                [;\mu := \frac{v+w}{2};]

mimo analitycznej formy okazuje się być geometryczna, gdyż takie  [;\mu;]  jest jedynym(!) punktem, spełniającym warunek geometryczny bycia geometrycznym środkiem pozostałych dwóch punktów:

        [;d(v\ \mu)\ =\ d(\mu\ w)\ =\ \frac{d(v\ w)}{2};]

Tak więc pojęcie środka algebraicznego jest pojęciem geometrycznym. Natomiast pojęcie sumy i różnicy:


                [;\sigma := v+w;]

                [;\delta := w-v;]

nie są geometryczne, co wykażę w kolejnej Cz 1 wspomnianego postu Cz 0. Żeby było ciekawiej, okazuje się, że pokrewna relacja pomiędzy czterema punktami, polegająca na tym, że suma lub różnica jednej pary punktów jest równa odpowiednio sumie lub różnicy pozostałej pary punktów jest geometryczna.

UWAGA  Widzimy, że niewinna, drobna różnica w sformułowaniu może mieć ogromny wpływ na znaczenie. W matematyce żyjemy z tym na codzień, świadomie, ostro zdając sobie sprawę z tego zjawiska. W życiu codziennym i politycznym jest z tym o wiele gorzej. Rozmowy i dyskusje są nagminnie szpecone przez tego typu nieporozumienia.

Popatrzmy na wspomniane wyżej relacje pomiędzy czterema punktami  [;(a\ b;\ v\ w);]:


                [;b-a = w-v;]

                [;a+w = b+v;]

Jest oczywistym, że jest to jedna i ta sama relacja. Prawdopodobnie wielu z was widzi, że jest to relacja równoległoboka. Można ją też tak ująć: istnieje  [;\mathbf u\in\mathbf C;]  takie, że jednocześnie zachodzą dwie równości:


                [;b = a + \mathbf u;]

                [;w = v + \mathbf u;]

W takiej sytuacji myślimy o  [;\mathbf u;]  jako o wektorze, i mówimy, że punkty  [;b\ w;]  powstały przez przesunięcie odpowiednio punktów  [;a\ v;]  o ten sam wektor  [;\mathbf u;],  i właśnie dlatego ta czwórka punktów tworzy rownoległobok. Pokażę, że pojęcie równoległoboku jest geometryczne: rzeczywiście, jest ono równoważne relacji:

                [;\frac{a+w}{2} = \frac{b+v}{2};]

a wiemy, że pojęcie środka algebraicznego pokrywa się z pojęciem środka geometrycznego. Zatem relacja równoległoboku jest geometryczna. Geometrycznie mówi nam ona, że czwórka punktów  [;(a\ b;\ v\ w);]  ma następującą własność:

geometryczny środek pary  [;(a\ w);]  pokrywa się z geometrycznym środkiem pary  [;(b\ v);].

Może powstać wrażenie, że trudno jest odróżnic analityczne wyrażenia, mające sens geometryczny, od tych które nie mają; oraz że trudno jest zgadnąć, jak dowieść, że pewne wyrażenia analityczne są geometryczne. Na szczęście geometrzy stworzyli bardzo silne narzędzia, które takie sprawy na ogół rozstrzygają z lekkością. Będzie o tym w Cz 1.

Fizyk contra złośliwy programista

Widzę w buzzie długą, fachową dyskysję o sprawdzaniu poprawności programów. Niestety, nie jestem w stanie jej rozumieć. Mam za duże dziury erudycyjne w zakresie wiedzy o różnych programach, narzędziach, ... - nie jestem informatykiem. Temat jednak mnie ciekawi. Programy, nawet krótkie, potrafią być naprawdę trudne, mogą się opierać na bardzo nieoczywistych algorytmach, opierających się na wysoce nietrywialnych twierdzeniach. Czyż program sprawdzający poprawność programów, ale tak na pewniaka, nie musiałby mieć ogromnej wiedzy? Przerastającej wiedzę schowaną w programach?

Dla łatwego wprowadzenia tematu chcę zacząć od czegoś bardzo prostego, od zmyślonej sytuacji:

Pewien fizyk potrzebuje pliku z parami (punkt prosta), gdzie chodzi o pary incydentne, brane z płaszczyzny afinicznej rzędu 9 (ma 81 punktów), standardowej, nad ciałem GF(9). Zatrudnił więc fizyk programistę, żeby mu ten plik sprokurował. Poza tym od programisty wziął program, który programista napisał, żeby wygenerować żądaną płaszczyznę.

A teraz fizyk ma wątpliwości co do poprawności pliku i programu. Jak program sprawdzający poprawność pomoże fizykowi? Powiedzmy, że złośliwy programista poprawnie zaprogramował, ale niestandardową płaszczyznę. Odróżnić ją od standardowej jest bardzo trudno, ma szereg własności takich samych. Program sprawdzający poprawność mógłby nawet machnąć ręką (:-) na kod, i sprawdzić poprawność outputu. Porównać go z płaszczyzną standardową. Takie rzeczy robią CAD programy. Ogólnie taki problem, sprawdzający izomorfizm dwóch grafów, jest NP-complete (?), jest niewielomianowy. Więc gdyby chodziło o płaszczyzny wyższego rzędu, to CAD programy wysiadłyby, mimo że można takie płaszczyzny łatwo generować (dostać outputowy plik, przedstawiający graf punktowo-liniowy). Jeżeli programy CAD wysiadłyby, to jak sobie poradzi program sprawdzający poprawność? Musi jednak zajrzeć do kodu - powodzenia! Kod jest poprawny w pewnym sensie, ale produkuje płaszczyznę nieizomorficzną z żądaną. Dowód niepoprawności kodu wydaje mi się znacznie trudniejszym problemem niż dowód niepoprawności outputowego pliku; najprościej byłoby program puścić i analizować jednak output. Ba!

Oczywiście w przypadkach ogólnych sprawdzanie outputu jest niemożliwe, bo w zależności od inputu, output może być ogromny (a zastosowanie może korzystać tylko z małej części outputu, ale a priori z dowolnej, w zależności od losowych parametrów).

Może jednak zacznijmy od malutkiej 81-punktowej płaszczyzny nad ciałem GF(9).

Dwa podejścia do geometrii - logiczne i grupowe. Cz 0.

Uwagi wstępne

Dla skupienia uwagi, będę pisał o płaszczyźnie zespolonej  [;\mathbf C;],  ale przedstawione idee będą znacznie ogólniejsze.

Słowo grupowe w tytule tego postu odnosi się do teorii grup, która to teoria jest częścią algebry. Dla zrozumienia niniejszego postu nie ma większej potrzeby znajomości podstaw teorii grup (ale co Wam szkodzi zajrzeć tu i tam :-).

Tytuł mówi o dwóch podejściach do geometrii. W przypadku płaszczyzny okaże się (w Cz 1), że są one równoważne. Będzie tak ze względu na wielką jednorodność płaszczyzny. Prawdziwe, zdrowe, klasyczne geometrie kochają jednorodność.

Podejście "logiczne"

Odległością  [;d(v\ w);]  pomiędzy dwoma liczbami (punktami) zespolonymi  [;v\ w\in\mathbf C;]  nazywamy moduł ich różnicy

                [;d(v\ w)\ :=\ |w-v|;]

(jest to zwykła odległość euklidesowa). Odtąd możemy rozwijać geometrię metryczną płaszczyzny  [;\mathbf C;].  Przez twierdzenia tej teorii rozumie się twierdzenia, które wyrażają się wyłącznie w terminach odległości. Takim twierdzeniem jest na przykład nierówność trójkąta:

        [;d(u\ v)+d(v\ w)\ \ge\ d(u\ w);]

dla dowolnych liczb zespolonych  [;u\ v\ w\in\mathbf C;].

Twierdzenia takie nazywa się niezmienniczymi. Nie występują w nich ani współrzędne punktów (popularnie nazywane  [;x\ y;] - chodzi o część rzeczywistą i urojoną), ani nie występują w nich konkretne liczby zespolone ani operacje algebraiczne ciała liczb zespolonych, jak  [;\mathbf 0\ \mathbf 1\ +\ -\ \cdot;].  

UWAGA  Znak dodawania, który wystąpił w nierówności trójkąta, to było dodawanie odległości, a nie punktów (liczb zespolonych). Może tu dojść do pewnych subtelnośći (komplikacji), ale znowu nie chcę się rozpraszać.

Powyższe określenie twierdzeń geometrycznych geometrzy używają intuicyjnie z łatwością, ale jednak budzi ono lekki niepokój. Tylko lekki. Nie jest to jeszcze definicja ścisła. Żeby ją uściślić, trzeba by się sporo i cierpliwie potrudzić, co chętnie uczyniliby logicy. Powiedziliby dokładnie co to znaczy, że twierdzenie wyraża się jedynie w terminach odległości, czyli że jest niezmiennicze. Geometrzy nie za bardzo potrzebują uściślenia. Gdy rozwijają geometrię, to wiedzą, że geometrię, wiedzą to i bez uściślenia. Na dodatek, oprócz twierdzeń ściśle geometrycznych (niezmienniczych) istnieją, i są ważne, twierdzenia analityczno-geometryczne. Na przykład, algebraicznym środkiem liczb zespolonych (punktów)  [;v\ w\in\mathbf C;] nazywamy punkt

        [;s(v\ w)\ :=\ \frac{v+w}{2};]

Natomiast ich geometrycznym środkiem nazywamy punkt  [;S(v\ w);], który spełnia warunek:

        [;d(v\ S(v\ w)) = d(S(v\ w)\ w) = \frac{S(v\ w)}{2};]

Nawet a priori nie wiemy, czy taka geometryczna definicja jest poprawna - a co jeżeli więcej niż jeden punkt spełnia podany warunek geometryczny? A może czasem żaden? Otóż twierdzenie mówi, że środek algebraiczny i geometryczny pokrywają się:

        [;S(v\ w)\ =\ s(v\ w);]

dla dowolnych punktów  [;v\ w\in\mathbf C;]. W szczególnośći środek geometryczny dwóch punktów zawsze istnieje, i tylko jeden. Ponieważ środek algebraiczny nie jest pojęciem a priori geometrycznym (zawiera dodawanie liczb zespolonych oraz dzielenie przez 2), to twierdzenie o równości środków nie jest (czysto) geometryczne, lecz jest analityczno-geometryczne. Takie twierdzenia są ważne na przykład jako narzędzia, gdyż pozwalają geometrze korzystać z algebry, a ta ma tendencję do bycia prostą i klarowną. Na przykład, zgodnie z twierdzeniem o środku geometrycznym i algebraicznym, odtąd możemy w twierdzeniach geometrycznych (niezmienniczych) korzystać "legalnie" ze środka algebraicznego, czyli z czegoś istotnego geometrycznie, a przy tym łatwego analitycznie. Ułatwia to znacznie rozwijanie geometrii.

Dla kontrastu, pojęcie dodawania liczb zespolonych  [;v+w;]  nie jest geometryczne, nie da się wyrazić czysto za pomocą wyłącznie odległości punktów. Matematyka potrafi zadziwiać. Po podzieleniu sumy przez 2 otrzymujemy pojęcie geometryczne. A algebraicznie prostsze wyrażenie samej sumy geometrycznym jednak nie jest. W tej chwili trudno byłoby nam tego dowieść, kupa żmudnej roboty, a nawet chyba nie widać dobrze jak się do tego zabrać, że suma nie jest geometryczna.

W następnej części przedstawię podejście grupowe. Wtedy na takie pytania będzie można odpowiadać rutynowo, na ogół z łatwością. Ponieważ podejście grupowe będzie równoważne z logicznym, to trudne dla podejścia logicznego pytania staną się łatwe. Byle zainwestować jednorazowo w podstawowe twierdzenie o równoważności dwóch podejść.

Prostactwo, naiwność, prostota - niebliźniacze pojęcia

W konfliktowych dyskusjach często rozmówcy pozwalają sobie na poślizg z jednego z tytułowych pojęć: prostactwo, naiwność, prostota, na drugie. Pojęcia te jednak różnią się pomiędzy sobą mocno.

Sytuacja jest bardziej skomplikowana w poezji, gdzie dochodzi kwestia zauważania źródła słów (słyszenia głosu), oraz stylizacja. Powstają więc wśród krytyków (:-) dodatkowe nieporozumienia.

O ile naiwność poglądów jest ich poważnym minusem, to naiwne brzmienie wiersza lub wręcz naiwność samego wiersza minusem być nie musi, a nawet może być jego zaletą (urokiem).

Prostota i złożoność w jednym stali domu

Przepisy weiqi (GO) są znacznie prostsze i czystsze od szachowych, a i tak weiqi jest bez porównania bardziej złożoną grą (gdy chodzi o granie na wysokim poziomie) od szachów. W szachy komputery są dziś szachowo znacznie silniejsze od ludzi. Natomiast w weiqi wybitnie uzdolnione dzieci z łatwością ogrywają najsilniejsze komputery.

Gra LIFE jest niezwykle prosta, a jednak może symulować uniwersalną maszynę Turinga, czyli dokonać tych samych obliczeń, które potrafi najbardiej złożony komputer. Istnieją podobne gry jeszcze prostsze i równie uniwersalne czyli równie w działaniu złożone. Zresztą i przede wszystkim istnieją niezwykle proste uniwersalne maszyny Turinga.

Podobnie głębokie zrozumienie skomplikowanych sytuacji społeczno-ekonomicznych polega na ujęciu ich w proste prawa. Tyle, że byle pętak nadmie się wtedy, i autorytatywnie z arogancką dumą oświadczy: rzeczywistość jest skomplikowana, i wszelkie proste teorie są fałszywe. Daje to mu powód, żeby akceptować rozwiązania komplikowane przez interesowność jednych, brak zrozumienia u drugich, przez konformizm (i komformizm :-), oportunizm, złą wolę, korupcję, złodziejstwo, amoralność.

Oho, muszę lecieć, być może więcej napiszę potem.

Tragedia - 2009, 2011

Kiedy zabijani są masowo ludzie sprzeciwiający się tyranii, to jest to ich i ich rodzin tragedia, ich przyjaciół i ich środowiska. Każda porażka sił humanistycznych przeciwko nieludzkim jest też ogromną stratą dla jakości życia na całej Ziemi.

Dlatego, gdy w tv słyszę bezdenne, nieskończone paplanie typu "będziemy śledzić rozwój wypadków" lub "w każdym kraju sytuacja jest inna" lub "w tych krajach (muzułmańskich, arabskich) jest wiele zdolnej młodzieży, której należy dać szansę (na wykształcenie i sukcesy)", to robi mi się niedobrze. Ludzie są masowo mordowani, a narcyz z Białego Domu mówi o tym, jakby chodziło o niewinną reformę systemu edukacyjnego, milcząc przy tym na tematy zasadnicze, owijając prawdę w bawełnę. (Na przykład woli sugerować, że to w Stanach jest rasizm, czy w ogóle zła sytuacja pod każdym względem, niż że rasizm i drastyczny brak tolerancji religijnej panuje w krajach muzułmańskich; terrorystów też po imieniu nie nazwie terrorystami, ani nie powie kim są).

Wszelacy eksperci, reporterzy, politycy, generałowie, ..., rozprawiają o interwencji amerykańskich i innych oddziałów lądowych, ze słuszną konkluzją, że lepiej nie okupować krajów. Rozpatrują "no fly zone" (strefę bez lotów samolotowych i helikopterowych). To już jest o wiele prostsze, ale wciąż trudne. Zresztą nasz narcyz z Białego Domu zbyt kocha tych wszystkich tyranów, woli z nimi prowadzić biesiady dyplomatyczne. Więc tylko ogranicza się do przydługich, nudnych paplań. A czas leci, szpitale są bombardowane z helikopterów, w cywili strzela się pociskami rakietowymi.

Nie jest na przykład moją rolą podawać najcelniejsze rozwiązania. Nie mam informacji o wielu technicznych możliwościach. Od tego powinni być doradcy liderów. Jednak z miejsca nasuwa się, że raz i drugi proste zbombardowanie Gaddafiego ogromnie ulżyłoby opozycji, wielce utrudniając Gaddafiemu działalność (wojskową i wszelką), dając mu sygnał, że tego konfliktu absolutnie nie wygra, że źle skończy (jak Saddam) - prawdopodobnie szybko zwiałby do jakiejś Wenezueli czy gdzie tam.

Oczywiście należało z miejsca, i dalej należy, zbombardować militarne lotniska w Libii (i inne instalacje wojskowe).

Pożyteczna też byłaby akcja, powiedzmy 36 lub 48 godzinna, wojsk wyborowych (amerykańskich lub NATO). Zniszczyliby, ile by się dało, wojskowych instalacji i sprzętu wojskowego armii Gaddafiego (a po 36 lub 48 godzinach wycofaliby się).

Również znaczenie psychologiczne takich akcji, choćby negatywne na innych tyranów i ich świty, i pozytywne na opozycję przeciwko tyranii, byłoby ogromne.

Przegląd tematów matematycznych z mojej internetowej przeszłości. Cz.0

Wstęp

Wspomnę od ręki kilka tematów, którymi chciałem zainteresować także innych internautów. I dalej chcę.

Muszę smętnie zauważyć, że ograniczenia oprogramowania internetowego praktycznie wykluczyły dla mnie sporą część matematyki, gdy chodziło mi o rozmowy grupowe.

Każdy temat poniżej wprowadzę ogólnie (trochę ponudzę), po czym napiszę kilka słów konkretnie.

Gry

Od samego początku zajmowania się matematyką odczuwałem silne powiązanie matematyki i gier. Walkę o dowód odczuwałem jako grę przeciwko naturze. Dlatego swój pierwszy oryginalny wynik (1959/60), który w pierwszym wydaniu sformułowałem klasycznie, szybko przeformułowałem zgodnie z tym, jak go uzyskałem, jako zwycięstwo w pewnej grze, i w takiej formie posłałem go na konkurs imienia Marcinkiewicza (1961).

Zysk ze sformułowania wyniku w postaci gry jest następujący: klasyczne sformułowanie jest jakby zwycięstwem przeciwko jednej strategii przeciwnika, podczas gdy często można pokazać, że się wygrywa przeciwko dowolnej strategii przeciwnika. Wtedy otrzymuje się znacznie lepsze twierdzenie. Skupiając się potem na szczególnie ciekawych strategiach przeciwnika, otrzymuje się wtedy dodatkowe wyniki matematyczne.

Chociaż zawsze wymyślałem różne gry, to promowałem przede wszystkim gry innych. W szczególności "wyścigi samochodowe" z artykułu Gardnera (nie wiem, kto tę grę wymyślił), oraz grę Fajtlowicza o podciągach monotonicznych, opartą na twierdzeniu Erdosa. Tę ostatnią zaadoptowałem dla edukacji, nawet kilka wariacji. Gry w oparciu o twierdzenia matematyczne wprowadzało wcześniej wielu autorów. Ulam proponował rysować w 3D łamaną, aż się zamknie. Jeden z graczy wygrywa, gdy otrzymana krzywa zamknięta nie jest zawęźlona, a drugi, gdy jest. Inne gry, szereg, były oparte na twierdzeniu o punkcie stałym dla domkniętego koła (lub kwadratu), lub raczej na równoważnych twierdzeniach rodu z teorii wymiaru. Itd.

Czysto kombinatoryczna jest gra, na nieskończonej płaszczyźnie pokratkowanej, w powieszanego do 5. Każdy matematyk odruchowo zauważy i udowodni, że pierwszy gracz nie ma prawa przegrać, chyba że jest jołopem (żartuję, pół na pół). Zdaje się, że ktoś w końcu dowiódł, że przy poprawnej grze wynik jest remisowy (czy jest o tym w Internecie??? - chyba tak). Zatem w praktyce wygra długowieczny.

To była głównie pre-internetowa dygresja. W Internecie przedstawiłem trochę gier, bez większego echa. Przez pewien czas aktywnie z Julem Wnorowskim prowadziliśmy Google site Gry. Każdy z nas proponował swoje gry, nawet trochę graliśmy, choć niewiele (z braku czasu). Na buzzie też parę gier przedstawiłem, ale głownie zainteresował się nimi... Jul! :-)

Jedną z gier, którą stworzyłem, a Jul mnie ogrywał bezlitośnie, korzystała ze skończonej płaszczyzny afinicznej. Najlepiej się gra, gdy liczba punków na prostej jest liczbą pierwszą powiedzmy 5 albo 7, może nawet 11. Dla 7 gra jest już ciekawa. Na pewno warto w nią grać z dziećmi! - bardzo. Płaszczyznę afiniczną można przedstawić jako dyskretny kwadrat:

* * * * *
* * * * *
* * * * *
* * * * *
* * * * *

Prostymi są linie poziome, pionowe, i uogólnione przekątne, zawijane - na przykład:

* * # * *
* # * * *
# * * * *
* * * * #
* * * # *

albo

* * * # *
* # * * *
* * * * #
* * # * *
# * * * *

Gracze na przemian wykreślają wszystkie wcześniej nieskreślone punkty leżące na jednej prostej, przy czym należy wykreślić co najmniej dwa różne punkty. Kto nie będzie miał ruchu, ten przegra - czyli wygrywa ten, który po sobie pozostawi nie więcej niż 1 punkt. Jeżeli kogoś to zainteresuje, to mogę podać dokładniejszy opis (lub zajrzyjcie do site Jula ze mną). A gdyby ktoś przy okazji poczytał sobie o skończonych płaszczyznach afinicznych i rzutowych, to już w ogóle byłoby cudownie.

Granie w płaszczyznach rzutowych nie wniosłoby niczego nowego. Ale możnaby też grać w wykreślanie prostych lub hiperpłaszczyzn wyższego wymiaru (z oczywistą modyfikacją przepisu o legalności ruchu i o wygranej) w wyżej wymiarowych przestrzeniach; lub w ogóle w wykreślanie innych rodzin zbiorów. Płaszczyzna afiniczna wydaje się do grania być bardzo praktyczna.

Teoria Ramseya

Jest to rozległy i nieostro zarysowany temat matematyczny. Ciekawy wariant zaproponował swojego czasu Jan Mycielski (bez publikowania), i zajmowałem się jego wersją z przyjemnością. Elementy ramseyowskie występują na przykład w teorii liczb. Klasycznie jednak przede wszystkim w teorii grafów. Gdy chodzi o dokładne wyniki, możliwe obecnie w zasadzie tylko dla małych parametrów, to jednym z czołowych ekspertów jest Stanisław Radziszowski, i właśnie on gromadzi i edytuje tablice rekordów światowych (w tym absolutnych). Dawniej swoje tablice udostępniał on-line. Teraz ten dawny link mnie zawiódł, ale odnalazlem nowy. Tyle, że tablice trzeba sobie ściągnąć w pdf lub czymś podobnym:

                Small Ramsey numbers

Przypadki najmniejszych parametrów opisywałem dokładnie na Poland-L, a potem pod psem (czyli na pl.sci.matematyka). Gdyby było zainteresowanie (gdzie jest Artur P ?!?!!!), to bym przedstawił te początkowe wyniki teorii Ramseya także na buzzie. Dawniej w pewnym momencie zatrzymywałem się, bo dalej już pójść nie potrafiłem. Ciekawe, czy teraz ktoś na buzzie zaszedłby dalej. Nawet nie wiem, czy ktokolwiek kiedykolwiek uzyskał dalsze wyniki bez komputera. Zresztą można zastanawiać się także nad ekstra zgrabnym zastosowaniem komputerów. Rekordy jednak są wyśrubowane, bodajże wymagają olbrzymich danych, dotyczących grafów. Gdy Stanisław usłyszał, że zainteresowałęm się Ramseyem, to z miejsca przyjacielsko ofiarował mi swoje własne, przecież na pewno z trudem uzyskane, dane. Jednak nie miałem systemu komputerowego, który by obiecywał sukces w tak zaawansowanej konkurencji, więc jednak Stanisławowi głowy przesyłaniem mi danych nie zawracałem.

---

Żeby pisać przystępnie, będę rozpatrywał relację znajmości, zamiast abstrakcyjnej. Zakładam, że relacja znajomości jest symetryczna" - gdy Adam zna Ewę, to Ewa nie może zadzierać nosa, że nie zna Adama. Zakładam poniżej, że ludzie o których mówię albo znają się w obie strony, albo wcale.

Wśród 5 ludzi może się zdarzyć, że nie istnieje trójka, w której każdy zna każdego, ani nie istnieje trójka, w której nikt by nie znał nikogo innego - może nie być ani takiej trójki, ani takiej. Potraficie podać (wymyśleć fikcyjny) przykład?

Natomiast wśród dowolnych 6 ludzi zawsze istnieje trójka, w której każdy zna każdego, albo nikt nikogo innego. Ba, istnieją nawet zawsze 2 różne takie trójki (choć mogą być tego samego rodzaju).

Grupę ludzi, w której każdy zna każdego, nazywamy kliką; gdy nikt nikogo, to grupą obcych (w literaturze panuje brzydki, impotencki termin anty-klika). Tak więc wśród dowolnych 6 ludzi zawsze występuje 3-osobowa klika lub 3-osobowa grupa obcych.

Podobnie, wśród dowolnych 9 różnych ludzi zawsze występuje 3-osobowa klika lub 4-osobowa grupa obcych. Ogólnie nie jest tak dla 8 ludzi.

Itd. Czy ktoś się sfrustrował, że tak szybko te przykłady urwałem? To byłby dobry znak!

Wstęp do liczb zespolonych, Cz. 1

Spis rzeczy

• Wstęp


• Sprzężenie


• Część rzeczywista i część urojona liczby zespolonej


• Iloczyn samosprzężony


• Wzór Pitagorasa dla liczb zespolonych


• Dzielenie liczb zespolonych


• Moduł liczby zespolonej


• Nierówność trójkąta

WSTĘP

Niniejsza Część 1 jest kontynuacją Części 0, w której wprowadziłem - w stylu Gaussa - liczby zespolone, wraz z ich dodawaniem, odejmowaniem i mnożeniem. Poniżej omówione będzie pojęcie modułu (normy, wartości absolutnej) liczby zespolonej oraz operacja dzielenia liczb zespolonych.

Sprzężenie

W kontekście liczb zespolonych, sprzężeniem nazywamy symetrię płaszczyzny zespolonej wokół osi (zespolonych) liczb rzeczywistych [;t\cdot\mathbf 1;]. Formalnie, sprzężeniem  [;\bar z;]  liczby zespolonej  [;z := (a\ b);]  nazywamy liczbę:

[;(I)\qquad\qquad \bar z\ :=\ (a\,\ -\!b);]

Zespolone liczby rzeczywiste przechodzą przy sprzężeniu na siebie, a liczby urojone na przeciwne (są wymnażane przez -1):

• [;z;]  jest rzeczywiste  [;\Leftrightarrow\quad \bar z = z;];


• [;z;]  jest urojone  [;\Leftrightarrow\quad \bar z = -z;];

Sprzężenie jest inwolucją czyli ma własność:

        [;\bar{\bar z} = z;]

dla dowolnej liczby zespolonej  [;z;] - dwukrotne zastosowanie sprzężenia daje tożsamość czyli za wartość daje argument wyjściowy. Co więcej, liczba zespolona i jej sprzężenie są nierozróżnialne jak jednojajowe bliźniaki (tyle, że jeden jest prawo-, a drugi leworęczny), bowiem sprzężenie jest automorfizmem względem operacji arytmetycznych:

• [;\overline{v+w} = \bar v + \bar w;]


• [;\overline{v-w} = \bar v - \bar w;]


• [;\overline{-z} = -\bar z;]


• [;\overline{v\cdot w} = \bar v \cdot \bar w;]


• [;\overline{t\cdot z} = t\cdot \bar z;]
  

dla dowolnych liczb zespolonych  [;v\ w\ z\in\mathbf C;]  oraz  [;t\in\mathbf R;].  Wynika stąd, że dla dowolnego wielomianu  [;f;],  o współczynnikach zespolonych, zachodzi podobna równość:

        [;\overline{f(z)} = f(\bar z);]

dla dowolnej liczby zespolonej  [;z;];  w szczególności:

        [;\overline{z^2} = \bar z ^2;]

Część rzeczywista i część urojona liczby zespolonej

Niech  [;z:=(a\ b) = a+b\cdot\mathbf i;]  będzie liczbą zespoloną, gdzie  [;a\ b\in\mathbf R;]  są dowolnymi liczbami rzeczywistymi. Wtedy definiujemy część rzeczywistą  [;\rho(z);]  oraz  część urojoną  [;\iota(z);]  jak następuje:

• [;\rho(z) := a;]


• [;\iota(z) := b;]

Zatem:

• [;z = (\rho(z)\,\ \iota(z)) = \rho(z) + \iota(z)\cdot\mathbf i;]


• [;\bar z = (\rho(z)\,\ -\!\iota(z)) = \rho(z) - \iota(z)\cdot\mathbf i;]


• [;\rho(z) = \frac{z+\bar z}{2};]


• [;\iota(z) = \frac{z-\bar z}{2};]

Ostatnie dwa wzory oraz własności sprzężenia dają:

• [;\rho(v+w) = \rho(v)+\rho(w);]


• [;\rho(t\cdot z) = t\cdot\rho(z);]


• [;\iota(v+w) = \iota(v)+\iota(w);]


• [;\iota(t\cdot z) = t\cdot\iota(z);]

dla dowolnych liczb zespolonych  [;v\ w\ z\in\mathbf C;]  oraz rzeczywistego  [;t\in\mathbf R;].  Ponadto:

• [;\rho(\mathbf i\cdot z) = -\iota(z);]


• [;\iota(\mathbf i\cdot z) = \rho(z);]

dla dowolnego zespolonego  [;z;].

Iloczyn samosprzężony

Niech  [;z;]  oznacza dowolną liczbę zespoloną. Zajmijmy się iloczynem

        [;M(z) := z\cdot\bar z;]

Jest jasnym, że

        [;\overline{M(z)} = M(\bar z) = M(z);]

Z tego powodu nazywam    iloczynem samosprzężonym.

Policzmy  [;M(z);]  dla  [;z:=(a\ b);],  gdzie  [;a\ b\in\mathbf R;]  są dowolnymi liczbami rzeczywistymi. Wtedy:

        [;M(z) = (a^2+b^2\quad 0);]

Utożsamiając zespolone liczby rzeczywiste  [;(x\ 0);]  z odpowiadającymi im liczbami rzeczywistymi  [;x\in\mathbf R;],  możemy powiedzieć, że iloczyn samosprzężony jest zawsze nieujemną liczbą rzeczywistą. Jednak dla spokoju ducha i pedantycznej ścisłości wprowadźmy:

        [;\mathit M(z) := \rho(M(z));]

gdzie po lewej "M" napisane jest kursywą (nie szkodzi, że trudno to nowe "M" odróżnić od starego, nic strasznego się od tego nie stanie). Wtedy, już bez obaw, możemy napisać:

        [;\mathit M(z) \ge 0;]

przy czym

        [;\mathit M(z) = 0\quad\Leftrightarrow\quad z=\mathbf 0;]

co ma miejsce tylko dla  [;a=b=0;].

Jest oczywistym, prosto z definicji iloczynu samosprzężonego, że jest on multiplikatywny:

[;(II)\qquad\qquad M(w\cdot z) = M(w)\cdot M(z);]

dla dowolnych liczb zespolonych  [;w\ z\in\mathbf C;]. Dla  [;w:= (a\ b);]  oraz  [;z:=(c\ d);],  własność multiplikatywna tłumaczy się na tożsamość Fermata dla liczb rzeczywistych  [;a\ b\ c\ d\in\mathbf R;]:

        [;(a^2+b^2)\cdot(c^2+d^2) = (a\cdot c - b\cdot d)^2 + (a\cdot d + b\cdot c)^2;]

Można tę tożsamość dowieść mechanicznie wprost, bez wprowadzania liczb zespolonych, ale łatwiej w kontekście zespolonym. Co ważniejsze, tożsamość ta nabiera pewnego podstawowego znaczenia dzięki liczbom zespolonym, zamiast być błyskotliwym dziwolągiem nie wiadomo skąd.

PRZYKŁAD 0   Ponieważ:

        [;5 = 1^2 + 2^2 = 2^2+1^2;]
        [;13=2^2+3^2;]

to na mocy równości Fermata:

        [;5\cdot 13 = 4^2 + 7^2 = 1^2 + 8^2;]

KONIEC PRZYKŁADU

Zachodzi także własność multiplikatywna dla iloczynu liczby zespolonej  [;z;]  przez rzeczywistą  [;t;]:

[;(III)\qquad\qquad M(t\cdot z) = t^2\cdot M(z);]

co z łatwością można dowieść wprost; można też wprowadzić zespoloną liczbę rzeczywistą  [;\tau := (t\ 0);],  tak że  [;t = \rho(\tau);]  (oraz  [;\iota(\tau) = 0;]. Wtedy  [;M(\tau)=t^2;]. Stąd już [;(III);] wynika z [;(II);].

Wzór Pitagorasa dla liczb zespolonych

Niech  [;z\in\mathbf C;]  oraz  [;s\ t\in\mathbf R;].  Zdefiniujmy: [;v := s\cdot z;]  oraz  [;w:=t\cdot\mathbf i\cdot z;].  Zachodzi wtedy następująca wersja wzoru Pitagorasa:

        [;M(v)+M(w) = M(v+w) = M(v-w);]

Oznacza to, że kąty  [;v\mathbf 0w;]  oraz  [;v\mathbf 0(-w);]  są proste. Więcej o tym będzie poniżej, w sekcji Moduł liczby zespolonej.

Dzielenie liczb zespolonych

Niech  [;w\ z\in\mathbf C;]  będą dwoma dowolnymi liczbami zespolonymi, przy czym  [;w\ne\mathbf 0;]. Wtedy wiemy jak mnożyć liczby zespolone przez  [;\frac{1}{\mathit M(w)};],  gdyż ta ostatnia liczba jest dodatnią liczbą rzeczywistą. Dzięki temu iloraz  [;\frac{z}{w};]  możemy zdefiniować jak następuje:

        [;\frac{z}{w} := \frac{1}{\mathit M(w)}\cdot z\cdot\bar w;]

Zdefiniowaliśmy w ten sposób to, co w sensie powszechnym zasługuje na nazwę iloraz, gdyż zachodzi twierdzenie:

[;(II)\qquad\qquad \frac{z}{w}\cdot w = z;]

DOWÓD

    [;\frac{z}{w}\cdot w = \frac{1}{\mathit M(w)}\cdot z\cdot\bar w \cdot w
= \frac{1}{\mathit M(w)}\cdot z\cdot M(z) = z;]

KONIEC DOWODU

Moduł liczby zespolonej

Skoro iloczyn samosprzężony  [;\mathit M(z);]  jest nieujemną liczbą rzeczywistą, to dopuszcza arytmetyczny pierwiastek kwadratowy

        [;|z| := \surd\mathit M(z);]

zwany modułem albo normą albo wartością bezwzględną liczby zespolonej  [;z;]. Jest to euklidesowa odległość punktu  [;z;]  od  [;\mathbf 0;]:  gdy  [;z:=(a\ b);],  to

        [;|z| := \surd(a^2+b^2);]

Oczywiście:

        [;\mathit M(z) = |z|^2;]

Na moduł przenoszą się następująco odpowiednie własności iloczynu samosprzężonego:

• [;|v\cdot w| = |v|\cdot |w|;]


• [;|t\cdot z| = |t|\cdot |z|;]

dla dowolnych zespolonych  [;v\ w\ z\in\mathbf C;]  oraz rzeczywistego  [;t\in\mathbf R;].

Możemy obecnie wzór Pitagorasa dla liczb zespolonych zapisać w postaci bardziej tradycyjnej. Jak poprzednio, niech  [;z\in\mathbf C;]  oraz  [;s\ t\in\mathbf R;].  Zdefiniujmy: [;v := s\cdot z;]  oraz  [;w:=t\cdot\mathbf i\cdot z;].  Zachodzi wtedy następująca wersja wzoru Pitagorasa:

        [;|v|^2+|w|^2 = |v+w|^2 = |v-w|^2;]

Nierówność trójkąta

Z geometrii euklidesowej (kartezjańskiej) wiemy, że

        [;||v|-|w||\ \le\ |v+w|\ \le\ |v|+|w|;]

dla dowolnych liczb zespolonych  [;v\ w\in\mathbf C;]. Ponieważ  [;|-w|=|w|;],  to podobna nierówność zachodzi też dla różnicy:


        [;||v|-|w||\ \le\ |v-w|\ \le\ |v|+|w|;]

Wstęp do liczb zespolonych, Cz. 0

Spis rzeczy

• Wstęp


• Zbiór liczb zespolonych


• Dodawanie i działania liniowe na liczbach zespolonych


• Mnożenie liczb zespolonych

WSTĘP

Liczby zespolone występowały w matematyce na różnym stopniu dojrzałości chyba ze dwieście lub więcej lat (warto sprawdzić), nim ostatecznie Gauss zdefiniował je z pełną ścisłością. Poniżej powtórzę jego definicję (być może z dokładnością do detali lub wysłowienia). Zakładam znajomość ciała liczb rzeczywistych [;\mathbf R;].

W niniejszej Części 0 wprowadzam liczby zespolone, ich dodawanie, odejmowanie i mnożenie. Pojęcie modułu liczby zespolonej oraz dzielenie liczb zespolonych omówię w Części 1.

Zbiór liczb zespolonych

Ciało liczb zespolonych od strony mnogościowej definiuje się jako płaszczyznę kartezjańską:

[;(I)\qquad\qquad\qquad \mathbf C := \mathbf R^2;]

Pewne trzy punkty tej płaszczyźny, czyli pewne liczby zespolone, oznaczamy następująco:

• [;\mathbf 0 := (0\ 0);]


• [;\mathbf 1 := (1\ 0);]


• [;\mathbf i := (0\ 1);]

Liczby zespolone postaci [;(a\ 0);] nazywają się zespolonymi liczbami rzeczywistymi (lub po prostu rzeczywistymi, co jest uproszczeniem i nieszkodliwym niechlujstwem), a w praktyce (na przykład inżynieryjnej) bez najmniejszych kłopotów utożsamia się zespolone liczby rzeczywiste [;(a\ 0);] z liczbami rzeczywistymi [;a;].

Historycznie, i do dziś, liczby postaci [;(0\ b);] nazywane są liczbami urojonymi, co oddaje uczucie tajemniczości i magii, przeżywanej przez wczesnych algebraików i amatorów, gdy się wypuszczali na nowe tereny matematyki, gdy okrężne drogi "rzeczywiste" zastępowali cudownymi skrótami przez świat "urojony".

Dodawanie i działania liniowe na liczbach zespolonych

Dodawanie i odejmowanie liczb zespolonych definiuje się tak samo jak dla punktów (wektorow) płaszczyzny kartezjańskiej [;\mathbf R^2;]:

[;(II')\qquad\qquad (a\ b) + (c\ d) := (a\!+\!c\ \ b\!+\!d);]
[;(II')\qquad\qquad (a\ b) - (c\ d) := (a\!-\!c\ \ b\!-\!d);]

dla dowolnych  [;(a\ b)\ \,(c\ d)\ \in \mathbf C;].  W szczególności:

    [;\mathbf 0+z=z+\mathbf 0 = z-\mathbf 0 = z;]

dla dowolnego zespolonego  [;z\in\mathbf C;]. Dodawanie liczb zespolonych jest przemienne i łączne:

    [;v+w=w+v;]
    [;(v+w)+z=v+(w+z);]

dla dowolnych liczb zespolonych  [;v\ w\ z;].

Ponadto, jak w przestrzeniach liniowych, których przykładem jest [;\mathbf R^2;], definiujemy także mnożenie liczb rzeczywistych przez zespolone:

[;(III)\qquad\qquad t\cdot (a\ b) := (t\!\cdot\!a\ \,t\!\cdot\!b);]

dla dowolnych  [;t\in\mathbf R;] oraz [;(a\ b)\in\mathbf C;].  Stąd, dla dowolnych rzeczywistych  [;a\ b\in\mathbf R;], otrzymujemy jednoznaczny rozkład na tak zwaną część rzeczywistą i urojoną:

• [;(a\ b) = a\cdot\mathbf 1 + b\cdot\mathbf i;]


• [;(a\cdot\mathbf 1 + b\cdot\mathbf i) + (c\cdot\mathbf 1 + d\cdot\mathbf i) = (a+c)\cdot\mathbf 1 + (b+d)\cdot\mathbf i;]
  

Definiujemy także liczbę zespoloną  [;-\!z;]  przeciwną do danej liczby  [;z:=(a\ b)\in\mathbf C;]:

[;(IV)\qquad\qquad -\!z := (-1)\cdot z;]

czyli

[;(IV')\qquad\qquad -(a\ b) = (-a\ -\!b);]

Na przykład:

• [;-\!\mathbf 1 = (-\!1\ 0);]


• [;-\!\mathbf i = (0\ -\!1);]

Zachodzi oczywisty wzór:

        [;-z = \mathbf 0-z;]

dla dowolnego zespolonego [;z;].

UWAGA 0   W praktyce, zamiast  [;a\cdot\mathbf 1+b\cdot\mathbf i;]  piszemy nieco prościej: [;a+b\cdot\mathbf i;],  co przy danym opisie liczb zespolonych jest wygodnym, ale lekkim niechlujstwem. Wszystko jedno będziemy, jak wszyscy, używać zapisu prostszego, który zresztą przy innych wprowadzeniach liczb zespolonych jest w stu procentach czysty, nieskazitelny. Według prostszej umowy, wzór wcześniejszy na dodawanie można zapisać tak:

        [;(a + b\cdot\mathbf i) + (c + d\cdot\mathbf i) = (a+c) + (b+d)\cdot\mathbf i;]

Mnożenie liczb zespolonych

Dla liczb rzeczywistych  [;x;],  zawsze  [;x^2 \ge 0;].  Z tego powodu nie istnieje liczba rzeczywista  [;x;],  ktora byłaby rozwiązaniem równania  [;x^2 = -1;]. Skoro nie było takiej liczby rzeczywistej, to algebraicy pomagali kiedyś sobie, nie przejmując się przesadnie formalnościami, wprowadzając liczbę "urojoną"  [;\mathbf i;], której kwadrat dawał  [;-1;].  Formalna definicja mnożenia dowolnych dwóch liczb zespolonych jest następująca:

[;(V)\qquad\qquad (a\ b)\cdot(c\ d) := (a\cdot c - b\cdot d\quad a\cdot d + b\cdot c);]

lub bardziej wizualnie:

[;(V')\qquad (a+b\cdot\mathbf i)\cdot(c+d\cdot\mathbf i) := (a\cdot c - b\cdot d)\ +\ (a\cdot d + b\cdot c)\cdot\mathbf i;]

dla dowolnych liczb zespolonych  [;(a\ b)\ \ (c\ d);].  W szczególności:

[;(-)\qquad\qquad\qquad\mathbf i^2 = -\mathbf 1;]

ponadto zachodzą ogólne równości:

• [;\mathbf 1\cdot z = z\cdot\mathbf 1 = z;]


• [;w\cdot z=z\cdot w;]


• [;(u\cdot w)\cdot z=u\cdot(w\cdot z);]


• [;(u+w)\cdot z=z\cdot(u+w) = u\cdot z + w\cdot z;]

dla dowolnych liczb zespolonych  [;u\ w\ z\in\mathbf C;].  Zauważmy też, że mnożenie liczb zespolonych przez rzeczywiste pokrywa się z mnożeniem liczb zespolonych przez odpowiednie zespolone liczby rzeczywiste:

[;(\bullet)\qquad\qquad t\cdot z = (t\cdot\mathbf 1)\cdot z;]

dla dowolnej liczby rzeczywistej [;t;] oraz zespolonej [;z;].