Liczby Całkowite i Estymaty

uncle bob label image
Co to jest: a^2 + b^2 = c^2
Twierdzenie Pitagorasa
Dobrze. Czym jeszcze to jest?
Równaniem z trzema niewiadomymi.
Znasz jakieś rozwiązania tego równania?
Jasne. (3,4,5) i (5,12,13).

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony :


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Dobrze. To są często spotykane trójki pitagorejskie. Znasz jakieś inne?
Cóż, Google jest moim przyjacielem, zobaczmy. (wpisuje) Wygląda na to, że (7,24,25) i (9,40, 41) spełniają to równanie.
Zauważyłeś, że te rozwiązania, które podałeś zawieraja tylko liczby całkowite?
Ooo, no tak. Przypuszczam, że jest całe mnóstwo niecałkowitoliczbowych rozwiązań.
Słyszałeś o Diofantosie?
Czy to nazwisko jakiegoś Greka?
Tak, Diofantos zainteresowany był równaniami, które mają rozwiązania złożone z liczb całkowitych. Nazywamy takie równania równaniami diofantycznymi.
Więc a^2 + b^2 = c^2 jest równaniem diofantycznym?
Tak. I jest też wiele innych. Na przykład: a^3 + b^3 = c^3
Ok, spoko. I jakie są przykładowe rozwiązania?
Nie ma żadnych.
Naprawdę? Żadnych?
Tak. Żadnych. To zostało udowodnione. W rzeczywistości zostało udowodnione, że każde równanie a^n + b^n = c^n nie ma całkowitoliczbowych rozwiązań dla n > 2. To jest znane jako Wielkie Twierdzenie Fermata
Hmm. To mogłoby być całkiem interesujące, ale dlaczego mam się tym przejmować w ogóle?
Co to jest komputer cyfrowy?
Co masz na myśli? Ta rzecz na której Ty i ja rozmawiamy jest komputerem cyfrowym.
Tak, ale co dokładnie robi komputer cyfrowy?
Yyy. Oblicza cyfrowo?
Dokładnie! I słowo cyfrowy oznacza ... ?
Hmm. Z użyciem cyfr?
Własnie! I czy liczba tych cyfr jest skończona?
Oczywiście, choć bardzo, bardzo duża w dzisiejszych czasach.
... i skończona liczba cyfr to...?
Ooo, myślę, że wiem, do czego zmierzasz. Skończona liczba cyfr jest liczbą całkowitą.
Tak. Komputer cyfrowy to komputer, który oblicza przy użyciu liczb całkowitych. Przy użyciu tylko liczb całkowitych, niczego innego.
No cóż, chwileczkę. A co z liczbami zmiennoprzecinkowymi i liczbami wymiernymi.
Są reprezentowane w komputerze przez liczby całkowite. Komputer radzi sobie z liczbami całkowitymi - tylko z liczbami całkowitymi.
OK. Dobra. Liczby całkowite. Ale co to ma wspólnego z równaniami diofantycznymi?
Jakie są wejścia programu komputerowego?
Jest wiele różnych typów. Znaki z klawiatury, ruchy myszki, kliknięcia myszki, pakiety internetowe. Do wyboru, do koloru.
One są pod spodem liczbami całkowitymi, prawda?
Hmm. No tak. Wydaję mi się, że są. OK, czyli każde wejście do programu komputerowego to liczby całkowite.
A co z wyjściami?
No cóż, tak, piksele, znaki, pakiety sieciowe. One wszystkie też są złożone z liczb całkowitych.
Więc komuter cyfrowy pobiera liczby całkowite i zwraca liczby całkowite.
Prawda. Masz rację. To wszystko liczby całkowite.
Program komputera cyfrowego, zatem, reprezentuje równanie diofantyczne.
Czekaj. Co?
Liczby całkowite na wejściu. Liczby całkowite na wyjściu.
Ok. Pewnie. Ale to całkiem duże, skomplikowane równanie diofantyczne.
Właściwie, specyfikacja programu jest równaniem. Program znajduje rozwiązanie tego równania.
Tak, tak, OK. To prawda. Specyfikacja programu jest jednym wielkim równaniem diofantycznym z tryliolem niewiadomych i program spełnia tę specyfikację znajdując rozwiązanie tego ogromniastego równania. Czy ta wiedza jest do czegoś potrzebna?
Kto to jest David Hilbert?
Masz na myśli tego gościa, który zaprojektował tę śmieszną rekurencyjną krzywą, która wyglada jak siatka na owady?
(Yhy) To było jedno z jego osiągnięć, tak. On także pomógł Einsteinowi z Ogólną Teorią Względności. Był wspaniałym matematykiem.
I zgaduję, że zrobił coś w temacie równań diofantycznych
W rzeczy samej on robił wiele, wiele rzeczy. Pośród nich było słynne pytanie. Pytanie o "Entscheidung" - rozstrzygalność.
Co on chciał rozstrzygnąć?
Pamiętasz Wielkie Twierdzenie Fermata?
Masz na myśli to równanie, które nie ma rozwiązań. a^n + b^n = c^n gdzie n > 2?
Tak, właśnie to. Przez długi czas nie było dowodu, że przy n = 2 równanie ma jedyne rozwiązanie. Jak możesz obalić przypuszczenie, jeżeli wydaje Ci się ono nieprawdą?
Mógłbym napisać program, który znajduje kontrprzykłady. Na przykład dla n=999999999 to mogłoby zadziałać.
Dobra. I gdybyś znalazł takie rozwiązanie to obaliłbyś Twierdzenie Fermata. Ale jak długo zajęłoby Ci DOWIEDZENIE tego twierdzenia przy użyciu tej metody?
Program wykonywałby się w nieskończoność. Nie mógłbym dowieść twierdzenia w ten sposób.
Dokładnie. To, czego Hilbert chciał, to skończony algorytm do sprawdzenia czy rozwiązanie istnieje, czy nie. Chciał sposobu "decydowania" czy poszukiwania, takie, jak Ty zaproponowałeś byłyby praktyczne.
Czekaj, zaraz. Co? Nie szukał rozwiązań. Szukał możliwości dowiedzenia się czy byłyby rozwiązania?
Tak. Chciał skończonego algorytmu, który powiedziałby, czy dane równanie diofantyczne ma rozwiązania czy nie. Ten algorytm nie dostarczałby rozwiązań; dostarczałby tylko rozstrzygnięcie.
To dlatego nazwał to "rozstrzygalnością"?
Entscheidung. Tak.
Harumph! A teraz. Kto Twoim zdaniem rozwiązał problem rozstrzygalności?
Sądzę, że zaraz mi powiesz.
Dwoje ludzi, o których już słyszałeś. Dwoje wielkich ojców współczesnej informatyki. Alonzo Church i Alan Turing.
Church! To ten gość, który wymyślił programowanie funkcyjne, tak?
W pewnym sensie tak.
I Turing! Wygrał II Wojnę Światową, prawda?
No, na pewno się dołożył. Oni oboje udowodnili, używając zupełnie innych sposobów, że nie istnieje ogólne i skończone rozwiązanie dla rozstrzygalności.
To musiało zawieść Hilberta.
Być może. Ale nie o to chodzi.
OK, no to o co chodzi?
Kiedy dają Ci specyfikację programu, to jest równania diofantycznego, to o co zwykle proszą Cię na początku?
O estymatę oczywiście. Goście chcą wiedzieć jak długo potrwa napisanie programu.


