Алгоритмы и автоматическое решение задач, Н.А. Трахтенброт [PWN 1961]

Tytuł: Algorytmy i automatyczne rozwiązywanie zadań, seria wydawnicza - „?”.

Autor: B.A. Trachtenbrot, tłumaczył Paweł Szeptycki.

Wydawca: Państwowe Wydawnictwo Naukowe, Warszawa 1961, wydanie I. 103 strony, tabele, wzory w tekście, oprawa miękka, format 12,5x19,5 cm.

Stan dobry - ogólne podniszczenie i zabrudzenia okładki oraz środka (okładka ponownie doklejona do bloku) – poza tym stan OK.

„Algorytmy i automatyczne rozwiązywanie zadań” - W książce B.A. Trachtenbrota rozważa się w przystępny sposób podstawowe zagadnienia teorii algorytmów i jej związek ze współczesną matematyką maszynową. Autor podaj e szczegółowo historyczny rozwój pojęcia algorytmu, zasady działania szybkoliczących maszyn matematycznych, zasady programowania, schemat maszyn Turinga oraz zagadnienia nie dające się rozwiązać za pomocą algorytmów.

Książka jest przeznaczona dla uczniów starszych klas szkół średnich, nauczycieli, inżynierów i tych wszystkich, którzy interesują się perspektywami zastosowań nowej techniki rachunkowej.

„Algorytmy i automatyczne rozwiązywanie zadań”. Przedmowa - Niniejsza książka, będąca elementarnym wstępem do teorii algorytmów, jest poświęcona wyjaśnieniu jednego z podstawowych pojęć matematyki — pojęcia algorytmu; rozpatruje się w niej zakres zagadnień leżących na pograniczu logiki matematycznej i teorii automatycznych maszyn matematycznych.

Książka powstała z popularnych wykładów, które autor wygłaszał w różnych kołach w mieście Penza począwszy od roku 1951, a także z pracy pod tym samym tytułem, napisanej przez niego dla czasopisma „Matiematika w szkolie 4-5” (1956).

„Algorytmy i automatyczne rozwiązywanie zadań”. Wstęp - W ostatnich latach nastąpił znaczny rozwój szybko działających maszyn matematycznych, które stosuje się obecnie do rozwiązywania najróżnorodniejszych zagadnień matematycznych i logicznych. Charakterystyczna cecha tych maszyn odróżniająca je od dotychczasowych maszyn obliczeniowych polega na tym, że przy wykonywaniu swych czynności, poczynając od momentu wprowadzenia danych początkowych i programu, pracują one bez jakiegokolwiek udziału człowieka aż do wydania ostatecznego wyniku. Wydajność współczesnych automatycznych maszyn elektronowych jest ogromna: mogą one wykonywać do 20000 operacji arytmetycznych w ciągu sekundy (¹współczesne maszyny cyfrowe wykonują do miliona operacji na sekundę - przypisek redakcji wydania polskiego), co przynajmniej 10 razy przekracza to, co może wykonać w ciągu roboczo-dnia wykwalifikowany rachmistrz pracujący na dobrym arytmometrze klawiszowym (²z punktu widzenia ilości wykonanych operacji.). Zakres zastosowania maszyn automatycznych stale wzrasta: maszyny rozwiązują skomplikowane układy równań, tłumaczą z jednego języka na drugi, grają w szachy itd. Istnieją duże perspektywy zastosowania w przemyśle maszyn automatycznych kierujących całym procesem technologicznym w skali dużej fabryki. Poza tym możliwość szybkiego, i niezawodnego opracowania matematycznego, a także analizy danych doświadczalnych) stwarza przesłanki dla pojawienia się nowych, przedtem niedostępnych metod badawczych w różnych działach nauki.

Obecnie wszyscy już przyznają, że automatyczne maszyny matematyczne stanowią potężne narzędzie, zdolne nie tylko ułatwić człowiekowi pracę umysłową, lecz nawet w pełni go uwolnić od pewnych rodzajów żmudnej i wytężonej pracy umysłowej.

Ponadto uzyskane sukcesy mogą wywołać i rzeczywiście wywołują wiele nieusprawiedliwionych złudzeń i zgoła fantastycznych przewidywań na temat wszechmocy maszyn. Należy w szczególności wskazać na podniesiony w prasie zagranicznej szum o „gigantycznym mózgu elektronowym”, o automatach zdolnych rozwiązać wszelkie zadania i zastąpić twórczą pracę uczonego.

