Komputery jako narzędzie rozwiązywania

naszych problemów - garść podstawowych

informacji

Andrzej Sendlewski

6 października 2010

1 WSTĘP

Od zarania dziejów informacja i jej przetwarzanie było, i jest obecnie jedną z podstawowych działalności człowieka. Z uwagi na wzrastającą ilość informacji do przetworzenia i omylność człowieka, usilnie i z coraz większym po-wodzeniem konstruowano automaty ułatwiające człowiekowi tę działalność.

W drugiej połowie XX wieku komputery stały się nieodłączną częścią na-szego codziennego życia. Wykorzystujemy je w przemyśle, bankowości, tele-komunikacji, edukacji - praktycznie wszędzie. W komputery wyposażone są samochody, kamery i inne urządzenia codziennego użytku. Komputer osobi-sty stał się w latach 90-tych zwykłym elementem wyposażenia wielu domów, gdzie zastępuje maszynę do pisania, kalkulator, notatnik; przy jego pomocy szybko i sprawnie wykonuje się bardzo wiele czynności. Mówimy obecnie o informatyzacji społeczeństw.

Co to takiego INFORMATYKA?

INFORMATYKA to dziedzina działalności człowieka służąca au-tomatyzacji przetwarzania i gromadzenia informacji.

Tworzą ją:

1

• dynamicznie rozwijający się przemysł produkcji komputerów o różno-rakim przeznaczeniu i coraz większych możliwościach technicznych oraz infrastruktura połączeń pracujących komputerów (sieci),

• gałąź nauki zwana COMPUTER SCIENCE badająca wszelkie aspekty wykorzystania komputerów.

Celem tego wykładu będzie nauczenie się co zrobić, aby daną informację przekształcić do żądanej postaci przy pomocy komputera (inaczej: aby dany problem rozwiązać za pomocą komputera).

2 Ogólna charakterystyka komputera

Potoczne określenie komputera jako dużego kalkulatora potrafiącego wykonywać skomplikowane operacje arytmetyczne jest dużym uproszczeniem.

Współczesne komputery potrafią jednak dużo więcej. Ogólnie można powie-dzieć, że komputery wykonują operacje na symbolach reprezentujących róż-

nego rodzaju informacje. Przez informację rozumiemy wszelkiego rodzaju dane (nie tylko liczbowe), fakty, zależności pomiędzy badanymi obiektami, idee niezależnie od postaci, w jakiej występują.

Komputer jest urządzeniem gromadzącym i przetwarzającym informacje.

SCHEMAT DZIAŁANIA KOMPUTERA

Informacja do przetworzenia

DANE

SYSTEM

KOMPUTEROWY

Informacja przetworzona

WYNIKI

2

Komputer wykonuje automatycznie pewien skończony proces, który od DANYCH prowadzi do WYNIKÓW. Proces ten polega na manipulacjach na symbolach reprezentujących informację i odbywa się zgodnie z pewnym przepisem zwanym ALGORYTMEM.

Komputery można scharakteryzować jako urządzenia:

• automatyczne - komputery przetwarzają informacje bez konieczności ingerencji człowieka w sam proces przetwarzania.

• uniwersalne - komputery mogą wykonać wszystkie zadania możliwe do zapisania w formie algorytmu. Interpretacja danych i otrzymanych wyników może dotyczyć różnych dziedzin życia. Rozwiązując problem komputer manipuluje symbolami, które reprezentują dany problem bez przypisywania specyficznego znaczenia tym symbolom. Mogło więc by się wydawać, że przy pomocy komputera można zrobić wszystko. W

tym miejscu podkreślić jednak należy, że

NIE WSZYSTKIE PROBLEMY

MOŻNA ROZWIĄZAĆ

PRZY POMOCY KOMPUTERA

Od lat trzydziestych ubiegłego stulecia, a więc na długo przed zbudo-waniem pierwszego komputera, wielu matematyków (między innymi: Church, Gëdel, Kleene, Post, Turing) starało się formalnie opisać klasę funkcji, które można mechanicznie obliczyć. Używając różnych forma-lizmów określili równoważnie tę sama klasę funkcji, tzw. funkcje czę-