I jeszcze raz, czym jest program w świetle równania diofantycznego?
Program jest ... rozwiązaniem ... dla ... AAA!
(uśmiech) Wydaje mi się, że zaczynasz rozumieć.
Taaa, że, oni proszą mnie abym ROZSTRZYGNĄŁ. Estymata jest rozstrzygnięciem.
I czy istnieje skończona metoda znalezienia rozstrzygnięcia w każdym przypadku?
Nie! O KURKA, to zabawne.
No właśnie. Fundamentalne podstawy informatyki dowodzą, że nie istnieje skończony mechanizm rozstrzygania czy program może być kiedykolwiek napisany. Fundamenty informatyki oparte są na dowodzie, że estymaty nie są gwarantowane.
No tak, ale nadal MOŻEMY estymować.
Tak, możemy. Ponieważ większość specyfikacji jest estymowalna.
A więc to była tylko mała matematyczna rozrywka bez żadnego użytecznego zastosowania.
Można tak powiedzieć. Ale podobało mi się to. Poza tym, to przepysznie ironiczne, że to właśnie dowód o NIEESTYMOWALNOŚCI stoi u podstaw dzisiejszej informatyki.

Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony :


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Zasada skautów

uncle bob label image
Skauci mają zasadę: "Zawsze zostawiaj obozowisko czystsze niż je zastałeś." Jeśli zastaniesz bałagan, posprzątaj go, niezależnie od tego, kto to zrobił. Celowo ulepszaj otoczenie dla następnych obozowiczów. W rzeczywistości, oryginalne brzmienie tej zasady, zapisanej przez Roberta Stephensona Smytha Baden-Powella, ojca skautingu, jest następujące: "Postaraj się zostawić świat choć trochę lepszym, niż go zastałeś."

