• piątek, 21 lipca 2017 r.

Co to jest złożoność problemu?

Każdy problem, którego rozwiązanie wymaga obliczeń charakteryzuje się tzw złożonością. Złożoność to nie trudność zrozumienia problemu lub metody rozwiązania. Złożoność to ilość informacji potrzebnej do opisania problemu lub ilość arytmetycznych operacji wymaganych przez metodę rozwiązania .

Na przykład obliczenie aerodynamiki samolotu jest dość złożone ale superkomputery radzą sobie z tym problemem w ciągu kilku minut lub godzin. Są jednak pozornie proste problemy, które maja złożoność wykładniczą .Wymagają one tak dużej ilości operacji, że możemy tylko rozwiązywać małe wersje. Duże wersje wymagałyby na przykład miliona lat obliczeń na szybkim komputerze co jest absurdalnym wymogiem.

 

Aby zilustrować czytelnikowi Racjonalisty czym jest wykładnicza złożoność opiszę dokładnie prosty problem.

Mamy bardzo duży kwadratowy kawałek papieru o grubości jednego milimetra. Składamy ten papier we dwoje i otrzymujemy podwójna warstwę o grubości 2 milimetrów. Składamy znów ten podwójny zwitek i otrzymujemy papier złożony z 4 warstw. Powtarzamy tę operację 50 razy. Pytanie jak gruby jest końcowy zwitek? Ludzie na ogol oceniają to na grubość cegły a bardziej odważni na grubość jednego metra.

Zróbmy elementarne obliczenie, aby poznać prawdę.

Po 50 złożeniach papierowy zwitek ma grubość 2 do potęgi 50 milimetrów, bo grubość podwaja się z każdym złożeniem.

Zamieńmy 2 do potęgi 50 na potęgę liczby 10 .

2 do potęgi 10 to jest około 1000 czyli 10 do potęgi 3.

Czyli 2 do potęgi 50 jest równe około 10 do potęgi 15 mm.

Zamieńmy milimetry na kilometry;1 kilometr to milion milimetrów. Dzielimy 10 do 15 przez 10 do 6.

Rezultatem jest 10 do potęgi 9 kilometrów (miliard).

 

Jeśli pamiętam z astronomii dystans Ziemi do Słońca to jest około 150 milionów kilometrów. Miliard jest około sześć razy większy od 150 milionów. Czyli nasz zwitek papieru byłby równy sześciokrotnej odległości Ziemi od Słońca. A nie grubości cegły. Teraz czytelnik chwyci intuicyjnie jak złożone są problemy wykładnicze i dlaczego są nierozwiązywalne.

Ten prosty problem ilustruje też fakt, że nasza intuicja jest bardzo zawodna kiedy mamy do czynienia ze światem atomów lub galaktyk. Tylko „ta cholerna matma” pozwala nam na zrozumienie dużej ilości problemów które nas otaczają. Myślę, że ten komentarz usprawiedliwia tytuł eseju.

Janusz KowalikJanusz Kowalik jest emerytowanym profesorem matematyki i informatyki na Washington State University oraz byłym kierownikiem organizacji badań informatyki w firmie lotniczej Boeing Company w Seattle. Adres internetowy Janusza: j.kowalik@comcast.net

Podobne materiały

