Prof.dr hab. Tadeusz Wieczorek

Notatki do wykładów

Podstawy informatyki

3

Czym zajmuje się informatyka?

Stara definicja encyklopedyczna głosi:

„Informatyka zajmuje się całokształtem przechowywania, przesyłania, przetwarzania i
interpretowania

informacji. Wyróżnia się w niej dwa działy, dotyczące sprzętu i

oprogramowania”.

Większość z tego, co robią informatycy nie bardzo do tej definicji pasuje.

Nowsza definicja, opracowana w 1989 roku przez ACM, mówi:

„Informatyka to systematyczne badanie procesów algorytmicznych, które
charakteryzują i przetwarzają informację, teoria, analiza, projektowanie, badanie
efektywności, implementacja i zastosowania procesów algorytmicznych. Podstawowe
pytanie informatyki to: co można (efektywnie) zalgorytmizować”.

Teoria informacji

W 1949 roku pojawiły się trzy niezwykle ważne dla rozwoju informatyki prace.
Norbert Wiener wydał książkę „Cybernetyka, czyli sterowanie i komunikacja w
zwierzęciu i maszynie”, rozpoczynając tym samym szeroki nurt nauk
cybernetycznych.

Dwóch amerykańskich uczonych, McCulloch i Pitts, opisało

pierwszy model sieci nerwowej traktowanej jako układ elementów logicznych. Claude
Shannon prowadził rozważania nad przesyłaniem informacji w telekomunikacji i
napisał książkę, w której po raz pierwszy zdefiniował, jak zmierzyć ilość informacji.
Shannon studiował u Vannevara Busha, budowniczego analogowych maszyn
liczących i wizjonera, na słynnej MIT (Massachussets Institute of Technology),
studiował też matematykę. Miał więc odpowiednie przygotowanie by dostrzec, że
idee algebry Boole'a dają się w prosty sposób
realizować przy pomocy przełączników elektrycznych i odwrotnie, analiza
skomplikowanych obwodów elektrycznych, np. central telefonicznych, jest znacznie
prostsza jeśli zastosować rachunek logiczny.

p

p

I

2

log





Pojęcie informacji zrobiło wielką karierę w wielu dziedzinach nauki i techniki. W fizyce
okazało się np. że informacja zdefiniowana przez Shannona sprowadza się do
znanego
pojęcia entropii, miary uporządkowania układów. Informacja zdefiniowana ilościowo
przez Shannona, zwana również informacją probabilistyczną, nie ma tych własności,
które intuicyjnie kojarzymy z pojęciem informacji. Ilościowa miara informacji
przydatna
jest przede wszystkim przy określaniu minimalnej liczby znaków potrzebnych do
przekazania komunikatu. Chociaż, formalnie rzecz biorąc, informatyka jest nauką o
przetwarzaniu informacji, klasyczne metody teorii informacji znajdują obecnie
większe

zastosowanie w telekomunikacji i naukach przyrodniczych niż przy projektowaniu
komputerów. Z metod tych wyrósł natomiast jeden z ciekawszych działów informatyki
teoretycznej, jakim jest teoria złożoności obliczeniowej. Pojęcie złożoności i miary
złożoności są - w porównaniu z miarą ilości informacji Shannona - bliższe
intuicyjnemu

pojęciu informacji.

Algorytmika -

fundament informatyki, wiedza o sposobach rozwiązywania

zagadnień, czyli konstruowaniu algorytmów.

Zadania algorytmiczne -

czyli zadania, dla których znamy sposób rozwiązania.

Algorytmy efektywne - czyli tak

ie, które dają rozwiązanie przed końcem świata.

Złożoność obliczeniowa algorytmów - ocena, ile trzeba będzie wykonać obliczeń.
Testowanie i dowodzenie poprawności algorytmów.

Algorytmy heurystyczne: metody bez gwarancji na znalezienie rozwiązania (sztuczna
inteligencja).

Problem wędrującego komiwojażera: jak znaleźć najkrótszą drogę, łączącą N miast
odwiedzając każde tylko jeden raz?

T ~ N! = N(N-1)(N-

2)... 3·2·1 rośnie bardzo szybko, np. 100! ~10

158

Struktury danych: liczby, tablice, wektory, rekordy, listy, stosy, kolejki,

drzewa, liście

drzewa

, węzły potomne, grafy, diagramy.

Niklaus Wirth: Algorytmy + struktury danych =
programy. WNT, W-wa 2001.

Teoria języków programowania: specyfikacja,
procesory, automaty skończone (automaty
Turinga).

Organizacja i architektury systemów
komputerowych, systemów operacyjnych i sieci
komputerowych, teoria baz danych.

Zastosowania komputerów, czyli to co tygrysy lubią
najbardziej?

Zwykle nie zajmują się nimi informatycy.

Komputer

to maszyna do wykonywania programów (dlaczego cyfrowa, wyjaśnię w dalszej

części tego wkładu).

Program

to ciąg instrukcji, zapisanych w języku zrozumiałym dla

komputera. Ten ciąg instrukcji realizuje jakiś algorytm.

Algorytm

to dokładny przepis -- na

przykład algorytm otwierania drzwi mógłby wyglądać tak:

naciśnij klamkę
jeśli drzwi się otworzą
udało się - koniec.
w przeciwnym razie
włóż do zamka klucz, przekręć w lewo i naciśnij klamkę
jeśli drzwi się otworzą
udało się - koniec.
w przeciwnym razie
nie udało się - koniec.

Literatura

David Harel, Rzecz o istocie informatyki (Wyd. Naukowo-Techniczne, Warszawa
1992)
Bardzo dobry wstęp do „prawdziwej” informatyki.

H.W. Roetzheim, Laboratorium złożoności (Intersofland, Warszawa 1994) -
Eksperymenty komputerowe z fraktalami, galaktykami, genetyka

Ellen Thro, Sztu

czne życie, zestaw narzędzi badacza (SAMS Publishing,

1994) -

Eksperymenty komputerowe z genetyką, ekosystemami i sztucznymi

żyjątkami.

Richard Dawkins, Ślepy Zegarmistrz (PIW, W-wa 1994) - Opisuje
eksperymenty komputerowe z modelowaniem ewolucji genetycznej.