Poniższy tekst jest tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony (Wayback Machine) :


Bazowałem na tłumaczeniu jakie dokonał Rafał Legiędź. @rafek.

na nieistnieącej już stronie 97rzeczy.devblogi.pl.

Archiwum na Wayback Machine

Licencja oryginalnego tekstu: Creative Commons Attribution 3


Co byłoby gdybyśmy postępowali według tej samej zasady podczas naszego kodowania: "Zawsze wysyłaj do repozytorium moduł czystszy niż go pobrałeś"? Co byłoby gdybybyśmy zawsze wkładali trochę wysiłku, nieważne jak małego, aby ulepszyć moduł, niezależnie od tego, kto był oryginalnym autorem? Jaki byłby rezultat?
Myślę, że jeżeli wszyscy pracowalibyśmy według tej zasady, to doświadczylibyśmy końca nieustającego pogarszania się naszego oprogramowania. Zamiast tego, nasze systemy, ewoluując stawałyby się coraz lepsze. Dostrzeglibyśmy zespoły, które dbają o system jako całość, a nie tylko indywidualne jednostki dbające o swoje małe części.
Nie sądzę, aby ta zasada była prośbą o zbyt wiele. Nie musisz doprowadzać każdego modułu do perfekcji przed oddaniem go do repozytorium. Po prostu musisz tylko sprawić, aby stał się odrobinę lepszy niż go zastałeś. Oczywiście oznacza to, że jakikolwiek kod jaki dodajesz do modułu musi być czysty. Oznacza to również, że musisz poprawić chociaż jedną dodatkową rzecz zanim skomitujesz moduł do repozytorium. Mógłbyś po prostu poprawić nazwę zmiennej, albo podzielić długą funkcję na dwie mniejsze. Mógłbyś usunąć cykliczne zależności, albo wprowadzić interfejs, aby odłączyć kontrakt od detali.


Szczerze mówiąc, to brzmi jak zwykły dobry nawyk - jak mycie rąk po skorzystaniu z ubikacji, bądź wrzucenie śmieci do kosza zamiast na ziemię. W rzeczywistości fakt zostawiania bałaganu w kodzie powinien być tak samo nieakceptowalny społecznie, jak śmiecenie. To powinno być coś, czego po prostu się nie robi.
Ale to coś jeszcze wiecej. Dbanie o własny kod to jedno. Dbanie o kod zespołu to kolejna rzecz. Zespoły pomagają sobie i wzajemnie po sobie sprzątają. Pracują trzymając się Zasady Skautów, ponieważ jest dobra dla wszystkich, a nie tylko dobra dla nich samych.

Powyższy tekst jest tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony (Wayback Machine):


Bazowałem na tłumaczeniu jakie dokonał Rafał Legiędź. @rafek.

na nieistnieącej już stronie 97rzeczy.devblogi.pl.

Archiwum na Wayback Machine

Licencja oryginalnego tekstu: Creative Commons Attribution 3