ELEMENTY INFORMATYKI Podręcznik Ewa Gurbiel Ewa Kołczyk Helena Krupicka Krzysztof Łukojć Zdzisław Płoski Maciej M. Sysło Jerzy Witkowski Roman Zuber pod redakcją Macieja M. Sysły wydanie trzecie zmienione Warszawa 1993 Wydawnictwo Naukowe PWN Książka ta jest zmienioną i rozszerzoną wersją książki: W. Dańko, E. Gurbiel, Z. Jarzębowski, E. Kolczyk, H. Krupicka, K. Łukojć, Z. Płoski, M.M. Sysło, R. Zuber, Elementy informatyki. Podręcznik pod redakcją M.M. Sysły; Wydanie pierwsze - Wydawnictwo Uniwersytetu Wrocławskiego, Wrocław 1988; Wydanie drugie - OFEK, Jelenia Góra 1990. Książka zalecana przez Ministra Edukacji Narodowej do użytku szkolnego i wpisana do zestawu książek pomocniczych do nauki informatyki na poziomie klasy I szkoły średniej. Numer w zestawie 314/93. Okładka i strony tytułowe: Maryna WiŚNIEWSKA Ilustracja na okładce: MAŁGORZATA FlLEW Redaktor: Agnieszka Grabarczyk Redaktor techniczny: JOLANTA ClBOR Skład komputerowy w TgX-u: Autorzy Copyright © by Wydawnictwo Naukowe PWN Sp. z o.o. Warszawa 1993 ISBN 83-01-11366-9 Następujące nazwy produktów i nazwy firm, do których odwołujemy się w tej książce są zastrzeżonymi znakami i nazwami handlowymi odpowiednich firm: IBM PC, AT, 386 - International Business Machines Corp.; MS-DOS, Windows - Micro- soft Corp.; The Norton Commander - Peter Norton Computing, Inc.; XTree, XTreeGold - Executive Systems, Inc.; AC-Logo - AdvaCom, Poznań; Turbo Pascal i Quattro Pro - Borland International, Inc.; dBASE, dBASE III - Ashton-Tate Co.; TAG - InfoSendce, Gdańsk; ChiWriter - Horstmann Software Design Co.; TgX - American Mathematical Society; Pizazz, Pizazz Plus - Application Technics, Inc.; CorelDraw - Corel Systems Corp. SPIS TREŚCI Wstęp 9 17 18 32 Czym jest informatyka. Elementy historii 1.1. Czym jest informatyka 17 1.2. Elementy historii informatyki Jak działa komputer 31 2.1. Dwójkowy system pozycyjny Wewnątrz komputera 34 Urządzenia zewnętrzne 36 Komputer w roli maszyny do pisania System operacyjny 45 Podstawowe zlecenia systemu MS-DOS Wokół komputera 59 Przy komputerze - pierwsze spotkanie 63 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 38 49 Zadania 65 69 71 3. Nauka i zabawa - grafika żółwia 3.1. Pierwszy rysunek 70 Pierwotne instrukcje graficzne Procedury 73 Wyrażenia 78 Zstępująca metoda projektowania algorytmów Rysowanie za pomocą procedur rekurencyjnych Struktury danych - listy 93 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 81 88 Zadania 102 4. Od problemu do programu - elementy programowania w języku Pascal 106 Podstawowe instrukcje 108 4.1. 4.2. 4.3. 4.4. 4.5. Zadania 154 Od problemu do programu 124 Funkcje i procedury 128 Strukturalne typy danych 133 Dynamiczne struktury danych 147 Spis treści 5. Zakładamy własny katalog - bazy danych 158 5.1. Zakładamy bazę danych. Pliki 158 5.2. Co już wiemy o plikach 165 5.3. Aktualizacja bazy danych 167 5.4. Systemy baz danych 174 5.5. Wprowadzenie do systemu dBASE 179 Zadania 187 6. Obliczenia w matematyce - metody numeryczne 189 6.1. Zadania numeryczne 189 6.2. Błędy zaokrągleń 190 6.3. Schemat Homera. Wzory rekurencyjne 195 6.4. Stabilność algorytmów 198 6.5. Interpolacja 203 6.6. Całkowanie numeryczne 211 6.7. Wyznaczanie pierwiastków równania 214 Zadania 222 7. Liczyć szybciej - efektywność algorytmów 225 7.1. Złożoność obliczeniowa 225 7.2. Złożoność algorytmu a czas działania programu 226 7.3. Dwa algorytmy optymalne 229 7.4. Porządkowanie ciągów 234 7.5. Porządkowanie przez scalanie 237 7.6. Niezbędna liczba porównań w algorytmach porządkowania Zadania 245 8. Bez kartki i ołówka - przetwarzanie tekstów 250 8.1. O sztuce opracowywania tekstów 250 8.2. Redagujemy tekst za pomocą komputera 251 8.3. Uruchomienie edytora 254 8.4. Trzy warstwy edytora TAG 254 8.5. Użytkowniku, pomóż sobie sam! 257 8.6. Okna i ich zastosowanie 258 8.7. Komputerowy "brudnopis", manewrowanie kursorem 8.8. Usuwanie i wstawianie tekstu 260 8.9. Operacje na blokach tekstu 262 8.10. Wyszukiwanie i zamiana tekstów 264 8.11. Wycofywanie pochopnych decyzji 265 8.12. Składowanie informacji 266 8.13. Przeglądanie plików 266 8.14. Zakończenie pracy 267 8.15. Inne własności edytorów 268 241 259 Spis treści Zadania 269 9. Łatwe i sprawne zarządzanie firmą - arkusz kalkulacyjny 271 9.1. Co to właściwie jest arkusz kalkulacyjny? 272 9.2. Rozpoczynamy pracę 274 9.3. Sposoby wyświetlania liczb, zasięg działania poleceń 277 9.4. Nieco o wyrażeniach 278 9.5. Prosty model symulacyjny 279 9.6. Nanoszenie poprawek 280 9.7. Zakończenie pracy 282 9.8. Skomputeryzowane przyznawanie premii 282 9.9. Graficzna prezentacja danych 285 9.10. Funkcje logiczne 287 9.11. Arkusz a metody numeryczne 289 9.12. Nowy system programowania? 292 9.13. Podsumowanie 293 Zadania 294 Dodatek. Kody ASCII 295 Omówienie literatury uzupełniającej 296 Skorowidz 298 WSTĘP Książka ta jest wprowadzeniem do informatyki i jako podręcznik może być wyko- rzystywana na zajęciach z elementów informatyki w szkołach średnich. Może być także pomocna w nauczaniu podstaw informatyki w szkołach pomatural- nych i na niektórych kierunkach studiów, w szczególności na studiach nauczyciel- skich: dziennych i podyplomowych. Książka jest pierwszą częścią opracowania pod wspólnym tytułem Elementy informatyki - do tej części odwołujemy się dalej przez EI-I. Dwie następne części to: Rozwiązania zadań (EI-II) oraz Przewodnik metodyczny (EI-III). Do całego opracowania w trzech częściach odwołujemy się przez EL W związku z zasadniczym przeznaczeniem tej książki przyjęto, że Czytelnik dysponuje mikrokomputerem, który - zakładamy - jest zgodny z komputerem osobistym IBM PC1 oraz odpowiednim dla niego oprogramowaniem, w tym: systemem operacyjnym MS-DOS (w wersji 4.0 lub wyższej), systemami pro- gramowania AC-Logo i Turbo Pascal (w wersji 6.0 lub późniejszej), edytorem tekstów TAG i arkuszem kalkulacyjnym Quattro Pro. Książka ta nie jest jednak podręcznikiem obsługi któregokolwiek z wymienionych systemów oprogramowa- nia. Podajemy w niej tylko najważniejsze informacje umożliwiające korzystanie w szkole z komputerów i z ich oprogramowania. Dokładne informacje o wykorzy- stywanych przez nas systemach można znaleźć w leksykonach lub podręcznikach poświęconych wyłącznie tym systemom. Informacje i rozważania w tej książce, chociaż są specyficzne dla komputera IBM PC i jego oprogramowania, nie wykluczają możliwości posługiwania się nią na zajęciach prowadzonych z wykorzystaniem innych komputerów i innego opro- gramowania. Wiodącym tematem książki, wokół którego skupia się nasza uwaga, są algo- rytmy. Metody konstruowania algorytmów ilustrujemy na przykładach wybra- nych z kilku podstawowych dziedzin informatycznych: grafiki żółwia, struktur i baz danych, porządkowania, metod numerycznych, korzystania z arkusza kal- kulacyjnego i komputerowego opracowywania tekstów. Omawiamy poprawność 1W dalszych fragmentach tej książki oraz w EI-II i EI-III komputery zgodne z IBM PC są nazywane po prostu IBM PC. 10 Wstęp działania algorytmów i przedstawiamy ich realizacje w wybranym języku pro- gramowania. Poświęcamy także -wiele miejsca efektywności obliczeń. Książka ta jest wprowadzeniem do algorytmicznego myślenia, które jest sednem informa- tyki i podstawą istotnych zastosowań komputerów oraz metod informatycznych w innych dziedzinach wiedzy i działalności człowieka. Książka składa się ze wstępu, dziewięciu rozdziałów, dodatku, zawierającego tabelę kodów ASCII, omówienia literatury uzupełniającej i skorowidza. Przed- stawmy w skrócie zawartość kolejnych rozdziałów. W pierwszym rozdziale próbujemy odpowiedzieć na pytanie, czym jest infor- matyka, jak się kształtowały związane z nią pojęcia w trakcie rozwoju myśli ora2 innych osiągnięć człowieka i jaka jest jej rola we współczesnym społeczeństwie. W przypadku stosowania komputerów i ich oprogramowania sprawdzenien słuszności obranej drogi rozwiązywania postawionego zadania jest uruchomieni na komputerze programu poprawnie rozwiązującego to zadanie. Dlatego możliwi* jak najwcześniej należy zapoznać się z komputerem, który jest podstawową po mocą naukową na lekcjach informatyki. Jest temu poświęcony rozdział 2 zawie rający najważniejsze informacje o budowie, działaniu i obsłudze komputera IB]V PC oraz o systemie operacyjnym MS-DOS. Omówiono w nim sposoby przy gotowywania komputera do pracy i korzystania z niego. Niektóre z zastosował komputerów wymienione w tym rozdziale, takie jak maszynopisanie, są omówion szerzej w dalszych rozdziałach. Z punktu widzenia użytkownika, komputer służy do wykonywania programów Niektóre programy, zwłaszcza ogólnego przeznaczenia, są dostarczane zwykł wraz z komputerem, natomiast programy rozwiązujące konkretne zadania p szemy sami, korzystając często z możliwości, jakie dają te pierwsze. W k( lejnych rozdziałach omawiamy informatyczne metody rozwiązywania niektóryc grup zadań, posługując się przy tym wybranymi systemami oprogramowania. Rozdział 3 jest poświęcony grafice żółwia, na przykładzie wybranych el< mentów języka Logo, w wersji AC-Logo. Rozdział ten nie jest jednak zbiorę] lekcji o języku Logo, lecz zwartym opisem niektórych konstrukcji tego język które umożliwiają tworzenie nawet dość skomplikowanych ilustracji graficznyc i przy okazji ułatwiają zapoznanie się z zasadami programowania. Sporządzan rysunków komputerowych jest w tym rozdziale pretekstem do uczenia system tycznych metod rozwiązywania zadań, począwszy od właściwego sformułowań zadania, poprzez ułożenie algorytmu jego rozwiązywania aż do zapisania alg rytmu w języku programowania. Rozdział ten jest więc wprowadzeniem do po stawowych konstrukcji algorytmicznych i programistycznych w ich najprostss postaci, rozwiniętych i wzbogaconych następnie w rozdziałach 4-6. Zgodnie z tytułem rozdział 4 prowadzi drogą od podania opisu zadania, cz; jego specyfikacji, do otrzymania gotowego programu, tym razem w języku P WSTCP 11 scal. Podobnie jak w odniesieniu do języka Logo w rozdziale tym są omówione tylko podstawowe instrukcje i typy danych języka Pascal. Programy (i ich fragmenty) napisane w języku Pascal i zamieszczone w opra- cowaniach El są poprawne w sensie systemu Turbo Pascal (w skrócie TP), począwszy od wersji 4.0. Zakres wiadomości o języku Pascal w zasadzie nie wy- kracza poza standardową wersję tego języka. Z tych względów posługujemy się jednym określeniem "język Pascal". Określenia "język Turbo Pascal" używamy tylko przy omawianiu fragmentów programów, które korzystają ze specyficznych cech systemu TP. W rozdziale 5 są omówione czynności związane z tworzeniem, aktualizowa- niem i korzystaniem z bazy danych na przykładzie zbioru informacji o prywat- nej bibliotece książek. Czynności te są zapisane w języku Pascal. Rozważania w tym rozdziale stanowią uzupełnienie poprzedniego rozdziału o informacje do- tyczące plików i operacji na nich. Ponadto zilustrowano wykonanie tych samych czynności za pomocą systemu obsługi baz danych dBASE. W rozdziale 6 są opisane podstawowe sposoby rozwiązywania prostych zadań obliczeniowych z matematyki takich, jak: obliczanie wartości wielomianu i całki oraz znajdowanie pierwiastków równania. Matematyka jest jednym z tych przed- miotów szkolnych, który najbardziej nadaje się do stosowania komputerów jako pomocy naukowych. Lektura tego rozdziału powinna jednak uzmysłowić, że właściwie zaprojektowane algorytmy i programy rozwiązywania zadań obliczenio- wych (matematycznych) najczęściej nie polegają na prostym wykonaniu działań występujących we wzorach definiujących wynik obliczeń. Co więcej, niewłaściwe posługiwanie się wzorami może prowadzić do otrzymywania rezultatów daleko odbiegających od prawdziwych wartości. Rozdział 7 jest rozwinięciem i pogłębieniem rozważań o algorytmach, ze szcze- gólnym uwzględnieniem efektywności ich działania. Na przykładach podstawo- wych zadań, takich jak szukanie najmniejszego elementu w ciągu i porządkowanie ciągu liczb, omówiono elementarne własności algorytmów rozwiązywania tych zadań, które wiążą się z szybkością wykonywania obliczeń. Komputer jest urzą- dzeniem dość uniwersalnym i szybkim, ale łatwo można znaleźć przykłady zadań pokazujące, że nie przemyślane do końca jego wykorzystanie może prowadzić do bardzo długich obliczeń. Co więcej, w przypadku niektórych zadań nawet super- komputery nie są w stanie nam pomóc. Rozdział 8 jest rozszerzeniem informacji o posługiwaniu się klawiaturą kompu- tera (podanych w rozdz. 2) do w miarę pełnego omówienia najważniejszych cech wspólnych dla większości edytorów tekstów. Rozważania są ilustrowane opisem obsługi edytora TAG. Komputer jako urządzenie osobiste jest w dużej mie- rze używany do opracowywania tekstów i ta umiejętność stanowi dzisiaj trwały element podstawowego przygotowania do pracy z komputerem. 12 Wstęp Wykorzystanie komputera jako urządzenia wspomagającego tradycyjne po- moce w typowych obliczeniach rachunkowych jest tematem rozdziału 9. Omó- wiono w nim system Quattro Pro, należący do grupy programów zwanych ar- kuszami kalkulacyjnymi. Są to drugie pod względem popularności (po edy- torach tekstów) gotowe programy używane na komputerach osobistych. Dzięki swojej uniwersalności programy te mogą być stosowane w wielu dziedzinach wy- kraczających poza ich początkowe przeznaczenie, którym była mechanizacja prac biurowych. Na końcu każdego rozdziału (z wyjątkiem pierwszego) jest umieszczony zbiór zadań do samodzielnego rozwiązania. Ich celem jest sprawdzenie, utrwalenie oraz pogłębienie zdobytej wiedzy i umiejętności. Wiele z nich polega na napisaniu fragmentu (lub całego) programu, dlatego mogą być także materiałem na zajęcia w laboratorium komputerowym. Rozwiązania wszystkich zadań, skomentowane i uzupełnione dodatkowymi informacjami, są zebrane w części EI-II. Książka ta, jako podręcznik do zajęć z elementów informatyki, zawiera wiele fragmentów, w których materiał i skala jego trudności mogą wykraczać poza ramy przyjętego programu nauczania tego przedmiotu. Co więcej, stopnie trud- ności materiału w poszczególnych rozdziałach nie są rozłożone równomiernie. Na przykład materiał zawarty w rozdziałach 6 i 7 wymaga pewnego przygotowania matematycznego i może być zbyt trudny dla uczniów z młodszych klas licealnych. Sądzimy, że będzie trudno zrealizować wszystkie omówione w książce zagadnie- nia w trakcie zajęć odbywających się w podstawowym wymiarze czasu (tj. 2 go dziny tygodniowo przez jeden rok). Dlatego osoba wykorzystująca tę książkę jak< podręcznik powinna zadecydować o odpowiednim doborze materiału w zależność od przygotowania uczniów2. Dla ułatwienia, na rys. 0.1 przedstawiamy schemat zależności między pc szczególnymi rozdziałami. Linia ciągła między rozdziałami a i 6 oznacza, że prze przejściem do lektury rozdziału b należy przerobić rozdział a. Linia przerywan oznacza dodatkowo zalecaną kolejność rozdziałów. Podkreślmy jeszcze raz, ta książka nie jest przewodnikiem po którymkolwit z przedstawionych systemów oprogramowania. Nie jest także podręcznikiem pn gramowania ani w języku Logo, ani w języku Pascal. Zamieszczone programy i jedynie zapisem omawianych algorytmów w wybranym języku programowani W wielu przypadkach programy nie są w pełni gotowe do wykonywania na koi puterze, gdyż ze względu na ograniczoną objętość książki nie umieszczono w ni na przykład należytej obsługi wprowadzania danych i wyprowadzania otrzym wanych wyników. Książce towarzyszy dyskietka z tekstami prezentowanych programów i pc programów w językach Logo i Pascal. Programy w języku Logo zostały prze 2Piszemy o tym dokładnie w części EI-III. Wstęp 13 Rys. 0.1. Schemat zależności między rozdziałami stowane w systemie AC-Logo, a programy w języku Pascal - w systemie Turbo Pascal 6.0. Podręcznik EI-I jest zmienioną i rozszerzoną wersją książki, której dane znaj- dują się na stronie czwartej. Większość zmian i uzupełnień wynikła z wymiany komputerów w szkołach - mikrokomputer Elwro 800 Junior został zastąpiony komputerem zgodnym z IBM PC i odpowiednio zostały wymienione także sy- stemy oprogramowania, o których jest mowa w książce. Uzupełnieniem dwóch pierwszych części EI-I i EI-II, które są przeznaczone zarówno dla uczniów, jak i dla nauczycieli, jest część trzecia EI-III, Przewodnik metodyczny, adresowana przede wszystkim do nauczycieli. Część EI-III zawiera omówienie materiału z dwóch pierwszych części oraz propozycje jego rozkładu pod kątem bezpośredniego wykorzystania na lekcjach. Ponadto, w EI-III zamie- szczono propozycje programu nauczania przedmiotu elementy informatyki oraz rozkładu materiału dla klas z różną liczbą godzin zajęć z tego przedmiotu. Wyróżnienia w tekście Dla poprawienia czytelności autorzy przyjęli następujące zasady użycia różnych krojów i wielkości czcionek w tekście: 1. Wrszystkie teksty wyświetlane na ekranie lub drukowane na drukarce, wpro- wadzane przez użytkownika lub wyprowadzane przez programy, są wydru- kowane w książce pismem maszynowym, tzn. każdy znak takiego tekstu zaj- 14 Wstęp muje na papierze tyle samo miejsca. W szczególności pismem maszynowyr są wydrukowane programy (i ich fragmenty) w językach programowani Logo i Pascal oraz zawartości pól w arkuszu kalkulacyjnym. Ponadto: - Słowa kluczowe oraz nazwy procedur i funkcji standardowych w jęz; kach i systemach programowania są pisane wielkimi literami. - W nazwach (m.in. zmiennych i procedur), każda część mnemoniczi (tj. mająca brzmienie i znaczenie jakiegoś słowa) rozpoczyna się ( wielkiej litery, a pozostałe litery w nazwach są małe. - W programach w języku Logo mogą występować nazwy zawierają litery z polskimi znakami diakrytycznymi, gdyż język AC-Logo akce tuje takie litery. - Programy i polecenia w pozostałych systemach oprogramowania w korzystanych w tej książce (w ich standardowej wersji) mogą zawiei nazwy złożone jedynie z liter alfabetu łacińskiego. 2. Zlecenia i komunikaty systemu operacyjnego MS-DOS są pisane także smem maszynowym i wielkimi literami. 3. Pismem pochyłym są pisane m.in.: - pojęcia metajęzykowe w definicjach konstrukcji programistycznych - nazwy opcji i operacji wzięte z oferty arkusza kalkulacyjnego lub nych systemów oprogramowania. 4. Nazwy klawiszy są wyróżnione wzięciem w ramkę. 5. Informacje o nazwach plików zawierających programy na dyskietce zi dują się w tekście obok znaku przypominającego dyskietkę (zobacz ot umieszczonego na marginesie. Pliki mają nazwy pochodzące od nazw gramów a ich rozszerzenia zależą od użytego systemu programowania i procedur w języku AC-Logo są LOG, dla programów w języku Turbo Pć - PAS, a dla arkuszy kalkulacyjnych systemu Quattro Pro - WQ1. Plik wierające programy z rozdziału x są zgrupowane na dyskietce w kartc R0ZDZx. Podziękowania W opracowaniach El zawarliśmy nasze doświadczenia zdobyte w trakcie wadzenia zajęć z elementów informatyki z uczniami III Liceum Ogólnoks cącego we Wrocławiu i innych szkół, z podstaw informatyki z przyszłymi czycielami na niektórych nieinformatycznych kierunkach studiów Uniwers Wrocławskiego oraz na kursach i Studiach Podyplomowych z Informatyki dl uczycieli. Słuchaczom tych zajęć składamy gorące podziękowania za współ] Jesteśmy wdzięczni naszym kolegom z Instytutu, Jerzemu Kucharcz; oraz Jerzemu Szczepkowiczowi, za dyskusje i sugestie dotyczące treści tej k jak i za pomoc w posługiwaniu się systemem TgK, w którym ta książka z Wstęp 15 złożona. Dziękujemy także Grażynie Hardt-Olejniczak i Adamowi Szustalewi- czowi za pomoc przy opracowywaniu rozdz. 6, a Urszuli Gładysz - za prace edytorskie, zwłaszcza nad rozdziałem 6. Dziękujemy również Recenzentom, Pani Iwonie Krajewskiej i Panu Witoldowi Kranasowi oraz Panu Janowi Madeyowi za bardzo wnikliwą lekturę tekstu i wiele cennych uwag, które przyczyniły się do ulepszenia zawartości książki i prezentacji materiału. Panu Zbigniewowi Książczakowi dziękujemy za uwagi dotyczące strony językowej tekstu. Chcielibyśmy podziękować także naszym dwóm współautorom dwóch poprze- dnich wersji tej książki3, Wiktorowi Dańce i Zdzisławowi Jarzębowskiemu, za ich wkład widoczny także w obecnej wersji. Książka jest wynikiem współpracy dość dużego zespołu autorskiego. Autorami rozdziałów są: E. Gurbiel - rozdz. 5, E. Kolczyk - rozdz. 4, H. Krupicka - rozdz. 3, K. Łukojć - rozdz. 2, Z. Płoski - p. 2.4 i rozdz. 8, M. M. Sysło - rozdz. 1 i 7, J. Witkowski - rozdz. 9, R. Zuber - rozdz. 6. Całość zredagował merytorycznie Maciej M. Sysło. Pani Redaktor Annie Szemberg z Wydawnictwa Naukowego PWN dziękujemy za pomoc i życzliwość okazane nam w trakcie powstawania opracowań El w ich ostatecznej postaci. Autorzy Wrocław, 19 sierpnia 1993 3Pełne dane o poprzednich wydaniach tej książki znajdują się na czwartej stronie. 1. CZYM JEST INFORMATYKA ELEMENTY HISTORII 1.1. Czym jest informatyka Informatyka jest najczęściej kojarzona z komputerami, programowaniem oraz algorytmami, a w ostatnich latach również z całą sferą działalności związanej z mikrokomputerami, zwanymi także komputerami osobistymi. Jako najbardziej zwięzłe określenie tego, czym jest informatyka, podaje się, iż jest to dziedzina wiedzy (ang. computer science) i działalności zajmująca się gro- madzeniem, przetwarzaniem i wykorzystywaniem informacji (czyli różnego ro- dzaju danych o otaczającej nas rzeczywistości), a ta obróbka informacji odbywa się za pomocą komputerów. Chociaż główny nacisk w tej definicji jest położony na informację i na różne jej aspekty, to jednak wprost lub pośrednio możemy odnaleźć w niej także wymienione na początku pojęcia: komputery - gdyż są to urządzenia do obróbki informacji, programowanie - gdyż jest narzędziem umożliwiającym i usprawniającym komunikowanie się użytkownika z kompute- rem, algorytmy - gdyż są tymi przepisami, według których przekształcamy in- formacje, by osiągnąć zamierzony cel. Każde z wymienionych pojęć może z kolei posłużyć do podania innej definicji informatyki. I tak, wiele osób za najważniejsze obiekty zainteresowań w informatyce uważa komputery wraz z całą gamą za- gadnień związanych z ich projektowaniem, konstruowaniem i wykorzystywaniem. Jest to zbyt jednostronne, techniczne spojrzenie na informatykę. Najczęściej in- formatyka bywa utożsamiana z programowaniem komputerów, a pośrednio także z językami programowania. Ta książka stara się przekonać, że pogląd ten jest wyraźnym zawężeniem zakresu dziedziny. Nam najbardziej odpowiada następujące określenie informatyki: informatyka jest dziedziną wiedzy i działalności zajmującą się algorytmami 2 — Elementy informatyki 18 1. Elementy historii informatyki Wyróżniliśmy tę ostatnią definicję, gdyż naszym zdaniem najtrafniej oddaji przewodnią myśl większości rozważań na tematy dotyczące informatyki. W tyn określeniu można odnaleźć także pozostałe pojęcia stosowane do definiowani informatyki: komputery - jako urządzenia za pomocą których są wykonywań algorytmy, informację - jako materiał, który przetwarzają i produkują algorytm i programowanie - jako metodę zapisywania algorytmów. Chociaż w tej defin cji główny nacisk jest położony tym razem na algorytmy, pozostałe jej aspekt są nie mniej ważne do właściwego traktowania zarówno algorytmów, jak i cał dziedziny. Znaczenie pojęć: algorytm, program, komputer, informacja omawiamy w na tępnym punkcie na tle ich historycznego rozwoju. 1.2. Elementy historii informatyki Zalew komputerów, który obserwujemy wokół nas, jest jedną z oznak rewolu mikrokomputerowej. Komputery nie pojawiły się jednak nagle i niespodziewar a pojęcia i wiedza składające się na informatykę były gromadzone przez dłu lata wraz z rozwojem innych nauk i działalności człowieka. Chcemy tutaj przybliżyć tylko te wydarzenia i osoby z historii informatj które według nas miały największy wpływ na tempo rozwoju i obecny jej st Naszą uwagę skupimy przede wszystkim na tych faktach, które odegrały najwi szą rolę w rozwoju podstawowych pojęć: algorytm, komputer i programowa: Na zakończenie odniesiemy się także krótko do obecnej, stale rosnącej roli in matyki w społeczeństwie. Pierwsze ślady informatyki można odnaleźć w historii matematyki i to c odległej. Zastanówmy się najpierw, co składa się na matematykę. Wys czy, jeśli rozróżnimy, bez specjalnego zagłębiania się w jej istotę, dwa rod działalności matematycznej: dowodzenie i obliczanie1. Matematyczny dowód uzasadnieniem słuszności faktu sformułowanego najczęściej w ogólnej, abstral nej postaci. Na przykład w twierdzeniu Pitagorasa jest mowa o zależności, spełniają długości boków w dowolnym trójkącie prostokątnym, czyli dotyczy wszystkich takich trójkątów. Za obliczenia zaś przyjęło się uznawać wyŁ nie na liczbach zaznaczonych działań. Dowody są wytworami umysłu noszą duży ładunek oryginalności i niepowtarzalności. Obliczenia natomiast w jej tradycyjnej postaci (tj. zapisywane ołówkiem na kartce papieru) są cig elementarnych działań, których różnorodność jest ograniczona do kilku po wowych operacji arytmetycznych. Bardzo trudno jest znaleźć w otaczaj lrTo rozróżnienie zaciera się ostatnio w wielu przypadkach i w matematyce znanych jes dowodów, które w znacznym stopniu polegają na wykonaniu obliczeń. Istnieją także koi rowe dowody twierdzeń. Od Starożytności do Średniowiecza 19 nas świecie odpowiedniki większości pojęć i pomysłów występujących w dowo- dach, liczby zaś (zwłaszcza naturalne) dają się łatwo przedstawiać za pomocą najróżniejszych obiektów, rzeczy i wielkości. Dlatego od najdawniejszych czasów próbowano pomagać sobie w liczeniu, np. kamieniami. Od Starożytności do Średniowiecza W wykopaliskach między Mezopotamią i Indiami odnaleziono ślady stosowanych już w X wieku p.n.e. systematycznych metod znajdowania wyniku najprostszych operacji za pomocą specjalnie przygotowanych i poukładanych kamieni. Począt- kowo kamienie układano w rzędach na piasku tworząc w ten sposób plansze obli- czeniowe, które nazywamy abakami (lub abakusami). Później zaczęto nawlekać kamienie na pręty, tworząc liczydła, czyli kompletne i przenośne przyrządy do obliczeń. W obu przypadkach, abakusa i liczydła, stan obliczeń określało rozmie- szczenie elementów ruchomych (czyli kamieni) na piasku lub na prętach. Liczydła przeżywały swój renesans w wiekach średnich. Wtedy na przykład ukształtował się japoński soroban w swej obecnej postaci. Rys. 1.1. Japoński soroban Na rys. 1.1. jest pokazany szkic współczesnego sorobanu w pozycji przygo- towanej do rozpoczęcia pracy. Cztery guziki na dole w każdym rzędzie służą do odkładania kolejnych jedności 1, 2, 3 i 4 przez przesuwanie ich w kierunku środka. Przejście od 4 do 5 polega na cofnięciu czterech jedności na pozycje początko- we i przesunięcie górnego guzika do środka. Zachęcamy do opracowania metody dodawania dwóch liczb za pomocą tego liczydła. Soroban jest jeszcze dzisiaj dość powszechnie stosowanym liczydłem w Japo- nii. Jego obsługi, w tym wykonywania na nim czterech podstawowych działań arytmetycznych, nadal uczą się japońskie dzieci w szkole podstawowej. Nierzadko można także spotkać urzędników (np. na poczcie) lub sprzedawców w małych skle- pikach, którzy obliczają należności korzystając z pomocy sorobanu. Soroban - jak każde liczydło - ma wady, które zostały naprawione częściowo w kalkulatorze, a ostatecznie dopiero w komputerach. Służy on bowiem tylko do odnotowania bieżących wyników obliczeń, gdyż nie ma w nim miejsca ani na pamiętanie wy- ników pośrednich, ani na pamiętanie kolejno wykonywanych działań. 20 _. 1. Elementy historii informatyki Cofnijmy się jeszcze do poprzedniej ery. W rozdziale 4 omawiamy metodę w; znaczania największego wspólnego dzielnika dwóch liczb. Metodę tę podał Eukl des, żyjący w latach 400-300 p.n.e., w swoim fundamentalnym dla matematy' (a zwłaszcza dla geometrii) dziele Elementy. Jego metoda jest dzisiaj powszecl nie nazywana algorytmem Euklidesa. Staraliśmy się unikać na początku tej akapitu słowa algorytm, gdyż w czasach, gdy żył i działał Euklides, i przez wie wieków po nim, nie używano jeszcze tej nazwy. Słowo algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego m tematyka, żyjącego na przełomie VIII i IX wieku. Muhammad ibn Musa a -Chorezmi, bo o nim tutaj mowa, jest uznawany za prekursora obliczeniowy! metod w matematyce. Napisał na ten temat kilka dzieł, a z fragmentu tytu jednej z jego ksiąg pochodzi inne jeszcze słowo - algebra. Upowszechnił także s stem dziesiętny i stosowanie zera jako pojęcia i symbolu, z którym wielu żyjący przed nim nie umiało sobie poradzić. Nie wyobrażano sobie bowiem by coś (cz; jakikolwiek znak, np. 0) mogło oznaczać nic. A co to jest algorytm? Nie podamy wyczerpującej odpowiedzi na to pytań Nie udało się bowiem do dzisiaj ująć w jednolite ramy jednego pojęcia wszystki tych procesów, które są opatrywane nazwą algorytm. W dalszych rozważania będziemy przyjmować, że algorytm jest przepisem rozwiązywania postawionego zadania, bę- dącym dokładnie określonym układem elementarnych instrukcji wraz z porządkiem ich wykonywania. Każda instrukcja ma precyzyjnie określoną interpretację za pomocą podstawowych operacji arytme- tycznych i logicznych, a jej wykonanie jest skończone i ma jednoznacz- nie określony efekt końcowy2. Jako elementy komunikacji ze światem w algorytmie można wyróżnić: dane, na których są wykonywane obli- czenia i wyniki, które są oczekiwanym rezultatem działań. Algorytm, jako opis sposobu rozwiązywania zadania jest często zapisywć w języku programowania by umożliwić jego wykonanie za pomocą kompute Dzięki precyzji określenia danych i wyników (w algorytmie i w odpowiadając mu programie), algorytm może być stosowany nawet w sytuacjach, gdy oso zainteresowanej rozwiązaniem nie jest znane dokładne jego działanie - wystari znajomość postaci danych i interpretacji wyników. Wiek XVII i XVIII Na początku XVII wieku John Neper opublikował najpierw swoje dzieło o lo rytmach a następnie przedstawił system wspomagający wykonywanie mnożei 2W tej definicji niezupełnie mieszczą się algorytmy niedeterministyczne i probabilistyc o których jednak nie mówimy w tej książce. Wiek XVII i XVIII 21 zwany pałeczkami Nepera. Genialność tego systemu polegała na sprowadzeniu mnożenia do serii dodawań. Pomysł Nepera wykorzystało wielu konstruktorów urządzeń liczących, jemu współczesnych i żyjących po nim. Za twórcę pierwszej w historii mechanicznej maszyny do liczenia jest uzna- wany Wilhelm Schickard (1592-1635), który przez długie lata był zupełnie za- pomniany. Schickard opisał projekt swojej czterodziałaniowej maszyny, wykorzy- stującej udoskonalone pałeczki Nepera w postaci walców, w liście do Keplera, któremu miała ona pomóc w jego astronomicznych (dosłownie i w przenośni) rachunkach. Niestety jedyny zbudowany egzemplarz maszyny spłonął w nie- wyjaśnionych okolicznościach, a dzisiejsze jej repliki zostały odtworzone dopiero niedawno na podstawie opisu z listu do Keplera. W XVII wieku żyli i tworzyli wielcy matematycy Gottfried Wilhelm Leib- niz (1646-1716) i Blaise Pascal (1623-1662). Leibniz jest uznawany za jednego z twórców rachunku różniczkowego i całkowego, a osiągnięcia Pascala można znaleźć w bardzo wielu działach nauk ścisłych. Dobrze jest znany trójkąt Pa- scala, który tworzą współczynniki w dwumianie Newtona dla kolejnych wykładni- ków potęg. Zainteresowania teoretyczne nie przeszkodziły tym światłym umysłom na zajęcie się także praktycznymi obliczeniami i dzisiaj obaj są znani również ze zbudowanych przez siebie maszyn liczących. Pascal zainteresował się zbudowaniem maszyny liczącej z myślą o dopomoże- niu swojemu ojcu, który był poborcą podatkowym. Wyprodukowano około 50 egzemplarzy Pascaliny - maszyny według pomysłu Pascala. Kilka egzempla- rzy istnieje w muzeach do dzisiaj; część z nich była przeznaczona do obliczeń w różnych systemach monetarnych, a część - dla różnych miar odległości i po- wierzchni (z przeznaczeniem dla geodetów). Pascal, który zbudował maszynę wykonującą tylko dwa działania (dodawanie i odejmowanie) przez ponad trzysta lat uchodził niesłusznie za wynalazcę pierwszej mechanicznej maszyny do liczenia. Schickard i Pascal wprowadzili w swoich maszynach mechanizm do przeno- szenia cyfr przy dodawaniu i odejmowaniu. Obie maszyny miały także pewne możliwości zapamiętywania niektórych wyników pośrednich. Leibniz odkrył na nowo pochodzący ze starożytnych Chin system dwójkowy (zwany także binarnym) do zapisu liczb. Przypisuje się jemu także zbudowanie pierwszej mechanicznej maszyny mnożącej. Chociaż w tym czasie istniała już Pascalina i Leibniz miał możność zapoznania się z nią w Paryżu, projekt swojej "żywej ławy do liczenia" opisał przed pierwszą wizytą w Paryżu. W maszynie tej wprowadził wiele części, które zostały użyte w późniejszych maszynach biuro- wych. Leibniz wiązał z systemem binarnym także swoje idee filozoficzne. Wierzył bowiem, że język matematyki, za pomocą skończonej liczby symboli i pojęć, może wyrazić wszystkie możliwe twierdzenia (lub ogólniej, słuszne sądy). Dopiero Kurt Godeł wykazał w latach trzydziestych naszego wieku, że jest to niewykonalne. 22 1. Elementy historii informatyki Maszyny Schickarda, Pascala i Leibniza wymagały od użytkownika manual- nej pomocy w wielu czynnościach związanych z kolejnymi krokami obliczeń. Za pomocą tych maszyn nie było jeszcze można w pełni automatycznie i w całości wykonać prostego działania na dwóch liczbach. W tym miejscu wypada wspomnieć o udziale naszego rodaka w dziele tworze- nia maszyn liczących. Abraham Stern (1769-1842), z zawodu zegarmistrz, wy- konał serię maszyn, które poza czterema działaniami podstawowymi, wyciągał} także pierwiastki kwadratowe. Jedna z jego maszyn, raz uruchomiona, potrafił? wykonać za pomocą mechanizmu zegarowego wszystkie operacje bez ingerencj człowieka. Maszyny skonstruowane przez Sterna okazały się jednak mało prak tyczne ze względu na wyjątkowo delikatną budowę. Charles Babbage (1791-1871) Za najwybitniejszego twórcę maszyn liczących, żyjącego przed erą elektroniczni uważa się Anglika Charlesa Babbage'a. Około 1820 r. spotkał on francuskie^ barona de Prony, który dla sporządzenia tablic logarytmicznych i trygonom trycznych utworzył specjalną "manufakturę logarytmów" i wzorując się na id ach szkockiego ekonomisty Adama Smitha zastosował podział pracy. W ty celu wynajął 6 wybitnych matematyków (wśród nich był Legendre) do oprać wywania formuł obliczeń, 8 przeszkolonych matematyków do przygotowywali poszczególnych etapów obliczeń i 60 rachmistrzów. Ci ostatni mieli jedynie d dawać i odejmować. Dzięki temu praca, która zajęłaby całe jedno życie, zost; ukończona w kilka lat. Babbage posunął się dalej i postanowił zbudować n szynę liczącą, która mogłaby wyręczyć człowieka i automatycznie wykonywać ] wtarzające się działania. Swoją pierwszą maszynę nazwał maszyną różnico\ gdyż wykonywała obliczenia metodą różnicową3. Nie będziemy dokładnie opisywać tutaj metody różnicowej. Zilustrujemy tylko na przykładzie obliczania wartości funkcji y = x2 dla kolejnych argumeni a; = l,2,3,... Zauważmy następującą prawidłowość: kwadrat kolejnej liczby naturalnej jest sumą kwadratu poprzedniej liczby naturalnej i kolejnej nieparzystej liczby naturalnej. Korzystając z tej zależności otrzymujemy schemat obliczeń przedstawi na rys. 1.2 (strzałki oznaczają kolejność obliczeń i przekazywania wyznaczał wartości). Zatem do policzenia kwadratów kolejnych liczb naturalnych wystarczy: 3Pierwszy projekt automatycznej maszyny do wykonywania obliczeń metodą różnicową J.H.Miiller w 1786 roku - jednak wydaje się, że ani baron de Prony, ani Babbage nie znal Miillera. n Charles Babbage 23 1. Ustawić O, 1 i 2 jako początkowe wartości. 2. Dla policzenia kwadratu kolejnej liczby naturalnej, wykonać dwa dodawa- nia: - otrzymać kolejną liczbę nieparzystą przez zwiększenie o dwa poprze- dniej liczby nieparzystej (jest to wykonywane w trzeciej i czwartej kolumnie na rys. 1.2), — otrzymaną liczbę nieparzystą dodać do kwadratu poprzedniej liczby naturalnej (dwie pierwsze kolumny na rys. 1.2). kolejne kwadraty kolejne liczby nieparzyste =9+7 — początkowe wartości Rys. 1.2. Obliczanie kwadratów kolejnych liczb naturalnych Podaliśmy bardzo prosty przykład obliczeń wykonanych metodą różnicową. Dla uzasadnienia znaczenia tej metody w automatycznych obliczeniach dodajmy, że w podobny sposób można tworzyć tablice wartości dla większości funkcji ele- mentarnych spotykanych w obliczeniach. W tym celu należy skorzystać z wie- lomianu, który dobrze przybliża tablicowaną funkcję oraz policzyć bezpośrednio kilka jej pierwszych wartości. Wszystkie następne działania są już tylko dodawa- niami pewnych liczb tworzonych także tylko za pomocą dodawań. I właśnie ten ostatni etap obliczeń automatyzowała maszyna różnicowa. Babbage konstruował swoją pierwszą maszynę przez ponad 10 lat. Trapiony jednak wieloma kłopotami rodzinnymi i finansowymi oraz nie mogąc do końca porozumieć się ze swoim głównym wykonawcą-konstruktorem Clementem, za- przestał dalszych prac nad maszyną różnicową w 1842 roku. Zmontowaną część maszyny (podobno nadal sprawną!) można oglądać w Muzeum Nauk w Lody- nie. Należy dodać, że w odróżnieiu od maszyn Leibniza i Pascala, po ręcznym ustawieniu początkowego stanu, dalsze działania maszyny różnicowej nie wyma- gają już żadnej ingerencji użytkownika poza kręceniem korbą. Prace Babbage'a zainspirowały wielu jemu współczesnych, którzy, jak na przykład Szwedzi George 24 1. Elementy historii informatyki i Edward Scheutzowie, często z większym powodzeniem ukończyli swoje, możi mniej ambitne ale nadal praktyczne konstrukcje maszyn różnicowych. Ale Babbage nie poprzestał na próbie skonstruowania maszyny różnicowe; Marzył o maszynie, która mogłaby rozwiązywać bardziej złożone zadania. Ta narodził się jeszcze w trakcie prac nad maszyną różnicową pomysł zbudowani maszyny analitycznej, którym Babbage żył do śmierci. Było to przedsięwzięć: czysto abstrakcyjne - przewidywane przeszkody techniczne i trudności finansów nie pozwoliły nawet na rozpoczęcie prac konstrukcyjnych . W projekcie Babbaj zawarł jednak wiele pomysłów zrealizowanych dopiero we współczesnych kompi terach. Między innymi rozdzielił pamięć (zwaną magazynem) od jednostki licząc (młyna), czyli miejsce przechowywania danych od jednostki wykonującej na nii działania. Obie te części maszyny analitycznej miały być sterowane za pomo< dodatkowego urządzenia kontrolnego, które otrzymywało polecenia na karta perforowanych, udoskonalonych i rozpowszechnionych przez Jacąuarda do pi gramowania maszyn tkackich. Można więc uznać maszynę analityczną Babbeg< za pierwszy pomysł kalkulatora sterowanego programem zewnętrznym. Opis działania maszyny analitycznej trafił w ręce Ady (jej pełne nazi sko: Ada Augusta hrabina Lovelace), córki Byrona, znanej w owych czas? z błyskotliwego umysłu. Urzeczona doskonałością projektu uważała, że "... n szyna analityczna tkać będzie wzory algebraiczne, tak jak krosna Jacąuarda tk liście i kwiaty ...". Nie czekając na skonstruowanie maszyny (czego jak wie i tak by się nie doczekała), Ada zajęła się sporządzaniem opisów jej używa do rozwiązywania konkretnych zadań obliczeniowych. Opisy te nazwalibyś dzisiaj programami, dlatego uważa się ją za pierwszą programistkę komputer Dla uczczenia zasług Ady na tym polu nazwano jej imieniem jeden z najbard uniwersalnych języków programowania. Przełom XIX i XX wieku Koniec XIX wieku był początkiem rozwoju urządzeń mechanograficznych, któi głównym przeznaczeniem było usprawnienie rachunków statystycznych, ksi wych i biurowych. Zaczęło się w Stanach Zjednoczonych od Hermana Hc ritha, który postanowił zautomatyzować prace statystyczne związane ze sp ludności przeprowadzanym wtedy w Stanach co dziesięć lat. Hollerith sięgnf elektryczność, jako źródło impulsów i energii, rozwinął postać karty perforow; na której zapisywano dane i zbudował elektryczny czytnik-sorter kart. Oli mim sukcesem Holleritha okazał się spis w 1890 roku, którego wyniki zo 4Po śmierci Babbage, projekty maszyny analitycznej odziedziczył jego syn Henry, ktć ich podstawie skonstruował tzw. młyn maszyny, odpowiadający jednostce liczącej w dzisie komputerach. Projekty maszyny analitycznej i prototyp młyna są przechowywane w M\ Nauk w Londynie. Alan Turing 25 całkowicie opracowane za pomocą jego urządzeń na podstawie danych zebranych na jego kartach. W następnych latach Hollerith dostarczał lub wypożyczał swoje urządzenia do przeprowadzenia spisów w wielu krajach, w tym także w Europie, między innymi w Rosji. Na przełomie XIX i XX wieku powstało wiele firm, które początkowo ofe- rowały maszyny sterowane kartami perforowanymi i z latami zyskiwały na swo- jej potędze a wiele z nich przetrwało do dzisiaj, jak na przykład IBM, Buli, Remington-Rand, Burroughs, a także NCR (kasy) i Bell (telefony). Udoskonalona i znormalizowana karta perforowana przez wiele dziesięcioleci była uniwersalnym nośnikiem informacji, a pierwsze maszyny mechaniczne do przetwarzania danych zapoczątkowały stale rosnący popyt na przetwarzanie infor- macji. Wniosło to także zmiany w stosunkach międzyludzkich, a w szczególności między państwem (posiadaczem maszyn do obróbki informacji) i obywatelem. Początek XX wieku Od przełomu XIX i XX wieku można zaobserwować wśród matematyków wzrost zainteresowania problemami obliczeniowymi i obliczalnością. Dla przykładu, wiel- ki matematyk niemiecki David Hilbert (1862-1943), wśród wielu problemów naji- stotniejszych dla rozwoju matematyki w XX wieku, umieścił także pytanie o ist- nienie uniwersalnej metody znajdowania pierwiastków równań o współczynnikach całkowitych będących liczbami całkowitymi. Zainteresowania te doprowadziły do powstania wielu teorii, których celem było dostarczenie teoretycznych podstaw obliczeń. W teoriach tych można na przykład ściśle określić, co to jest algorytm. Przy badaniu wzajemnych związków między teoretycznymi modelami obliczeń okazało się, że zdecydowana ich większość jest równoważna sobie, obejmuje bowiem te same klasy zadań dających się rozwiązy- wać za pomocą konstruowanych w tych teoriach algorytmów. Alan Turing (1912-1954) Wśród modeli obliczeń powstałych w pierwszej połowie XX w. największą po- pularność zdobyły maszyny Turinga. W swojej fundamentalnej pracy z 1936 roku Alan Turing bardzo przystępnie opisał tok myślenia prowadzący od obliczeń wykonywanych ręcznie do obliczeń wykonywanych przez bardzo prostą maszynę. Przytoczymy tutaj ten opis. Obliczenia ręczne są najczęściej wykonywane na pokratkowanej kartce pa- pieru, której pojedyncze kratki są wypełniane cyframi i symbolami działań. Dys- ponujemy tylko skończoną liczbą znaków (cyfr, np. 0 raz 1 i symboli działań), które mogą być wpisywane w kratki. To, co robimy w ustalonej chwili, zależy od znaków, które obserwujemy i od działania, jakie podjęliśmy. Możemy przyjąć. 26 1. Elementy historii informatyki że liczba kratek obserwowanych w danej chwili jest ograniczona. Przejrzenie zaś większej ich liczby sprowadza się do wykonania ciągu obserwacji. Możemy także założyć, że liczba wszystkich stanów, w jakich może znaleźć się nasz umysł wy- konujący obliczenia, chociaż duża, jest skończona. Turing doszedł do koncepcji swojej maszyny wprowadzając pewne uproszcze- nia i uściślenia w działaniach na kartce i nad nią. Po pierwsze, zapis obliczer na kartce papieru (a dokładniej na dwuwymiarowym układzie kratek) możne sprowadzić do zapisu na jednowymiarowej pokratkowanej kartce, czyli na taśmi< podzielonej na kratki. Wystarczy w tym celu treść obliczeń wypełniających kartk' zapisać wierszami. Traci się przy tym na czytelności, ale zyskuje redukcję wy miaru kartki. Po drugie, umysł wykonujący obliczenia można zastąpić prze obiekt bardziej fizyczny zwany głowicą, która znajduje się nad taśmą, może si poruszać w obie strony taśmy, a w danej chwili widzi jedynie symbol umieszczon w kratce, nad którą zawisła. Działanie głowicy jest określone przez ustalony zbić instrukcji, zgodnie z którymi może poruszać się w lewo, w prawo lub stać w mie scu, potrafi rozpoznawać symbole i może zmieniać zawartość kratki, nad którą s znajduje. Wykonanie instrukcji przez maszynę Turinga jest działaniem głowic uzależnionym od stanu, w jakim się znajduje i co widzi. Obliczenia wykonywane za pomocą maszyny Turinga zależą od początkowe zapisu symboli na taśmie i od przyjętego zestawu dozwolonych instrukcji. Z tem działa ona podobnie jak dzisiejsze komputery - wyniki obliczeń zależą zapisanych w pamięci komputera danych i od zestawu wykonywanych intrukc Zawartość taśmy po zatrzymaniu się maszyny zależy od obu tych czynnikć Nieodparcie nasuwa się pytanie o to, co możemy policzyć za pomocą tak p stych maszyn. Okazuje się, że bardzo wiele. Sam Turing sformułował tezę, iż maszynie tego typu można zrealizować każdy algorytm. Do dzisiaj nie obalono tezy. Zauważmy, że w związku z tym można przyjąć, iż algorytmem jest dowo opis wykonania obliczeń na maszynie Turinga. Analizując moc swoich maszyn, Turing doszedł jednak do wniosku, że istn funkcje, których wartości nie mogą one obliczać. Nakreślił w ten sposób grai możliwości obliczeń. Działo się to w latach, gdy w matematyce, inny gen: XX wieku, Kurt Gódel nakreślił granice możliwości dowodu matematyczni Wykazał on bowiem, że nie z każdego skończonego układu aksjomatów mc wyprowadzić wszystkie zgodne z nimi (czyli prawdziwe) fakty. Wspomnijmy tutaj jeszcze o dwóch innych dziedzinach działalności Turi ściśle związanych z automatyzacją obliczeń i komputerami. W latach II w światowej Turing został włączony do grupy specjalistów zajmujących się w \ kiej Brytanii deszyfracją kodów Enigmy - maszyny, którą Niemcy używa kodowania meldunków i rozkazów rozsyłanych swoim jednostkom na wszysi frontach. W 1941 roku działalność tej grupy przyczyniła się do zredukowania Pierwsze komputery 27 tyjskich strat na morzach o 50%. Brytyjscy specjaliści korzystali z materiałów (wśród których był egzemplarz Enigmy oraz maszyna deszyfruj ąca zwana bombą) przekazanych im w 1939 roku przez grupę Polaków kierowaną przez Mariana Re- jewskiego, zajmujących się od pięciu lat skonstruowaniem maszyny deszyfrującej. Chociaż Brytyjczycy udoskonalili maszynę deszyfrującą otrzymaną od Polaków, pozostawała ona nadal maszyną mechaniczną i jej działanie nie nadążało za ciągle udoskonalanymi i zmienianymi przez Niemców egzemplarzami Enigmy. Ocenia się, że w szczytowym okresie II wojny światowej Niemcy używali ponad 70 tysięcy maszyn szyfrujących Enigma. Prace nad maszyną deszyfrującą Enigmę przyczyniły się do powstania pod koniec wojny w Wielkiej Brytanii kalkulatorów elektronicznych5. Powstało kilka wersji maszyny o nazwie Coloss, których głównym konstruktorem był T.H. Fo- wers. Były to już maszyny elektroniczne, w których zastosowano arytmetykę b