1 Wprowadzenie do filozofii computer science Wykład monograficzny r.a. 2011/2012 Prowadzący: Paweł Polak
2 Część 3: Polski wkład do CS 1. Wkład w rozwój techniki obliczeniowej (XIX w.) 2. Wkład teoretyczny (lata 20.-40., 80.) 3. Przetwarzanie danych – źródła błędów w mechanicznych obliczeniach statystycznych (1928) 4.Języki programowania 5.Wątpliwy wkład ideologiczny
3 Główne źródła informacji Polish Contributions to Computing http://chc60.fgcu.edu/ http://chc60.fgcu.edu/ Katalog Historia Nauka i Technika – zdigitalizowane materiały archiwalne dotyczące historii computer science w Polsce http://hint.org.pl/ http://hint.org.pl/ Własne poszukiwania
4 1. Wkład w rozwój techniki obliczeniowej XIX-wieczni konstruktorzy maszyn liczących: Jewna Jacobson – mechaniczna maszyna licząca (przed 1770) Abraham Izrael Stern – maszyna licząca: cztery operacje i pierwiastkowanie (1817) Chaim Zelig Słonimski – maszyna do mnożenia (1840) Izrael Abraham Staffel – maszyna licząca: cztery operacje i pierwiastki kwadratowe (1844) Bruno Abdank-Abakanowicz – wynalezienie integrafu, czyli mechnicznego integratora (1878)
5 2. Wkład teoretyczny – Jan Łukasiewicz i notacja polska Jan Łukasiewicz (1878-1956) – polski logik ze Lwowa, uczeń Tardowskiego 1924 – sformułowanie notacji beznawiasowej użyta po raz pierwszy w pracy „O znaczeniu i potrzebach logiki matematycznej”, Nauka Polska, X (1929). 1950 – K.L. Bauer: „Stanislaus” maszyna logiczna sterowana formułą w notacji polskiej, powstaje pojęcie stosu (Kellerprinzip). Bauer dowiedział się o notacji od Zusego, a ten od wiedeńczyka Karla Mengera
6 2. Wkład teoretyczny – Jan Łukasiewicz i notacja polska (2) Znaczenie notacji polskiej na jej bazie stworzono pojęcie stosu, wpłynęła na język Algol i jego kompilatory znaczenie dla rozwoju wczesnych kompilatorów, Bob Cralle (Lawrence Livermore National Labs): „the people who did the first FORTRAN were unaware of his [Łukasiewicz] work, which allowed one easily do one pass through an algebraic statement and parse it into instructions with which the computer could compute”. kompilatory tłumaczą wyrażenia na ciąg instrukcji odpowiadający odwrotnej notacji polskiej
7 2. Wkład teoretyczny – złamanie kodu Enigmy (1) Marian Rejewski, Jerzy Różycki i Henryk Zygalski Rejewski opracował podstawy matematyczne do złamania kodu Enigmy Należało odtworzyć wewnętrzną budowę Enigmy (stosowano różne typy) i rozkodować zmienny klucz wysyłany w nagłówku wiadomości Rejewski opracował teorię cykli i teorię podstawień oraz sformułował równania opisujące działanie maszyny (za pomocą permutacji)
8 2. Wkład teoretyczny – złamanie kodu Enigmy (2) Płachty Zygalskiego – pozwalały na analizę tzw. „żeńskich” pozycji (powtórzenia tej samej litery w kodzie na 1 i 4 pozycji lub 2 i 5 itp. metoda „rusztu” polegała na sprawdzeniu wszystkich sześciu możliwych zestawów trzech bębnów i dla każdego z nich na sprawdzeniu 26 możliwych liter na pierścieniu lewego bębna (156 prób, ale wynik zwykle osiągano wcześniej) płachty były przygotowane dla każdej litery i każdej kombinacji wirnika
9 2. Wkład teoretyczny – złamanie kodu Enigmy (3) Bomba kryptologiczna – Rejewski opracował zautomatyzowany sposób znajdowania ustawień wirników Enigmy na podstawie żeńskich pozycji w ustawieniach podwójnie szyfrowanych kluczy wiadomości służyła jedynie do łamania klucza, synchroniczne obroty 6 zestawów bębnów Enigmy za pomocą silnika elektrycznego, każdy bęben był przestawiony o jedną pozycję w stosunku do poprzedzającego pierwszy na świecie pomysł zautomatyzowanego łamania kodu rysunek Rejewskiego
10 2. Wkład teoretyczny – S. Ulam i metoda Monte Carlo Stanisław Ulam (1909-1984) – polski fizyk, pracował przy projekcie bomby wodorowej (konfiguracja Tellera- Ulama zapłonu bomby wodorowej) 1947 – sformułowanie metody Monte Carlo (współpraca: N. Metropolis, J. von Neuman) – metoda testowania statystycznego metoda służy do rozwiązywania skomplikowanych problemów, niemożliwych do rozwiązania metodami analitycznymi) – obok przykład całkowania (błąd całkowania maleje proporcjonalnie do 1/\sqrt{N}
11 2. Wkład teoretyczny – Zdzisław Pawlak i zbiory przybliżone Zdzisław Pawlak (1926-2006) współtwórca pierwszego polskiego komputera XYZ (1958), opracował nową metodę geneowania liczb pseudolosowych (1951) – pierwsza polska praca z informatyki (1953) metoda reprezentacji liczb w systemie pozycyjnym z ujemną podstawą (tzw. system arytmetyki minus dwójkowej ozn. "-2"), lata 50. maszyna UMC-1 operująca w tym systemie (kilkadziesiąt sztuk) model formalny komputera („maszyna Pawlaka”) zaproponował klasę języków beznawiasowych, uogólnienie pomysłu Łukasiewicza (cytowany przez D. Knutha w „The Art of Programming”; „Organizacja maszyn bezadresowych” (1962) pierwszy formlny model kodu genetycznego DNA
12 2. Wkład teoretyczny – Zdzisław Pawlak i zbiory przybliżone (2) Teoria zbiorów przybliżonych 1982 (wg. Wikipedii): formalizm matematyczny, stanowiący rozwinięcie klasycznej teorii zbiorów. Zbiór przybliżony (ang. rough set) – obiekt matematyczny zbudowany w oparciu o logikę trójwartościową. W pierwotnym ujęciu zbiór przybliżony to para klasycznych zbiorów: przybliżenie dolne i przybliżenie górne. Istnieje również odmiana zbioru przybliżonego, definiowana przez parę przybliżeń będących zbiorami rozmytymi (ang. fuzzy set). Dany element może należeć do obydwu przybliżeń, do żadnego lub tylko do przybliżenia górnego. Narzędzie do modelowania niepewności wynikającej z braku odpowiednich informacji. Stosowane w technologiach kosmicznych (NASA), w medycynie i w ekonomii.
13 2. Wkład teoretyczny – Zdzisław Pawlak i „maszyna Pawlaka” Z. Pawlak, „Maszyny programowane”, Algorytmy (1969), nr.10, s.5-19: «Celem pracy jest sprecyzowanie podstawowych pojęć z zakresu maszyn matematycznych, takich jak pamięć maszyny, obliczanie, program itp. Punktem wyjścia pracy jest pojęcie procesu obliczania. Zdefiniowano maszynę jako funkcję częściową, której argumentami i wartościami są stany pamięci maszyny. Udowodniono pewne elementarne własności maszyn oraz wskazano na dalsze problemy związane z ich teorią. » dzisiejsza ocena: „Stosowność wykorzystywanego w tym celu matematycznego aparatu ( z teorią mnogości jako ontologią fundamentalną ) nie jest jednak dyskutowana. W konsekwencji trudno ocenić moc wiążącą podanych definicji”.
14 2. Wkład teoretyczny – Zdzisław Pawlak i zbiory przybliżone (2) Teoria zbiorów przybliżonych 1982 (wg. Wikipedii): formalizm matematyczny, stanowiący rozwinięcie klasycznej teorii zbiorów. Zbiór przybliżony (ang. rough set) – obiekt matematyczny zbudowany w oparciu o logikę trójwartościową. W pierwotnym ujęciu zbiór przybliżony to para klasycznych zbiorów: przybliżenie dolne i przybliżenie górne. Istnieje również odmiana zbioru przybliżonego, definiowana przez parę przybliżeń będących zbiorami rozmytymi (ang. fuzzy set). Dany element może należeć do obydwu przybliżeń, do żadnego lub tylko do przybliżenia górnego. Narzędzie do modelowania niepewności wynikającej z braku odpowiednich informacji. Stosowane w technologiach kosmicznych (NASA), w medycynie i w ekonomii.
15 3. Przetwarzanie danych inż. Juliusz Miller „O dokładności opracowań dat statystycznych przy pomocy maszyn systemu Powers'a”, Kwartalnik Statystyczny (1928) z.1, s.185 (dostępny w katalogu hnit.org.pl) «Celem niniejszej pracy jest analiza tych wszystkich faktów, które mają wpływ na dokładność maszynowego opracowania materiałów statystycznych oraz określenie sposobów ujawniania i usuwania błędów. » oszacowanie błędów obróbki danych, rozważania nad optymalizacją i ergonomią procesu obróbki, meotdy wykrywania błędów
16 4. Języki programowania (1) Praca z historii języków programowania: Zygmunt Ryznar, Zarys historii programowania elektronicznych maszyn cyfrowych (na tle rozwoju ich konstrukcji i zastosowań), Ośrodek Badawczo-Rozwojowy Informatyki, Warszawa 1972 Polskie języki programowania (lata 60.): SAS (System Adresów Symbolicznych), PJES (Podstawowy Język Symboliczny), EOL (Expression Oriented Language) oraz wersje językowe ALGOLu, COBOLu i podzbioru GPSS (CEMMA 2 – Cyfrowe Modelowanie Maszyny Analogowej). oprac Instytut Maszyn Matematycznych w Warszawie (oprócz SAS).
17 4. Języki programowania (2) SAKO (System Automatycznego Kodowania) – oryginalny język, oprac. Instytut Maszyn Matematycznych w Warszawie pierwszy translator uruchomiono w 1962 roku przykład (wg Ryznara): GDY BYŁ NADMIAR: α INACZEJ β SKOCZ WEDŁUG I: α β... WRÓĆ itp.
18 5. Wątpliwy wkład ideologiczny Oskar Lange (1904-1965) – ideolog gospodarki planowej O socjaliźmie i gospodarce socjalistycznej, Państwowe Wydawnictwo Naukowe, Warszawa 1966 s.448-456 „Maszyna licząca i rynek”, Życie Gospodarcze,1965.10.24 «Zaprogramujmy układ jednoczesnych równań na elektronowej maszynie liczącej i otrzymamy odpowiedź w niecałą sekundę. Proces rynkowy ze swą uciążliwą metodą prób i błędów wydaje się przestarzały. Może on być traktowany jako narzędzie rachunkowe wieku przedelektronowego.» Wizja naiwna, brak świadomości problemów ze złożonością obliczeniową. Do dziś problem aktualny w związku z regulacjami gospodarki (planowanie = ścisła regulacja).