W związku z powyższymi okolicznościami ostro zarysowuje się aktualny problem.: jakie rodzaje pracy umysłowej mogą wykonywać automatyczne maszyny matematyczne. Zagadnienie to jest rozpatrywane z określonego punktu widzenia we współczesnej teorii algorytmów, będącej ważną gałęzią logiki matematycznej. Dla logiki matematycznej charakterystyczne jest rozpatrywanie istoty takich pojęć, jak proces obliczeniowy, dowód matematyczny, algorytm itd. Już kilka lat przed stworzeniem współczesnych elektronowych maszyn matematycznych, w logice matematycznej opracowano ściśle pojęcie algorytmu i ogólny schemat automatycznej maszyny matematycznej (maszyna Turinga), a także wyjaśniono ścisły związek między algorytmami i maszynami. Pozwoliło to ustalić szereg, ważnych twierdzeń wyjaśniających istotę procesów realizowanych w maszynach automatycznych, w szczególności udowodniono ściśle istnienie zagadnień, których nie można rozwiązać za pomocą maszyn. Niniejsza książka jest poświęcona wyjaśnieniu związku między algorytmami i maszynami.

W paragrafach 1-3 wyjaśnia się na przykładach, czym jest algorytm i buduje się algorytmy dla rozwiązania pewnych klas zadań matematycznych i logicznych.

W paragrafach 4-5 są wyłożone zasady budowy elektronowych maszyn matematycznych oraz układania programów, tj. algorytmów dostosowanych do realizacji w maszynach.

W paragrafach 6-11 omówiono szereg ważnych problemów teorii algorytmów, przy czym za podstawowe pojęcie teorii obrano pojęcie maszyny Turinga.

Czysto techniczna żmudność wielu dowodów nie pozwala podać ich w całości w tak małej książeczce. Dlatego też rezygnujemy w niej ze ścisłości i zupełności wykładu, co jednak, jak się nam wydaje, nie utrudnia, a przeciwnie ułatwia lepsze wyjaśnienie istoty sprawy. Dla pełności obrazu powiedziano o tym trochę w sposób przeglądowy (patrz §6.).

Uczynimy jeszcze jedną uwagę. Współczesne maszyny sterowane automatycznie nazywa się elektronowymi, ponieważ ich najważniejsze części są zbudowane z lamp elektronowych. Zastosowanie techniki elektronowej daje dużą oszczędność czasu w realizacji poszczególnych operacji wykonywanych przez maszynę. Jednak automatyczne sterowanie nie wynika z zastosowania właśnie techniki elektronowej. W zasadzie lampy elektronowe można by było zastąpić nawet urządzeniami mechanicznymi, tzn. można by zbudować mechaniczną maszynę matematyczną sterowaną automatycznie, która byłaby zdolna rozwiązywać te same zagadnienia, co maszyna elektronowa (co prawda znacznie wolniej). Tak więc nie należy rozpatrywać powstania nowoczesnych maszyn matematycznych jako wyniku rozwoju tylko techniki elektronowej. Co więcej, pierwszy opis ogólnego schematu automatycznej maszyny matematycznej (maszyna Turinga, por. §7.) został podany w teorii algorytmów już w roku 1936 jako opis urządzenia mechanicznego. Pierwsze faktycznie skonstruowane maszyny (1940 r.) były elektromechaniczne.

W niniejszej książce przy opisie budowy maszyn nie będziemy zatrzymywać się nad szczegółami technicznymi, skupiając uwagę na rozpatrzeniu zasad współdziałania poszczególnych części maszyny. Podejście to odpowiada zasadniczemu celowi książki, polegającemu na wyjaśnieniu matematycznych i logicznych możliwości maszyny, a nie na pokazaniu technicznej strony zagadnienia.

Spis treści:

Przedmowa;

Wstęp;

• §1. Algorytmy liczbowe;
• §2. Algorytmy dla rozwiązywania zadań logicznych;
• §3. Zagadnienie słów;
• §4. Maszyna matematyczna ze sterowaniem automatycznym;
• §5. Program (algorytm maszynowy);
• §6. Konieczność uściślenia pojęcia algorytmu;
• §7. Maszyna Turinga;
• §8. Realizacja algorytmu w maszynie Turinga;
• §9. Podstawowa hipoteza teorii algorytmów;
• §10. Uniwersalna maszyna Turinga;
• §11. Problemy nierozwiązywalne algorytmicznie;

Uwagi końcowe.

- Polecam!