ściowo rekurencyjne. Istnieje wiele świadectw na to, że klasa ta jest równoważna klasie funkcji obliczalnych przez komputery.

• elektroniczne - określenie to dotyczy części składowych komputera.

z tych powodów komputery dzieli się na generacje (podział ten odpo-wiada okresom rozwoju techniki komputerowej):

– komputery zerowej generacji, zbudowane na przekaźnikach elek-tromagnetycznych (np. pierwszy na świecie komputer ze sterowaniem automatycznym Ź3”i pierwszy amerykański ”MARK-I”),

3

– komputery pierwszej generacji, w których zastosowano lampy elek-tronowe (pierwszymi na świecie komputerami tej generacji były -

ĆOLOSSUS-Iź 1943 i ENIACź 1946),

֒

– komputery drugiej generacji skonstruowane w technice tranzysto-rowej (model ŻCA 501ź 1959 był pierwszym komputerem całko-

wicie tranzystorowym),

– komputery trzeciej generacji, w których zastosowano układy scalone małego (SSI) lub średniego (MSI) stopnia scalenia, generację tę zapoczątkował francuski ”MICRAL”w 1972,

– komputery czwartej generacji, w których zasadniczymi elemen-tami są układy scalone o dużym (LSD) lub bardzo dużym (VLSI)

stopniu scalenia.

– Komputery wyższych generacji są obecnie w fazie projektów. Trwają prace badawcze nad komputerami optycznymi, neurokomputerami,

a nawet komputerami kwantowymi. Przewiduje się, że komputery

piątej generacji będą produkowane jeszcze w pierwszych latach XXI w. Powszechnie zakłada się, że ich moc obliczeniowa powinna być co najmniej 30 razy większa od komputerów czwartej generacji. Przyjmuje się, że prawa fizyki nie nakładają żadnych ograni-czeń na szybkość, niezawodność i pojemność pamięci komputerów.

Każda nowa generacja jest mniejsza, szybsza i tańsza od poprzed-niej.

• cyfrowe - informacje reprezentuje się wewnętrznie jako liczby binarne.

3 Algorytmy

Słowo algorytm jest fonetyczną wariacja na temat nazwiska

Abu Ja’far Mohammed ibu-Musa al-Khowarizmi

arabskiego matematyka, który żył w IX wieku i badał zbiór reguł algebraicz-nych rządzących wykonywaniem operacji arytmetycznych na liczbach dzie-siętnych.

4

ALGORYTM to skończony ciąg dobrze określonych i jednoznacz-nych instrukcji (rozkazów) prowadzących od DANYCH do WY-

NIKÓW, z których każda musi być wykonywana mechanicznie w

skończonym czasie.

Przyjrzyjmy się bliżej pojęciom, jakie w tej definicji się pojawiają. Algorytm to skończony ciąg instrukcji. Zbiór instrukcji jest zatem uporządkowany (ważna jest kolejność). Instrukcje muszą być dobrze określone i jednoznaczne.

Musimy mieć określoną tzw. bazę algorytmiczną czyli zbiór danych i instrukcji podstawowych oraz reguł rozstrzygających poprawność każdej instrukcji. Instrukcje mają być wykonywane mechanicznie, tzn. w trakcie dzia-

łania algorytmu ingerencja z zewnątrz jest zbędna. Każdy algorytm musi zakończyć działanie w skończonym czasie, czyli wszystkie instrukcje muszą mieć jednoznacznie określone i zdeterminowane zakończenie. Z algoryt-mem mamy związane też takie pojęcia jak: DANE i WYNIKI - rozwiązanie problemu. Wykonanie instrukcji algorytmu powinno gwarantować osiągnięcie zakładanych wyników.

5

Przykład 1. Włoska Fantazja.

Składniki: 1 budyń o smaku waniliowym,

0,5 litra mleka,

1 łyżeczka masła,

1 łyżka rodzynek,

1 łyżka posiekanych orzechów włoskich,