63 komentarze

  1. Piotr Napierała
    Piotr Napierała
    6 czerwca 2016 at 10:03 - odpowiedz

    „…Tylko „ta cholerna matma” pozwala nam na zrozumienie dużej ilości problemów które nas otaczają…” pewnie ale równie często ściślaki nie rozumieją świata ludzi, myslą, że polityka działa jak fizyka, a geopolityka jak matma, i tu błąd za błędem

    • Jacek Tabisz
      Jacek Tabisz
      6 czerwca 2016 at 10:21 - odpowiedz

      Obserwacje statystyczne mogą wiele powiedzieć o działaniach mas ludzkich. W niektórych wypadkach nie ma metodologii obliczeń lub (i) obliczenia są bardzo złożone. Ale przypuszczam, że można stworzyć modele statystyczne dotyczące wzrostu preferencji populistycznych w danej grupie osób, oraz modele dotyczące możliwych zachowań. Biznes posługuje się różnymi tego typu modelami preferencji konsumenckich i są one bardziej niezawodne niż refleksja historyczna.

      • Piotr Napierała
        Piotr Napierała
        6 czerwca 2016 at 10:38 - odpowiedz

        po raz setny powtarzam, że statystyki się nie czepiam tylko uproszczen czegośc co można by nazwać matematycznym światopoglądem

        • Jacek Tabisz
          Jacek Tabisz
          6 czerwca 2016 at 10:44 - odpowiedz

          Chyba wszyscy zwrócili uwagę, że chodziło o statystykę.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 13:36

            nie zwrócili uwagi, lecz błędnie założyli i nie wszyscy tylko ci ostatnio na mnie cięci z innych powodów : )

          • Jacek Tabisz
            Jacek Tabisz
            6 czerwca 2016 at 14:21

            Moim zdaniem rozmawiałeś na zasadzie „bo tak” i zlekceważyłeś wiele solidnych argumentów.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:23

            dyskusja w 75% toczyła się obok problemu jaki chciałem przedyskutować

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:27

            ty dyskutujesz na zasadzie bo tak i przypisujesz to innym typowy mechanizm psychologiczny

      • Piotr Napierała
        Piotr Napierała
        6 czerwca 2016 at 10:39 - odpowiedz

        „…modele dotyczące możliwych zachowań…” – w wielkim przybliżeniu i to dzięki obserwacji bardziej niż statystyce sensu stricte

        • Jacek Tabisz
          Jacek Tabisz
          6 czerwca 2016 at 10:44 - odpowiedz

          Ale obserwacja bez analizy danych jest bezwartościowa. Analiza nie oparta na żadnej metodologii jest tylko wyrazem gustu i poglądów obserwatora.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 13:36

            wszystko ok, tylko trzeba wiedzieć, że każda analiza jest niedoskonała inaczej wychodzi uczone głupstwo

          • Jacek Tabisz
            Jacek Tabisz
            6 czerwca 2016 at 14:22

            Z Twojego artykułu o „matematycznych osłach” wynikało coś innego. Stąd oburzenie komentujących

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:22

            wcale nie, po prostu z moich komentarzy wynikł pewien chaos, w artykule nie uderzam w statystykę

    • Lucyan
      7 czerwca 2016 at 03:33 - odpowiedz

      Napierała juz sobie zaczyna sam zaprzeczac, i to w ciagu kilku dni. Przed chwila napisał, ze Armia X ma wiecej broni Y niz Armia Z. Wiec Armia Z musi liczyc na Armie U, w celu wyrownania sił. Jak by Pan PN doszedł do tych wnioskow bez matematyki, a własciwie bez prostej arytmetyki? Na intuicje?
      Poza tym sam wysnuwa wnioski na podstawie prosciutkich wyliczen, a oskarża „matematykow” o upraszczanie problemow.

  2. Benbenek
    6 czerwca 2016 at 10:06 - odpowiedz

    Dwa przykłady i dwa jednocześnie poniekąd przeczące postawionej tezie. Poniekąd bo próba praktyczna rozwiązania problemu jest łatwiejsza niż model. Złożoność modelu nieraz utrudnia rozwiązanie zamiast go ułatwiać.
    W przypadku pierwszym jeśli chodzi o skrzydło to do dziś trwa spór o to co generuje siłę nośną. Czyli uwaga istnieją dwa różne modele. Jeden wynikający z prawa Bernoulliego a drugi da się sprowadzić wprost do praw Newtona i efektu Coandy. Dziś ten drugi model zaczyna wypierać ten pierwszy. Chociaż wiele starszych podręczników nadal opisuje zagadnienie na podstawie prawa Berboulliego i co więcej budowano samoloty przez dziesięciolecia modelując je zgodnie z tymi prawami.
    W drugim przypadku każde dziecko wie że nie można złożyć papieru więcej niż 6-7 razy. Gdzie to 12 to podobno mistrzostwo świata. Dlatego więc rozważania o 50 razach złożenia papieru są „modelowym” przykładem złego modelu. Złego bo pomijającego właściwości materiałowe koncentrującego się za to na teoretycznym wyidealizowaniu.
    W jednym i w drugim przykładzie pokazano, że matematyczne modele mogą dawać wyniki nieistotne lub przypadkowo tylko zbieżne ze sobą. Może przypadkowo to złe słowo bo nie rządzi tym przypadek a spójne prawa fizyki a modele matematyczne je jedynie opisują i dlatego dają

    • Piotr Napierała
      Piotr Napierała
      6 czerwca 2016 at 10:14 - odpowiedz

      „…Dlatego więc rozważania o 50 razach złożenia papieru są „modelowym” przykładem złego modelu. Złego bo pomijającego właściwości materiałowe koncentrującego się za to na teoretycznym wyidealizowaniu…” otóż to, dlatego matma w realnym świecie czesto ssie

      • Jacek Tabisz
        Jacek Tabisz
        6 czerwca 2016 at 11:08 - odpowiedz

        Przyrost wykładniczy często pojawia się w rzeczywistości. Bez niego nie byłoby ewolucji naturalnej (szybkie zasiedlanie środowisk i rywalizacja o zasoby), nie byłoby gwiazd (reakcja łańcuchowa w gwiazdach), nie byłoby krachów giełdowych, wielkich epidemii, migracji ludów etc.

        • Piotr Napierała
          Piotr Napierała
          6 czerwca 2016 at 13:35 - odpowiedz

          bez jakiegoś wzorka nie byłoby krachu? To jest wąłśnie matematyczne spustoszenie myślenia… to wzorek stara się opisać krachy itd które istnieją i bez łaski matematyka

          • Jacek Tabisz
            Jacek Tabisz
            6 czerwca 2016 at 14:20

            To jest próba przewidzenia. Dygresje historyczne stanowią tu słabsze narzędzie.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:24

            dygresje??? Czy ty wiesz co to są dygresje? To jest naskzicowanie planu do porównań. Gdybyś stuiował normalną historię a nie hist sztuki widziałbyś czemu służą tak pogardzane przez Ciebie dygresje… żenada Jacku żenada.

          • Jacek Tabisz
            Jacek Tabisz
            6 czerwca 2016 at 14:27

            Ja również proszę cię o to samo, co Tatajarek w poniższym komentarzu:

            „nie mam obsesji natymatematycznej po porstu wiem jak sciślaki upraszczają rzeczywistość i wszytsko mylą w polityce”
            To może niech Pan o tym napisze artykuł?
            W tamtym feralnym artykule matematycznym brakowało przykładów.
            Były jakieś nieudolne próby zdyskredytowania brzytwy Ockhama, oraz wspomnienia
            jakichś systemów filozoficznych, jak rozumiem z czasów popularnosci mechanicyzmu. Od tamtego czasu matematyka jak i matematyczne myslenie
            znacznie się zmieniły (jak Pan to ujmuje, było to „dawno, dawno”).
            Rzuciłby Pan garścią świeżych przykładów, np. wziąć kilku współczesnych polityków
            z wykształceniem humanistycznym, oraz kilku z matematycznym i pokazać
            konkretne przypadki, w których humaniści podejmowali salomonowo celne decyzje, a ścisłowcy – ograniczone determinizmem biedaki – zachowywali się jak wspomniane przez Pana osły.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:29

            nikt nie będzie mi mówił o czym mam pisać. może napiszę może nie. To co chciałem napisać napisałem. Mam pracę 40 h i szkoda mi czasu na przekomarzania pisałem o La Mettriem i Le Brecie, sami sobie odpowieddzie czy wy też stosujecie takie uproszczenia – moim zdaniem JAK NAJBARDZIEJ i jeszcze znieważacie humanistów tfu.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:32

            zresztą o jednym uproszczeniu pisałeś ty sam – Obama Prezydent Putin też USA władza Rosja władza 1 rząd 1 rząd ergo putin knuje tyle co obama. tyowe myslenie matematyczne bez brania pod uwage kultury . Ty sam to widzisz, ale pieścisz w duszy słowo matma i chcesz mi dokopać za to, ze nie popieram Izraela bezwarunkowo, idź sobie ujadać na kogoś innego.

          • Piotr Napierała
            Piotr Napierała
            6 czerwca 2016 at 14:36

            zreszta jedne przykład dałem; najlepsza matma na swiecie na MIT a tolerują bajkopisarza Chomsky’ego i jeszcze go wyznają, sami są za głupi by zobaczyć co to za bajkopisarz

          • darekpiotrek
            6 czerwca 2016 at 21:35

            Jackowi Tabiszowi dużo łatwiej jest być odważnym, bo jest artystą, zna matematykę i sobie to chwali. Matematyka dodaje odwagi, wprawdzie nie rozwiązuje wszystkich problemów ale czy są jakieś szczególne powodu by sądzić, że niektóre problemy z istoty swojej są matematycznie nieopisywalne w ogóle(?) to pobożne życzenie, jakich sporo i w tym względzie fizyka nie jest jakoś specjalnie uprzywilejowana czy wyłączona poza nawias. Dzisiaj „znamy” teorie; prawdopodobieństwa, podobieństwa i wiele innych, zakładając, że kiedyś ich nie było, i że te teorie powstały bo było na nie zapotrzebowanie, to być może – a nawet na pewno jeśli nas coś nie zje po drodze – za 50, 500 lat ludzie nadal będą używać matematyki, będą kolejne nowe teorie i nowe zastosowania. Jeśli nauczać matematyki na wszystkich kierunkach to prawdopodobnie stosowalność matematyki + odkrycia nowych teorii = pożytek, wzrośnie wykładniczo

          • Rafał Gardian
            Rafał Gardian
            7 czerwca 2016 at 01:29

            Oczywiście, że byłby. Nie byłoby jednak jego dobrego opisu.

        • Tomek Świątkowski
          7 czerwca 2016 at 09:31 - odpowiedz

          Przyrost wykładniczy jest teoretycznym modelem, ale w praktyce zazwyczaj nie zadziała (wymaga znaczących korekt) – dlatego np. piramidy finansowe są pospolitym oszustwem, choć matematycznie wszystko się zgadza.
          Można to łatwo przećwiczyć np. licząc swoich przodków: mam 2 rodziców, 4 dziadków, 8 pradziadków itd. Proste obliczenie pokazuje, że 30 pokoleń wstecz miałem już ponad …miliard przodków. Tymczasem cała Ziemia liczyła wtedy (ok 1000r.n.e.) ok 300 mln mieszkańców.

          • Piotr Napierała
            Piotr Napierała
            7 czerwca 2016 at 09:40

            dokładnie znowu co ma matma do świata? trochę…

          • Tomek Świątkowski
            7 czerwca 2016 at 10:03

            ma wiele, ale proste wzory zazwyczaj są nie do zastosowania ot tak i wymagają skomplikowanych korekt
            dlatego np. krzywa balistyczna nie jest prostą parabolą (jaka wynika z praw Newtona) bo musi uwzględnić opory powietrza
            niestety w przypadku wielu zagadnień ilość wymaganych korekt rośnie …wykładniczo
            🙂

          • Jacek Tabisz
            Jacek Tabisz
            7 czerwca 2016 at 10:35

            W matematyce też możemy poddać przyrost wykładniczy modulacjom. Może być też przyrost wykładniczy o znacznie wolniejszym charakterze. Globalne ocieplenie to przyrost wykładniczy efektu gazów cieplarnianych w atmosferze nałożony na dawną, jeszcze dominującą funkcję.

          • Piotr Napierała
            Piotr Napierała
            7 czerwca 2016 at 11:44

            taaaa, a jak nie wiemy jak będzie przebiegał dokładnie e ciepl., tak nie wiemy. Matma najlepiej wygląda na papierze, tam nie musi się mierzyć z rzeczywistością : )

          • darekpiotrek
            7 czerwca 2016 at 22:28

            TŚ@ Opór powietrza jest związany również z panem Newtonem,, .”te” poprawki wynikają z pełniejszego zapisu równania ruchu X(t);Y(t);Z(t). czyli większej ilości informacji (niedawno wklejałem fragment z książki Hartoga, o równaniach niejednorodnych i o zmiennych własnościach, można o tym poczytać bo to jest dokładnie na ten temat)
            JT@ „W matematyce też możemy poddać przyrost wykładniczy modulacjom.” Jak się ma do dyspozycji worek wielu różnych funkcji, i dodatkowo jeśli wie się co z nimi zrobić to cała reszta ogranicza się do kreacji i badań: Pisząc równania nadajemy znaczeń,.Ktoś kto zna „Matematyczny alfabet od A do Z” i jest kreatywny z potrafi uszyć linijkę lub dwie czegoś co niesie bardzo dużo precyzyjnych informacji: – skomplikowanej geometrii.
            PN@ Z rzeczywistością mierzą się: metrologia, metrolog i matematyk, a Ty wciąż krytykujesz matme.. 🙂

    • Jacek Tabisz
      Jacek Tabisz
      6 czerwca 2016 at 10:31 - odpowiedz

      Ja dodałem te przykłady do tego artykułu, a nie Janusz. Pomyślałem, że ktoś zainteresowany może się przy okazji czegoś dowiedzieć o Słońcu czy badaniu aerodynamiki. Oczywiście modele aerodynamiki czy gwiazd nie byłyby możliwe bez matematyki. Tym bardziej nie byłaby możliwa analiza uzyskiwanych wyników.

    • Rafał Gardian
      Rafał Gardian
      7 czerwca 2016 at 01:47 - odpowiedz

      „Dlatego więc rozważania o 50 razach złożenia papieru są „modelowym” przykładem złego modelu.” Przecież to oczywiste, że nie chodzi tu o żadne modelowanie, tylko o pokazanie czym jest przyrost wykładniczy. Przykład Janusza jak najbardziej adekwatny.

  3. darekpiotrek
    6 czerwca 2016 at 15:14 - odpowiedz

    Wiele błędnych wniosków i nieporozumień, mówiąc najogólniej, wynika z „płaskiego” pojmowania fizyki. Wiele razy spotkałem się z czymś takim. Ludziom często wydaje się że np parametry fizyczne są liniowo zależne od wymiarów przestrzennych. Niestety przyroda wcale tak nie działa – prawie zawsze wszystko jest inne. Nie bez przyczyny lina stalowa dla zachowania warunku samonośności nie może być dłuższa niż wartość graniczna; budowlańcy wiedzą że piramida kamienna nie może być wyższa niż ściśle określona wysokość; z tego samego powodu człowiek ma wzrost 1,8 m a nie np 5 m; dlatego upadło wiele bzdurnych i niekompetentnych teorii na temat jakie to wielkie gady niegdyś BIEGAŁY po naszej planecie. Wspominam o tym zainspirowany tą aerodynamiką. Mechanika płynów – bo tak naprawdę o tym jest mowa – jest jednym z dobitnych przypadków pokazującym jak zwodnicze i bałamutne bywa – dla jednych intuicyjne dla innych wręcz przeciwnie – pojmowanie rzeczywistości. Mechanicy płynów dowiadują sie o tym kiedy np w aerodynamicznych tunelach badają modele wykonany w skali – dowiadują się, że przez zmianę wielkości obiektu wszystko bierze w łeb. Oczywiście dzięki temu że nauki ścisłe rozwijane są przez co cwańsze jednostki ludzkie, dzisiaj możemy badać model 1000 razy mniejszy i wyniki tych badań z dobrym skutkiem przekładać na konstrukcje rzeczywiste. Służy temu teoria podobieństwa, która już samą nazwą sugeruje, że w przyrodzie możemy mówić o podobieństwach a prawie nigdy o identyczności. Wspominam o tym żeby uwypuklić to o czym kiedyś pisał pan Tabisz: jak ważnym czynnikiem jest perspektywa i jakie kolosalne skutki może mieć brak perspektywy czy to kosmicznej czy mikroskopowej.

  4. Janusz
    Janusz
    6 czerwca 2016 at 20:40 - odpowiedz

    Matematyka jest narzedziem ktore stosuje sie do duzej ilosci problemow natury ale nie wszystkich. Statystyka to galaz matematyki ktora jest przedluzeniem do oceny pokrewnych problemow dajacych sie opisac liczbowo.
    Matematyka moze ulatwic zrozumienie polityki ale nie zastepuje metod politologii. To chyba jest jasne nawet przedszkolakom.
    Mowiac prosto. Kazdy klucz otwiera tylko drzwi do ktorych jest odpowiednio dopasowany.Nauka stwarza rozne klucze do roznych problemow. Ktos kto sadzi ze jeden klucz otwiera wszystkie dzwi jest jak mechanik ktory uwaza ze jedyne potrzebne narzedzie to mlotek.
    Przyklad skladania papieru ilustruje jak szybko rosnie wykladnicza funkcja. To oczywiscie nie jest praktycznym problemmem.Szokiem jest odkrycie jak szybko wzrasta wykladicza funkcja .
    Jesli chodzi o samolot to lecac samolotem nie musimy rozumiec jak zostal policzony i zaprojektowany ale dobrze jest miec zaufanie do ludzi ktorzy to poprawnie zrobili.
    Wydaje mi sie ze czlowiek inteligientny nie musi i nie moze rozumiec wszystkich nauk i trechnologii ale ma intuicyjne wyczucie jak otaczajacy swiat dziala.
    Na przyklad nie musimy rozumiec matmy teorii wzglednosci ale czlowiek swiatly wie ze czas nie jest absolutny we wszystkich ukladach . Taki artysta i poeta jak Jacek nie musi nie moze studiowac matematyki ale stara sie intuicyjnie zrozumiec np teorie strun lub ewolucje .Ja to nazywam intelektualna odwaga.
    Pewien chlop poszedl do ogrodu zoologicznego i zobaczyl zyrafe, Splunal i powiedzial Takiego zwierzaka nie ma.Nie chcial zrozumiec ze swiat jest wiekszy niz jego podworko z kurami ,krowami i konmi.
    Dlatego uwazam ze powinnismy miec otwarty umysl na
    wszystkie klucze ktore cos tlumacza.Dobrze byc kompetentnym kompozytorem muzyki ale to nie wyklucza pewnej wiedzy o Aleksandrze Wielkim i Albercie
    Eisteinie . Im wiekszy horyzont tym pelniejsze zycie .Nie powinnismy odrzucac niczego co pomaga rozumiec rzeczywistosc.
    Nie tylko klucz ale i wytrych jest dobry jesli cos otwiera.

    • Tomek Świątkowski
      7 czerwca 2016 at 09:38 - odpowiedz

      Fajnym modelem przyrostu wykładniczego jest legenda o perskim królu, który chciał nagrodzić wynalazcę szachów. Wynalazca zaproponował, aby król na pierwsze pole szachownicy położył ziarenko pszenicy, na drugie 2, na trzecie 4 itd. Król ucieszony, że się tanio wywiąże z obietnicy przystał na to, ale szybko się okazało, że spichrze całego królestwa nie posiadają wystarczających ilości pszenicy by wywiązać się z królewskiego zobowiązania.

  5. Janusz
    Janusz
    6 czerwca 2016 at 22:18 - odpowiedz

    Kilka slow o kryptografii.
    Nie mozemy powiedziec ze dzieki matematykom Alianci wygrali druga wojne. Ale dzieki polskim i angielskim matematykom udalo sie zlamanie niemieckiego wojskowego szyfru Enigmy co powaznie ulatwilo lotnicza obrone Anglii w 1940 i 41 roku oraz wygranie morskiej bitwy o Atlantyk co bylo konieczne do utrzymania dostaw militarnych i ekonomicznych odizolowanej Wielkiej Brytanii przez niemicka Kriegsmarine .
    Jednym z tych ludzi byl ojciec teoretycznej informatyki Alan Turing.
    Szyfrowanie tajnych wiadomosci bylo juz uzywane w starozytnosci . Kazda metoda szyfrowania miala dwa klucze.Jeden do szyfrowania i jeden do odczytania wiadomosci. Mialo to powazna wade bo trzeba bylo przekazac metode czytania tej stronie ktora miala odczytac wiadomosc.W latach 1970tych trzech informatykow (Izraelita i dwoch Amerykanow) stworzyli metode ktora nie wymaga ryzykownego przekazania klucza do odczytania zaszyfrowanej wiadomosci.
    Metoda jest znana jako „metoda publicznego klucza”
    i jest stosowana we wszystkich systemach kryptografii militarnej i bankowej.
    Wyobrazmy sobie grupe instytucji ktore chca wymieniac tajne wiadomosci. Kazda z nich ustala jeden wlasny klucz do szyfrowania i odwrotny klucz do odczytania wiadomosci.
    Klucz do szyfrowania jest opublikowany np w Internecie a klucz do odczytania jest scisle tajny.
    Jesli instytucja A chce wyslac tajna wiadomosc do B to
    uzywa opublikowanego klucza instytucji A i wysyla wiadomosc do A. Tylko A ma odwrotny klucz. nikt inny nie moze odczytac szyfru nawet jesli przechwyci wiadomosc.
    Zasada jest genialnie prosta.Szczegoly ktore utrudniaja zlamanie kodu sa dosc skomplikowane i wymagaja wyzszej szkoly jazdy konno. Ale czytelnik Racjonalisty
    poznal czytajac komentarz zasade i wie o co chodzi w metodzie publicznego klucza.Mozna udowodnic ze zlamanie kodu tej metody nie jest praktycznie
    mozliwe. Slaby punkt to absolutna koniecznosc tajemnicy
    klucza odczytujacego.

    • Rafał Gardian
      Rafał Gardian
      7 czerwca 2016 at 02:16 - odpowiedz

      Złamanie kodu jest praktycznie niemożliwe, póki ktoś nie odkryje (jeśli ona istnieje) reguły rozmieszczenia liczb pierwszych. Wtedy będzie (nie)ciekawie 😉

  6. Rafał Gardian
    Rafał Gardian
    7 czerwca 2016 at 01:52 - odpowiedz

    @ Piotr”zreszta jedne przykład dałem; najlepsza matma na swiecie na MIT a tolerują bajkopisarza Chomsky’ego” Chomsky opowiada polityczne kretynizmy, ale jest światowym klasą lingwistą, dlatego go tolerują. Zresztą nie powiesz mi, że podobnych marksistowskich profesorków nie ma na licznych humanistycznych wydziałach uniwersytetów.

  7. Rafał Gardian
    Rafał Gardian
    7 czerwca 2016 at 01:54 - odpowiedz

    „wszystko ok, tylko trzeba wiedzieć, że każda analiza jest niedoskonała inaczej wychodzi uczone głupstwo” ale to właśnie matematycy określają jak niedoskonała jest dana analiza. Więc jak najbardziej zdają sobie z tego sprawę.

  8. Janusz
    Janusz
    7 czerwca 2016 at 03:36 - odpowiedz

    Rafale
    Jesli ktos w przyszlosci skonstruuje szybka metode na znalezienie dwoch liczb pierwszych p,r majac m=pr to trzeba bedzie zmienic algorytm szyfrowania. Bedzie to bardzo ciekawe bo
    mamy ciagly postep wiedzy i naukowcy kochaja nowe wyzwania a nie zastoj.
    Tomku.
    Nic w tym zdroznego aby pomagac bogu.
    Bog ma czasem zle pomysly np zabij nowa zone jesli sie okaze ze nie jest dziewica w noc poslubna.
    To nie jest alegoria ani przenosnia.To jest nakaz.
    Ja i Ty tak by nie zrobili .A wiec bog moze sie czegos od nas nauczyc.Nauka to nie wstyd.
    Jak mowia Rosjanie
    „nauka diengi stoit” a ja ofiaruje moje rady bogu za darmo. Krytyka tego daru jest niesprawiedliwa .
    Gwalci zasade Chrzescijanska wdziecznosci za rade.

    • Jacek Tabisz
      Jacek Tabisz
      7 czerwca 2016 at 04:23 - odpowiedz

      „Doradca Boga” – zabawne i dobrze powiedziane.

    • Tomek Świątkowski
      7 czerwca 2016 at 09:48 - odpowiedz

      Chyba przeniosłeś tutaj wątek z innej dyskusji
      🙂
      Dla ateisty „bóg” jest tylko awatarem ludzkich idei – niczym więcej.
      Problem w tym, że nie da się formułować i uzasadniać imperatywów moralnych bez takiego „aksjomatu” jak Bóg (osobowy absolut) który arbitralnie narzuci jakieś fundamentalne wartości. Na przykład (dla humanizmu) – człowiek.
      A bez takiego fundamentu nie da się niczego (żadnego systemu etycznego) zbudować.

      • Piotr Napierała
        Piotr Napierała
        7 czerwca 2016 at 12:09 - odpowiedz

        Nie chciałbyś być u nas autorem?

        • Tomek Świątkowski
          8 czerwca 2016 at 09:57 - odpowiedz

          do przemyślenia – dzięki za propozycję
          już wcześniej Jacek składał mi taką propozycję
          mam wrażenie, że tutejsze środowisko powoli dojrzewa do zaakceptowania takiego pluralizmu
          🙂
          ale jeden z autorów (nie ujawnię kto, ale wysoko stał w twoim rankingu) konsekwentnie usuwa każdy mój głos polemiczny (przypuszczam, że nawet nie czytając)

          • Jacek Tabisz
            Jacek Tabisz
            8 czerwca 2016 at 10:00

            Ja nie usuwam głosów polemicznych. Janusz, Krzysztof, Alicja, Rafał, Piotr Browarski nie mają takich możliwości, chyba że czasem pod swoimi artykułami. Ma je oprócz mnie Kaja, Grzegorz, Piotr Napierała. Moja propozycja pisania wobec Tomka Świątkowskiego padła już dawniej, z tym że dodałbym temu jakiś podtytuł – „krytycznym okiem protestanta”, żeby Tomkowi nie było głupio, że jest wprost związany z moimi Bezbożnymi Pogadankami itp.

          • Tomek Świątkowski
            8 czerwca 2016 at 11:30

            Myślałem, że każdy autor ma uprawnienia do dowolnego moderowania dyskusji pod swoimi własnymi tekstami. Na szczęście to chyba jest jednostkowy problem i dotyczy niezbyt płodnego (przynajmniej na tym portalu) autora.

  9. Janusz
    Janusz
    7 czerwca 2016 at 04:34 - odpowiedz

    Wydaje mi sie ze te dyskusje w Racjonaliscie swiadcza ze jest duzo ludzi w Polsce intelektualnie zywych. Racja jest mniej wazna niz zainteresowanie .Racje zawsze mozna poprawic ale intelektualny bezruch to koniec rozwoju czlowieka.
    Dyskusje pokazaly duza roznorodnosc stylu i zawartosci.
    Spektrum jest szerokie, od glebokich obserwacji do bezwartoseciowych wyznan typu:
    jedni mowia tak a drudzy inaczej
    dokladnie
    no wlasnie
    zastapmy bezbozna medycyne macierzynstwa na bocianologie.Jest ekonomiczna,bezgrzeszna i bezkrwawa.
    Jurek jako dentysta nie moze mowic o polityce bo dentystyka to najgorsza baza do prawidlowego myslenia o Putinie lub IS.
    Auschwitz to pikus w porownaniu z bomba wodorowa
    nie jestem antysemita ale Zydow trzeba usadzic aby nie rozrabiali
    Polska dla Polakow a ziemia dla ziemnakow
    tylko lewacy uzywali gilotyne
    Swiat ma tylko 4000 lat .Precz ze scislakami i ich brednia o 13.8 ,miliardach lat .

  10. Janusz
    Janusz
    7 czerwca 2016 at 09:37 - odpowiedz

    Jacku
    My zwykli ludzie mamy wielkie doswiadczenia zdobyte w ciagu kilku tysiecy lat w rozroznireniu co jest dobre a co jest zle. Probpowalismy wiele metod i sposobow zycie .Mielismy sukcesy i katasstrofy. Tak ciezko wypracowana cwiedza i doswiadczenie jest niezwykle cenne.
    Jahwe nie musi sie wstydzic aby nauczyc sie od ludzi.
    To nic nie kosztuje i moze byc pozyteczne.
    Ja bylbym dumny bedac w ekipie doradcow.To bylby moj drugi dobry uczynek. Moj pierwszy byl w szkole kiedy katecheta na lekcji religii powiedzial: kowalik ja przez Ciebie pojde do nieba .Bo ty jestes wyjatkowy gagatek z tymi pytaniami.

    • Tomek Świątkowski
      7 czerwca 2016 at 09:56 - odpowiedz

      my nie rozróżniamy, co jest dobre lub złe – to złudzenie (urojenie)
      my o tym arbitralnie decydujemy
      .
      nie ma w przyrodzie dobra i zła, które możemy obiektywnie rozpoznawać

      • Piotr Napierała
        Piotr Napierała
        7 czerwca 2016 at 10:02 - odpowiedz

        w ogóle nie ma dobra i zła są tylko szkodliwe i dobroczynne skutki działań

        • Tomek Świątkowski
          7 czerwca 2016 at 10:07 - odpowiedz

          no ale to są w praktyce synonimy: zło=szkodliwość, dobro=dobroczynność

  11. Janusz
    Janusz
    7 czerwca 2016 at 09:50 - odpowiedz

    Obecni historycy oceniaja ze zlamanir Enigmy skrocilo wojne w Europie o okolo 2 lata.
    Moge wspomniec ze Amerykanscy matematycy zlamali tez wojskowy szyfr japonski w 1942 roku. To z kolei pomoglo pokonac japonska flote w bitwie o Midway w ktorej Japonia stracila trzy lotniskowce i panowanie w powietrzu .Byl to zwrotny moment w bitwie na Pacyfiku.

    • Piotr Napierała
      Piotr Napierała
      7 czerwca 2016 at 09:52 - odpowiedz

      tylko dlatego, że Niemcy myśleli, że jest nie do złamania, jakby się zorientowali szybciej nie byłoby roznicy

    • Piotr Napierała
      Piotr Napierała
      7 czerwca 2016 at 09:53 - odpowiedz

      wieksze znaczenie miało schwytanie wsyztskich agentów niemiec w UK, i przekabacenie ich by wywyłali fałszywe info, m,in potwierdzające „skuteczność” enigmy. Jak zwykle zerowa wiedza historyczna u pana Janusza…

  12. Janusz
    Janusz
    7 czerwca 2016 at 23:46 - odpowiedz

    „Pan Janusz” tylko uwaznie czyta i slucha co pisza i mowia kompetentni historycy.
    Prawda ze Niemcy jak i Japonczycy uwazali ze ich szyfr jest bespieczny. Co by bylo gdyby tak nie mysleli jest tylko domyslem a nie faktem . Ja sie staram pisac o faktach ktore mona wzglednie latwo sprawdzic .Ocena skrocenia wojny o 2 lata skutkiem zlamania Enigmy to poglad brytyjskich historykow. Odpowiedz na pytanie Czy to jest dokladne? wymaga badania historykow .Ja mam inne projekty .
    Jesli chodzi o Midway to bitwa byla zasadzka Floty USA dowodzonej przez Admirala Nimitza .Jego przeciwnikiem byl japonski admiral Yamamoto ktory tez dowodzil
    napadem na Pearl Harbor w grudniu 1941 roku.
    Japonczycy mieli tam niemal cala swoja flote aby zadac smirtelny cios Flocie USA. Ale ich szyfr zostal zlamany i w dodatku Amerykanie mieli dlugosiezny radar . Cala bitwa odbyla sie wylacznie w powietrzu bez artylerii okretowej. Japonskie lotniskowce byly zatopione torpedami zrzucanymi z nurkujacych bombowcow.
    Po utracie swoich lotniskowcow Japonia stracila
    mozliwosc obrony swoich baz na calym Pacyfiku.Amerykanie zaczely wyspa po wyspie wypychac Japonczykow z Pacyfiku co wymagalo inwazji
    z morza na lad . Tu centralna role odegrala dominacja w powietrzu i jedmostki desantowe piechoty mordkiej tzw marines.Bylo to bardzo kosztowne w sensie strat ludzkich ze wzgledu na fanatyczny opor Japonczykow. Na wielu wyspach Japonczycy woleli zginac w beznadziejnej obronie niz poddac sie .Kroniki filmowe pokazuja czasem
    zolnierzy japonskich ktorzy wychodzili z tunelu gorskiego
    palac sie jak ludzkie pochodnie. Setki japonskich zolnierzy nie wiedzialy o zakonczeniu wojny i opuscily dzungle wysp po kilkunastu latach od konca wojny.
    Wojna na Pacyfiku byla bardzo rozna od wojny w Europie .

  13. Janusz
    Janusz
    9 czerwca 2016 at 05:08 - odpowiedz

    Najstarsze szczatki praczowieka w Indonezji.
    W 2014 i 16 archeolodzy znalezli w Indonezji fragmenty praczlowieka .Bylo to male stworzenie o wysokosci okolo 1 metra ktore wyginelo.To odkrycie jest fascynujace poniewaz datowanie zebow i szczeki pokazalo ze ten nasz kuzyn zyl 700,000 lat trmu. Artykul o nim ukazal sie w zurnalu Nature.

  14. Janusz
    Janusz
    10 czerwca 2016 at 23:00 - odpowiedz

    EMERGENCJA
    Po dyskusji o zlozonosci kolej na krotkie wyjasnienie czym jest emergencja.
    Slowo pochodzi od angielskiego czasownika to emerge co znaczy powstac.Na przyklad:Poland emerged after WW I as a result of the Versailles Treaty. Polska powstala po Pierwszej Wojnie na mocy traktatu wersalskiego.
    W nauce slowo emergencja znaczy powstanie nowej jakosci jako rezultatu wspoldzialania wielu elementarnych skladnikow.
    Przykladem moze byc gwiazda ktora sklada sie z atomow helu i wodoru i zachowuje sie inaczej niz jej skladniki. Lepszym przykladem jest procesor komputera lub ludzki mozg.
    Procesor wsparty pamiecia moze wykonac bardzo zlozone obliczenia ale jak przyjrzymy sie blizej procesorowi to zauwazymy ze sklada sie z tranzystorow ktore wykonuja kilka prostych operacji zerojedynkowych logiki Boole’a .Tych opercji ucza na pierwszym roku informatyki.
    Podobnie jest z mozgiem ,ktory potrafi wytworzyc poczucie swiadomosci,myslec i czuc ale sklada sie z
    miliardow neuronow ktore choc chemicznie skomplikowane wykonuja proste operacje na elektrycznych slabych sygnalach. Moga sygnal wzmocnic i przeslac do sasiadow lub zatrzymac.
    Problemami emergencji zajmowal sie Istytut Naukowy w Santa Fe w Nowym Meksyku. Byli tam naukowcy biologii,psychologii, astrofizyki , matematyki i informatyki.Celem badan bylo zrozumienie jak powstaja bardzo zlozone stystemy z prostych elementow.Pionierem tego problemu byl fenomen matematyczny John von Neumann w latach 1940tych ktoremu zawdzieczamy architekture nowoczesnego komputera. John odkryl ze bardzo proste regoly rzadzace elementami systemu mogas prowadzic do zlozonosci achowania calego systemu. John stworzyl tzw teorie automatow ktore zapoczatkowaly cala dziedzine badan zlozonych systemow.
    Dlaczego naukowcy sa zainteresowani problemem emergencji?.Glowna motywacja jest zrozumienie powstania zycia na ziemi. Kazda zywa istota to skomplikowany system skladajacy sie z martwych atomow i molekul ktore pojedynczo niczego takiego jak
    myslenie ,czucie kub swiadomosc nie maja. Tylko razem wspoldzialajac wykon uja zdumiewajace czynnosci i maja nadzwyczajne wlasciwosci.

  15. Janusz
    Janusz
    12 czerwca 2016 at 00:35 - odpowiedz

    Ilustracja problemu wykladniczo zlozonego.
    W eseju jest przyklad szybko rosnacej funkcji wykladniczej .Skladanie kartki papieru nie jest oczywiscie praktycznym problemem.
    Teraz opisze problem ktory jest praktyczy i posiada algorytm wykladniczo zlozony. Szegoly nie sa tu istotne i mozna je znalezc w mojej ksiazce „Discrete Optimization
    Problems with Pascal programs”Prentice Hall 1984.
    Pascal to jezyk programowania komputerow ktory byl popularny na uniwersytetach w pkresie pisania ksiazki.
    Pascal byl filozofem ktory polecal wiare w boga jako mniejsze ryzyko w wypadku pomylki. Taki francuski asekurant. Ale ludzie go sluchaja.
    W latach 1930 tych rosyjski matematyk Kantorowicz zajmujacy sie problemami ekonomii sformulowal problem programowania liniowego do optymalizacji niektorych problemow w ekonomii, transporcie i komunikacji. Dostal za to Nobla w ekonomii.Zastosowania czekaly do momentu w 1950tych latach kiedy Amerykanin z Stanford University George Danzig stworzyl szybki algorytm zwany simplex.Ten algorytm ma ograniczenia .Na przyklad jesli liczby w wyniku musza byc tylko 1 lub 0 algorytm sie nie stosuje. Aby to pokazac zalozymy ze maly problem liniowego programowania wymaga wyniku
    zer lub jedynek. Tak zrobilem w 1983 roku uzywajac szybkiej madszyny dla sprawdzenia czasu obliczen algorytmu ktory rozwiazuje problemy zero jedynkowe. Okazalo sie ze czas obliczen rosnie wykladniczo.
    NP dla problemu z n=7 zmiennymi czas byl 8 milisekund.
    Dla podwojnej ilosci zmiennych n=15 czas obliczen wzrosl do 1788 milisekund. Fatalnie szybko!
    Funkcja czasu byla Time(n)=0.0625*2 do potegi n.
    Jest to podobny wzrost jak grubosc zwitka papieru w eseju. Taki wzrost czasu wyklucza rozwiazanie praktycznych problemow o rozmiarach ponad n=100 zmiennych.
    Takich problemow sa setki. Tu uciekamy sie do rozwiazywania problemu przez podzielenie na male czesci lub znalezienie przyblizonych rozwiazan.
    W naturze wykladnicza eksplozja odgrywa duza role w rozmnazaniu jednokomorkowcow przez podzial.
    Seksualne rozmnazanie z dwoma osobnikami powstalo dosc pozno w ewolucji. Przyspieszylo ewolucje skutkiem kombinowania genow rodzicow. Bez seksualnego rozmnazania ewolucja bylaby dluzsza lub niemozliwa.
    Podsumowujac: nasze istnienie zawdzieczamy miedzy innymi faktami dwom wydarzeniom. Jednym byla smierc gwiaazd (supernova explosion) ktore wyrzucily ciezkie atomy stworzone wewnatrz gwiazd) oraz temu ze natura stworzykla rozmnazanie przez dwuplckiowy sekjs. Bez tego bylibysmy prostymi bakteriami w pierwotrnej zupie
    oceanow.Rowniez wymarcie dinozaurow umozliwilo szybki rozwoj mniejszych ssakow .Natepne rewolucje to wyjscie z oceanu na lad, zejscie z drzewa na ziemie i rozwoj mowy.
    I jak tu nie byc szczesliwym czlowiekien dyskutujacym
    ewolucje i wykladnicza zlozonosc na lamach Racjonalisty.
    To znacznie lepsze niz byc bakteria lub szkieletem Neandertalczyka ktory wymarl skutkiem Intelligent Design!! 99.9 % zyjacych istot na ziemi wymarlo . To co widzimy dookola to wyjatki. My tez to wyjatek .Homo sapiens mogl zniknac tak jak nasz kuzyn Neandertal.
    Mala dziewczynka zapytala mamy: dlaczego te wyjatki wyja?

  16. Janusz
    Janusz
    21 czerwca 2016 at 05:08 - odpowiedz

    Pisalem o znaczeniu zlamania wojskowego kodu niemieckiego w zwyciestwie Aliantow w bitwie o Atlantyk.
    Amerykanie zlamali rowniez kod japonski co pomoglo pokonac flote japonska pod Midway na Pacyfiku.
    Japonczycy spodziewali sie ze flota amerykanska bedzie bronila Hawaii glowne bazy marynarki .Amerykanie urzadzili zasadzke wysylajac duza czesc swojej floty na spotkanie z Japonczykami kolo wyspy Midway.W morskiej bitwie lotniskowcow Japonczycy stracili c ztery lotiskowce i do konca wojny inicjatywe na morzu i w powietrzu.
    Byl to zwrotny moment w wojnie z Japonia ktora trwala od 7 grudnia 1941 do 2 wrzesnia 1945.

Zostaw komentarz

Wpisz kod antySPAMowy *