1 łyżka smażonej skórki pomarańczowej.

Przygotowanie: Z pół litra mleka odlać pół szklanki, wsypać zawartość to-rebki i dobrze wymieszać. Resztę mleka zagotować. Do gotującego się mleka dodać masło i wlać rozrobiony proszek. Gotować około pół minuty ciągle mie-szając. Do gotowego budyniu dodać wypłukane wcześniej rodzynki, posiekane orzechy i skórkę pomarańczową. Całość dokładnie wymieszać i przełożyć do pucharków. Podawać po ostygnięciu.

Zwróćmy uwagę na fakt, że przepis ten składa się z dwóch części: opisu obiektów, którymi będziemy się zajmować i opisu czynności, które będziemy wykonywać (jak zobaczymy później podobna będzie struktura programu w języku PASCAL: program taki będzie miał cześć deklaracyjną i operacyjną).

Druga część tego przepisu nosi znamiona algorytmu. Czy jest to algorytm, czy nie można by długo dyskutować. Przyczyną naszych wątpliwości jest mało precyzyjny język. Wynika stąd ważny wniosek, że język naturalny nie nadaje się do zapisu algorytmów.

Rozważmy inny dobrze nam znany z lekcji matematyki problem.

Przykład 2. Rzeczywiste pierwiastki trójmianu kwadratowego.

Problem polega na wyznaczeniu wszystkich pierwiastków rzeczywistych rów-nania

ax 2 + bx + c = 0 ,

gdzie a 6= 0 , b, c są dowolnymi liczbami rzeczywistymi.

Oto dobrze znane nam rozwiązanie:

1. Obliczamy wyróżnik ∆.

6

2. Jeżeli ∆ < 0, to równanie nie ma pierwiastków rzeczywistych.

3. Jeżeli ∆ = 0, to równanie ma jeden pierwiastek rzeczywisty x = b

− .

2 a

√

4. Jeżeli ∆ > 0, to równanie ma dwa pierwiasteki rzeczywiste x = b+ ∆

−

1

2 a

√

i x = b ∆

− −

.

2

2 a

Czy ten matematycznie precyzyjny przepis można bezpośrednio wykonać na komputerze? Niestety w takiej postaci także nie.

Aby komputer mógł zrealizować proces prowadzący od danych do wyniku według zadanego algorytmu, algorytm ten musi być mu dany w tzw. języku maszynowym. Algorytm zapisany w języku maszynowym to po prostu ciąg zer i jedynek. Zrozumienie jego struktury, lub ewentualne usunięcie błędów, graniczy z czarną magią. W praktyce do zapisu algorytmu na rozwiązanie danego problemu stosujemy tzw. języki programowania wyższego poziomu. Języki te są najbliższe językowi naturalnemu, dużo bardziej zrozu-miałe, koncentrują się na ułatwieniu życia programistom.

Aby można było na danym komputerze używać języka wyższego rzędu po-trzebne jest narzędzie tłumaczące taki program na język maszynowy. Proces taki podzielony jest zazwyczaj na dwie części: kompilacja czyli tłumaczenie na kod pośredni oraz konsolidacja (linkowanie), czyli właściwe tłumaczenie na język maszynowy. Wytrawni programiści czasami posługują się językami assemblerowymi. Języki te wykorzystują podstawowe instrukcje procesora komputera dlatego stopień ich komplikacji jest znaczny.

7

SCHEMAT WYKONANIA ALGORYTMU NA KOMPUTERZE

4 Wnioski

Abyśmy mogli rozwiązywać zadania za pomocą komputera musimy w najbliższej przyszłości nauczyć się:

• „poruszania się”w różnych sieciowych systemach komputerowych (WIN-DOWS, UNIX, LINUX),

• projektowania algorytmów rozwiązujących postawione nam zadania (elementów teorii algorytmów),

• zapisywania tych algorytmów w języku wyższego poziomu (tym języ-kiem będzie dla nas język PASCAL),

• wykonywania procesu kompilacji na wybranych platformach systemo-wych.

8