Projekt okładki i stron tytułowych Hubert Zacharski

Projekt okładki i stron tytułowych Shutterstock/ RealVector

Wydawca Łukasz Łopuszański

Redaktor prowadzący Adam Kowalski

Redaktor Joanna Forysiak

Koordynator produkcji Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN Marcin Kapusta / konwersja.virtualo.pl

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo

Więcej na www.legalnakultura.pl

Polska Izba Książki

Copyright © by Wydawnictwo Naukowe PWN SA

Warszawa 2017

eBook został przygotowany na podstawie wydania papierowego z 2017 r., (wyd. I)

Warszawa 2017

ISBN: 978-83-01-19604-2

Wydawnictwo Naukowe PWN SA

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl,

www.pwn.pl

Spis treści

1. Wprowadzenie

1.1. Informacja

1.2. Podstawowe cechy informacji

1.3. Informatyka

1.3.1. Istota informatyki

1.3.2. Informatyka a komputery

1.4. Komputer

1.5. Działy informatyki

2. Teoria informacji

2.1. Miara informacji

2.2. Entropia źródła informacji

2.3. Kodowanie komunikatów

2.4. Algorytmy kodowania optymalnego

2.4.1. Algorytmy Shannona-Fano

2.4.2. Algorytm Huffmana

2.4.3. Uzupełnienia

3. Systemy liczbowe

3.1. Wprowadzenie

3.2. Analogowość, cyfrowość, binarność

3.3. Działania na liczbach naturalnych w systemach pozycyjnych

3.3.1. Dodawanie i odejmowanie

3.3.2. Mnożenie i dzielenie

3.3.3. Zapis liczb rzeczywistych

3.4. Konwersje między systemami liczbowymi

3.4.1. Konwersja do systemu dziesiętnego

3.4.2. Konwersja do systemów niedziesiętnych

3.4.3. Zależność podstaw systemów liczbowych

4. Arytmetyka komputerowa

4.1. Kodowania stałopozycyjne

4.1.1. Kodowanie znak-moduł prosty

4.1.2. Kodowanie odwrotnościowe

4.1.3. Kodowanie uzupełnieniowe

4.1.4.Kodowanie nadmiarowe

4.2. Kodowania zmiennopozycyjne

4.2.1. Wprowadzenie

4.2.2. Normalizacja i jednoznaczność

4.2.3. Algorytmy kodowania i dekodowania

4.2.4. Reprezentatywność

4.2.5. Efektywność i optymalizacja

4.2.6. Działania na kodach zmiennopozycyjnych

4.2.7. Praktyczne implementacje

5. Maszyna Turinga

5.1. Wprowadzenie

5.2. Definicja

5.3. Przykłady

5.3.1. Pracowity bóbr stopnia trzeciego

5.3.2. Inkrementacja liczby binarnej

5.3.3. Inkrementacja liczby dziesiętnej

5.3.4. Dekrementacja liczby binarnej

5.3.5. Sumowanie przez inkrementację i dekrementację

5.3.6. Dodawanie pisemne liczb binarnych

6. Przykładowa Maszyna Cyfrowa (PMC)

6.1. Architektura von Neumanna

6.2. Budowa PMC

6.3. Działanie PMC

6.3.1. Interpretacja słowa maszynowego

6.3.2. Rozkazy

6.3.3. Tryby adresowania

6.3.4. Cykl pracy

6.4. Realizacja przykładowych algorytmów

7. Podstawy algorytmiki

7.1. Wprowadzenie

7.2. Podstawowe pojęcia

7.2.1. Pojęcie algorytmu

7.2.2. Wstępne przykłady

7.2.3. Zmienna

7.2.4. Podstawienie

7.2.5. Tablica

7.3. Zapis algorytmów

7.3.1. Zapis krokowy

7.3.2. Schemat blokowy

7.3.3. Strukturalne schematy blokowe

7.3.4. Zapis liniowy, pseudokod

7.4. Strukturalność

7.4.1. Generalia

7.4.2. Strukturalny zapis niestrukturalności

7.5. Tworzenie algorytmów

7.6. Złożoność algorytmów

7.7. Poprawność algorytmów

7.7.1. Wprowadzenie

7.7.2. Podstawy

7.7.3. Częściowa poprawność, niezmienniki pętli

7.7.4. Częściowa poprawność wybranych algorytmów

8. Notacje wyrażeń algebraicznych

8.1. Generalia

8.1.1. Podstawowe pojęcia

8.1.2. Rodzaje notacji algebraicznych

8.2. Notacje algebraiczne w informatyce

8.3. Konwersje notacji

8.3.1. Stos

8.3.2. Sprowadzenie do zapisu liniowego

8.3.3. Zamiana na odwrotną notację polską

8.3.4. Wartościowanie wyrażeń w ONP

8.4. Zapis algorytmów w ONP

8.4.1. Konwersja zapisu algorytmów do ONP

8.4.2. Odtworzenie algorytmów z zapisu w ONP

9. Języki formalne

9.1. Podstawowe pojęcia i oznaczenia

9.1.1. Przykładowe alfabety

9.1.2. Przykładowe języki

9.2. Gramatyka formalna

9.2.1. Intuicja

9.2.2. Formalne definicje

9.2.3. Hierarchia Chomsky’ego

9.2.4. Jeszcze o gramatykach

9.2.5. Gramatyki języków programowania

9.3. Gramatyki regularne a maszyna Turinga

9.3.1. Akceptacja słów języka regularnego

9.3.2. Rozpoznawanie palindromów

Przypisy

1. Wprowadzenie

1.1. Informacja

Zasadniczym tematem naszych rozważań jest informatyka, jednak nawet nikła wiedza o informatyce, wywiedziona jedynie z pobieżnej analizy użytego słowa, sugeruje związek pojęcia informatyka z pojęciem informacja. Dlatego, by zajmować się informatyką, konieczne jest przybliżenie bardziej podstawowego pojęcia informacji. Na początek spróbujmy zorientować się w zasobach najpopularniejszego obecnie źródła wiedzy – polskojęzycznej Wikipedii.

Informacja (łacińskie informatio – przedstawienie, wizerunek; informare – kształtować, przedstawiać) – termin interdyscyplinarny, definiowany różnie w różnych dziedzinach nauki; najogólniej – właściwość pewnych obiektów, relacja między elementami zbiorów pewnych obiektów, której istotą jest zmniejszanie niepewności (nieokreśloności)[1].

Doceniając wysiłek autora hasła w pokonaniu trudności wynikających z nadmienionej interdyscyplinarności, nie sposób pominąć nadużycia słowa „pewnych”, w żaden sposób nieprzybliżającego czytelnika do rozumienia pojęcia informacji. Jednakże istota „informatycznego” rozumienia informacji zawarta jest w ostatnim zdaniu, pozwalającym wskazać najważniejszą, najbardziej fundamentalną cechę informacji, niemal jej kwintesencję:

Informację niesie każde zjawisko zmniejszające niepewność.

Powyższa cecha nie stanowi jeszcze definicji, dlatego skoncentrujmy uwagę na opisanym w Wikipedii bardziej komputerowo/informatycznym rozumieniu informacji.

Można wyróżnić dwa podstawowe punkty widzenia informacji:

1) obiektywny – informacja oznacza pewną właściwość fizyczną lub strukturalną obiektów (układów, systemów), przy czym jest kwestią dyskusyjną czy wszelkich obiektów, czy jedynie systemów samoregulujących się (w tym organizmów żywych),

2) subiektywny – informacja istnieje jedynie względem pewnego podmiotu, najczęściej rozumianego jako umysł, gdyż jedynie umysł jest w stanie nadać elementom rzeczywistości znaczenie (sens) i wykorzystać je do własnych celów[2].

Pomińmy sztuczność powyższego podziału i wskazując na ponowne nadużycie słowa „pewien”, zrezygnujmy z subiektywnego punktu widzenia i skoncentrujmy uwagę na spojrzeniu obiektywnym. Rozwijając opis hasła informacja, otrzymujemy następującą definicję:

Informacja obiektywna – w cybernetyce i teorii informacji najbardziej ogólnie: każde rozpoznanie stanu układu odróżnialnego od innego stanu tego układu (stanu wyróżnionego); wyróżnienie pewnego stanu wyróżnionego (odróżnialnego) z repertuaru (zbioru stanów wyróżnionych); „...w pojęciu informacji istotne jest nie samo zaistniałe zjawisko, lecz jego stosunek do zbioru zdarzeń, które mogły były zaistnieć”.

Można odróżnić:

1) informację swobodną, kiedy możliwości (stany, zdarzenia) uważamy za abstrakcyjne i nie przypisujemy im żadnego znaczenia fizycznego,

2) informację związaną, kiedy możliwości (stany, zdarzenia) mogą być interpretowane jako mikrostany (lub zbiory mikrostanów) pewnego układu fizycznego.

Informacja zawarta w stanach układu kwantowego to informacja kwantowa.

Bardziej szczegółowo można rozpatrywać informację:

1) w odniesieniu do procesu komunikowania się (systemu przekazywania informacji, toru sterowniczego),

2) w odniesieniu do budowy układu[3].

Powyższa definicja graniczy z pseudonaukowym pustosłowiem, a sytuację w umiarkowanym stopniu ratuje inne określenie zawarte w dalszej części opisu hasła:

Informacja w odniesieniu do procesu komunikowania się

Informacja jest to wyróżnienie przez pewien układ informacyjny (odbiorcę) ze swojego repertuaru pewnego stanu wyróżnionego (przez odróżnienie go od innego stanu

wyróżnionego), odbijające wyróżnienie stanu wyróżnionego układu informacyjnego będącego nadawcą (Definicja 1).

O informacji można tu mówić jedynie w odniesieniu do układu, który jest zdolny ją odebrać (odbić wyróżnienie stanu wyróżnionego nadawcy), i tylko w takim zakresie, w jakim jest zdolny. Różne układy informacyjne mogą odbijać (rozpoznawać) różne stany wyróżnione z różnych repertuarów.

W tym znaczeniu informacja ma charakter relatywny i jest nazywana informacją względną[4].

Niestety, kolejny raz nadużyto słowa „pewien”, a ponadto częstość użycia słowa „wyróżnienie” w cytowanej definicji graniczy z absurdem.

Jednakże usunięcie zbędnych wystąpień słowa „wyróżnienie” prowadzi do poniższej definicji informacji, prostej i skrótowej.

Informacja – zjawisko osiągnięcia przez źródło informacji szczególnego stanu spośród wszystkich możliwych stanów.

Powyższa definicja, mimo że lapidarna, jest ogólniejsza od wcześniej cytowanych, a ponadto odzwierciedla fundamentalną cechę informacji – zmniejszenie niepewności. Jeżeli bowiem istnieje niepewność stanu źródła informacji, to właśnie osiągnięcie szczególnego stanu tę niepewność zmniejsza.

Dla pełności definicji dookreślenia wymaga jeszcze termin źródło informacji. Ponieważ każda dziedzina wiedzy uznaje wybrane pojęcia za pierwotne (niewymagające definicji, zrozumiałe z natury rzeczy), dlatego w ślad za większością źródeł i autorów za niemal pierwotne uznajmy pojęcie źródła informacji – poprzestając na intuicyjnym opisie, że źródłem informacji jest każde zjawisko cechujące się możliwością zmiany swojego stanu.

Wprowadzona definicja informacji nie aspiruje do powszechnej akceptowalności i z całą pewnością pozostanie jedną z wielu.

1.2. Podstawowe cechy informacji

Wspomniana na wstępie fundamentalna cecha informacji, czyli zmniejszanie niepewności, jest wielkością mierzalną i będziemy się nią zajmować szczegółowo w rozdziale dotyczącym ilościowej teorii informacji. Jednakże informacja wykazuje wiele dodatkowych niezbywalnych cech, często z racji oczywistości zaniedbywanych, w konsekwencji zapominanych i powodujących problemy. Odwołajmy się powtórnie do zamieszczonego w Wikipedii opisu hasła informacja, znajdując następujący opis:

Przenoszenie i przetwarzanie informacji

Informacja może być przenoszona w czasie i przestrzeni. Przenoszenie w czasie nazywamy magazynowaniem lub zapamiętywaniem, przenoszenie w przestrzeni – przekazem lub komunikowaniem. Przenoszenie informacji odbywa się za pośrednictwem obiektów fizycznych i zjawisk fizycznych zwanych nośnikami informacji. Magazynowanie związane jest najczęściej ze stanami wyróżnionymi obiektu fizycznego – podłoża zapisu, a przekaz ze stanami wyróżnionymi zjawiska fizycznego – sygnałami.Problemami przetwarzania informacji zajmuje się informatyka[5].

Powyższy opis zawiera całkiem udaną definicję informatyki (zajmiemy się nią osobno w dalszej części książki), a ponadto sygnalizuje niezbędne cechy informacji. Rozbudowując listę niezbywalnych cech informacji (z domniemaniem pewnej kompletności), można powiedzieć, że informacja:

• istnieje obiektywnie – inaczej mówiąc, niezależnie od odbiorcy; niemożność odebrania informacji (z różnych powodów: zależności czasowych, możliwości percepcyjnych lub technicznych) nie oznacza, że informacja nie występuje;

• podlega przetworzeniu – może być analizowana (na przykład dla wyodrębnienia części informacji w zależności od wagi), syntezowana (dla osiągnięcia nowej obszerniejszej informacji) i przetwarzana w dowolny inny sposób; informacja zastrzeżona do formy początkowego wystąpienia (bez możliwości przetworzenia) miałaby znaczenie ograniczone;

• jest przenaszalna – a nawet MUSI BYĆ przenaszalna; pozostając dostępna wyłącznie u źródła informacji, byłaby fizycznie związana ze źródłem, więc nie miałaby możliwości szerszego oddziaływania;

• jest powielalna – ponieważ występując w pojedynczej reprezentacji byłaby podobnie ściśle związana z jednostkową reprezentacją, co prowadziłoby do ograniczonego kręgu odbiorców oraz niemożności niezależnego przetwarzania;

• posiada różnorodne równoważne reprezentacje – w rozumieniu reprezentacji teoretycznej (matematycznej), ale również fizycznej; fizyczność reprezentacji należy rozumieć szeroko: fala elektromagnetyczna czy wartość natężenia w półprzewodniku równie dobrze służą zatem reprezentacji informacji jak zapis papierowy;

• bywa fragmentaryczna – kompletna informacja jest raczej ideą, a konieczność fizycznej reprezentacji implikuję możliwość fragmentaryczności; świadoma fragmentaryzacja stanowi zatem podstawę teleinformatyki i optymalizacji przesyłania informacji;

• podlega zniekształceniu – z racji wspomnianej konieczności fizycznej reprezentacji, implikującej naturalne podleganie różnorodnym oddziaływaniom;

• podlega interpretacji – fakt wystąpienia informacji, a nawet jej ilość są ścisłe i obiektywne, mimo wielu odbiorców; jednak działanie wynikające z informacji w zależności od konkretnego odbiorcy może być rozmaite, powodować odmienne skutki, stanowiąc inną interpretację.

1.3. Informatyka

1.3.1. Istota informatyki

Dysponując pojęciem informacji, możemy pokusić się o zdefiniowanie pojęcia informatyka. Ponownie odwołajmy się do polskojęzycznej Wikipedii.

Informatyka – dyscyplina naukowa i techniczna zajmująca się przetwarzaniem informacji, a w tym technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informacje. Pierwotnie część matematyki, została rozwinięta do odrębnej dyscypliny naukowej. Pozostaje jednak nadal w ścisłym związku z matematyką, która dostarcza informatyce podstaw teoretycznych[6].

Powyższy opis wydaje się trafny, z nieco być może przesadnym podkreśleniem ścisłego związku informatyki z matematyką. Najbardziej rozwojowa część informatyki może być uznana za stosowaną matematykę (wspomniany związek jest niezaprzeczalny), jednakże postęp technologiczny istotnie ogranicza znaczenie czystej matematyki w codziennej informatyce, czyniąc go nie tak ścisłym, jak kiedyś.

Dla szerszego spojrzenia skonfrontujmy polski opis hasła z angielskim.

Informatyka zajmuje się badaniem teoretycznych podstaw informacji, automatycznego obliczania i praktycznymi technikami ich wdrażania oraz stosowania w systemach komputerowych. Informatycy wymyślają algorytmiczne procesy tworzące, opisujące i przetwarzające informację, a ponadto formułują odpowiednie abstrakcyjne modele złożonych systemów informatycznych[7].

W powyższej definicji łatwo dostrzec brak określenia istoty informatyki, z wątpliwym wyszczególnieniem wybranych zakresów pracy informatyków. Jednakże łącząc powyższe opisy hasła informatyka i odwołując się do wcześniejszych opisów hasła informacja, możemy sformułować określenie informatyki w poniższy sposób:

Informatyka – dziedzina wiedzy zajmująca się przetwarzaniem informacji.

1.3.2. Informatyka a komputery

Polskie słowo informatyka skonfrontowane z angielskim odpowiednikiem computer science (w kalce językowej – nauka komputerowa) może wzbudzić wątpliwość z powodu braku odniesienia do (wydawałoby się fundamentalnego) komputera. Nieco rozważenie etymologii słowa informatyka pozwoli zarazem sięgnąć pogłębione w istotę informatyki, obalając obiegowy mit o niemal równoważności informatyki i komputerów.

Fundamentalnemu wkładowi Wielkiej Brytanii (początkowo) i Stanów Zjednoczonych (aż do teraz) w rozwój informatyki trudno zaprzeczyć. Nawet odniesienia do wcześniejszych niż brytyjskie osiągnięć Niemca Konrada Zuse z komputerem Z3 mogą być podważone, ponieważ przed nimi pojawiły się maszyny różnicowa i analityczna Anglika Charlesa Babbage’a. Użycie słów computer science datowane jest mniej więcej na koniec lat pięćdziesiątych XX wieku. Pojęcie to zostało przyjęte zapewne z braku lepszej propozycji i od zarania budziło wątpliwość, ponieważ nadmiernie akcentuje znaczenie komputerów. Tymczasem fachowcy twierdzą, że informatyka jest czymś znacznie obszerniejszym niż nauka o komputerach. Najdobitniej rzecz ujmuje zdanie pochodzące z wydanego w styczniu 1993 roku czasopisma „Computer Research News”, przypisywane holenderskiemu pionierowi informatyki Edsgerowi Dijkstrze:

Twierdzenie, iż informatyka to nauka o komputerach, ma tyle samo sensu, ile twierdzenie, że astronomia to nauka o teleskopach, biologia to nauka o mikroskopach, a chemia to nauka o zlewkach i probówkach[8].

W powyższej sentencji zasygnalizowano, że komputer jest jedynie narzędziem informatyki (niewątpliwie ważnym – czym zajmiemy się szerzej w następnym podrozdziale), a określenie computer science jest nieco ułomne. W konsekwencji w innych obszarach językowych, ze świadomością wspomnianej ułomności, posłużono się innymi wyrażeniami. W 1962 roku Francuzi zaproponowali termin informatique, stanowiący udane połączenie słów information (informacja) i automatique (automatyka), w konsekwencji prowadzące do niemieckiego oraz skandynawskich Informatik, włoskiego informatica czy rosyjskiego информатика (hiszpański obszar językowy używa wyrażenia ciencias de la computación). Opisane francuskie połączenie słów pozwala sformułować alternatywne określenie informatyki, być może mniej ogólne, ale zwracające uwagę na związek informatyki z automatycznością:

informatyka = informacja + automatyka

1.4. Komputer

Przy okazji opisu słowa informatyka wspomnieliśmy o podrzędności komputera w stosunku do informatyki – pojęcia znacznie szerszego. Mówiąc obrazowo, komputer bez informatyki jest bezużytecznym zestawem przetworzonej materii, podczas gdy informatyka istnieje nawet bez komputerów. Niemniej spośród wielu narzędzi wykorzystywanych w informatyce komputer pełnia rolę dużo istotniejszą niż wszystkie inne narzędzia razem wzięte. W konsekwencji ogólne opisanie pojęcia komputera wydaje się konieczne. W ślad za polską Wikipedią otrzymujemy definicję:

Komputer (z angielskiego computer od łacińskiego computare – obliczać; dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – maszyna elektroniczna przeznaczona do przetwarzania informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego[9].

Podkreślenie roli przetwarzania informacji wydaje się właściwe, natomiast odniesienia do ciągu cyfr lub sygnału ciągłego trudno uznać za poprawne. Dlatego sprawdźmy jeszcze anglojęzyczną Wikipedię. Znajdujemy w niej następującą definicję w wolnym tłumaczeniu autorów niniejszej książki:

Komputer jest maszyną programowalną przeznaczoną do sekwencyjnego i automatycznego przeprowadzania ciągu operacji arytmetycznych lub logicznych. Poszczególne sekwencje operacji są łatwe do zmiany, dzięki czemu komputer pozwala rozwiązywać więcej niż jeden rodzaj problemów[10].

W przeciwieństwie do polskiej wersji, w angielskiej brak wyraźnego odniesienia do przetwarzania informacji (wynika ono z całości opisu), jednakże wprowadzenie zależności od programowania czyni całość definicji znacznie trafniejszą.

Kolejny raz syntetyzując różnorodne informacje dotyczące pojęcia komputera, formułujemy własne określenie:

Komputer – urządzenie zdolne do przetwarzania informacji, z możliwością sterowania przez nieograniczoną liczbę programów.

Wydaje się, że kwestia przetwarzania informacji, występująca w powyższym opisie, została już wcześniej uzasadniona i dlatego skupimy się na części dotyczącej sterowania. Nie będziemy wnikać w formalne definicje pojęć sterowania i programu (przyjmujemy tymczasowo, że są one intuicyjnie znane w stopniu niezbędnym do zajmowania się pojęciem komputera), ponieważ istotą jest odróżnienie komputera od automatu. Zarówno komputer, jak i automat są urządzeniami (realnymi lub wirtualnymi) przetwarzającymi informacje oraz sterowanymi programami – jednak występują między nimi istotne różnice. Automat jest przede wszystkim urządzeniem ukierunkowany na zamknięty zbiór możliwych działań, a odrębne sterowania/programy są stosunku do działań podrzędne i również ograniczone. W przypadku komputerów sytuacja jest niejako odwrotna: sterowanie (program, algorytm) jest najważniejsze i teoretycznie nieograniczone, a urządzenie/komputer jest podrzędnym narzędziem do realizacji idei zawartej w sterowaniu/programie/algorytmie.

1.5. Działy informatyki

Dzielenie dziedzin wiedzy o nawet głębokiej przeszłości nigdy nie jest jednoznaczne, dlatego trudno wymagać jednoznaczności w dzieleniu tak młodej i zarazem tak eklektycznej dyscypliny naukowej, jak informatyka. Dlatego dla klasyfikacji działów informatyki posłużymy się arbitralnymi podziałami pochodzącymi z polsko- i angielskojęzycznej Wikipedii. Towarzyszy nam zarazem świadomość, że opisy poszczególnych działów sięgają do wiedzy spoza przedstawionego materiału.

Polskojęzyczna Wikipedia wyróżnia następujące działy informatyki:

• Administracja sieciowa

Dział koncentrujący się na zarządzaniu sieciami komputerowymi, z dużym udziałem wiedzy telekomunikacyjnej.

• Administracja systemów

Dział zajmujący się większą liczbą komputerów połączonych nie tylko na poziomie komunikacji (jak w sieciach komputerowych), lecz także w rozumieniu wspólnej pracy.

• Algorytmika

Bez wątpienia najważniejszy dział informatyki, stanowiący o jej najbardziej znaczących postępach, niemal o istocie informatyki. Zajmuje się tworzeniem nowych algorytmów i w znaczącym stopniu wszechstronną oceną algorytmów istniejących.

• Architektura procesorów

Dział oparty na technologii i ukierunkowany na technologię, ale wraz z rozwojem możliwości procesorów coraz bardziej teoretyczny niż inżynierski.

• Bezpieczeństwo komputerowe

Dziedzina kiedyś mocno z związana z kryptografią, aktualnie w przeważającej części dotycząca bezpieczeństwa teleinformatyki.

• Grafika komputerowa

Dział silnie eklektyczny, zajmujący się szczególnym medium stanowionym przez ekran komputerowych monitorów.

• Inżynieria oprogramowania

Dział zajmujący się szerokim zakresem zjawisk towarzyszących tworzeniu oprogramowania. Z racji sięgania do zarządzania produkcją, zarządzania zasobami ludzkimi i wieloma innymi pokrewnymi dziedzinami również mocno eklektyczny.

• Języki programowania

Jeden z niewielu działów czysto informatycznych, zajmujący się tytułowym zagadnieniem z wykorzystaniem zaawansowanej lingwistyki i kognitywistyki, z użyciem szczególnych języków służących komunikacji z komputerem.

• Programowanie

Dział zajmujący się bezpośrednio tworzeniem programów i korzystający z dorobku wielu innych działów. Jednocześnie być może dział najbardziej informatyczny, stanowiący rodzaj ogólnoinformatycznego rzemiosła.

• Sprzęt komputerowy

Dział zajmujący się nie tylko komputerami w rozumieniu fizycznych urządzeń, lecz także szerokim zakresem urządzeń towarzyszących pracy komputerów we wszystkich możliwych aspektach.

• Symulacja komputerowa

Dziedzina wymagająca sięgania do wiedzy szczególnego przedmiotu symulacji, ale ponadto zajmująca się ogólnym zjawiskiem symulacji, niezależnie od konkretnego symulowanego zjawiska.

• Sztuczna inteligencja

Zapewne najbardziej interdyscyplinarny dział informatyki, próbujący sprawić, by komputery naśladowały inteligencję, czymkolwiek ona jest.

• Teoria informacji

Być może najbardziej fundamentalny dział informatyki, mocno zmatematyzowany i niejednokrotnie sięgający do różnych działów filozofii.

• Webmastering

Zróżnicowany dział ukierunkowany na obszar działalności związany z obsługą protokołu WWW, czyli (w ogromnym uproszczeniu) zasobami dostępnymi przez przeglądarki internetowe.

Mimo zapowiedzianej arbitralności powyższy podział wydaje się mocno niekompletny, a z drugiej strony grzeszy nadmierną szczegółowością. Alternatywę może stanowić podział pochodzący z anglojęzycznej Wikipedii, wyróżniający dwa najbardziej ogólne działy informatyki. Pierwszym jest informatyka teoretyczna (theoretical computer science), mieszcząca w sobie bardziej szczegółowe dziedziny związane z matematyką, teoretyczną fizyką czy filozofią. Drugi ogólny dział (applied computer science) jest ukierunkowany na zastosowania i obejmuje wiele bardziej praktycznych dziedzin inżynierskich. Szczegółowe dziedziny obu ogólnych działów często się przenikają, granice między nimi są płynne, dlatego zostaną przedstawione razem. Wyróżnione działy informatyki obejmują:

• Teorię obliczeń (obliczalności), (theory of computation)

Jeden z najbardziej fundamentalnych działów informatyki, zajmujący się między innymi odpowiedzią na pytania o sens stosowania komputerów. Mimo zaawansowanej matematyki ukierunkowany na informatykę.

• Teorię informacji i kodowania (information and coding theory)

W polskiej Wikipedii dział został nazywany teorią informacji.

• Algorytmy i struktury danych (algorithms and data structures)

Dział obejmujący zakres algorytmiki z polskiej Wikipedii, jednak uzupełniony o struktury danych, czyli (w dużym uproszczeniu) zagadnienia jak najlepszego (pod wieloma względami) pamiętania różnorodnych bytów.

• Teorię języków programowania (programming language theory)

W polskiej Wikipedii nazywaną językami programowania.

• Metody formalne (formal methods)

Dziedzinę zajmującą się wieloma aspektami informatyki z użyciem formalnej matematyki.

• Współbieżność, obliczenia równoległe i rozproszone (concurrent, parallel and distributed systems)

Dziedzinę zajmującą zagadnienia równoczesnego działania wielu programów na jednym komputerze, działania wielu komputerów nad rozwiązaniem jednego problemu czy też inne problemy jednoczesnego działania.

• Bazy danych i pozyskiwanie informacji (databases and information retrieval)

Jedną z najważniejszych dziedzin codziennej informatyki, kiedyś skoncentrowaną na szybkości dostępu do informacji, a obecnie coraz silniej akcentującą sposoby wyszukiwania informacji w ogromnym jej natłoku.

• Sztuczną inteligencję (artificial intelligence)

Definiowaną identycznie jak w polskiej Wikipedii.

• Architekturę i inżynierię komputerów (computer architecture and engineering)

To połączenie w jeden dział architektury procesorów oraz sprzętu komputerowego z polskiej Wikipedii.

• Grafikę komputerową i wizualizację (computer graphics and visualization)

Definiowaną odobnie jak w polskiej Wikipedii, z uwzględnieniem złożonych zagadnień wizualizacji różnorodnych bytów.

• Bezpieczeństwo komputerów i kryptografię (computer security and cryptography)

Opisywaną analogiczne jak w polskiej Wikipedii.

• Obliczenia naukowe (computational science)

Dziedzinę badającą możliwości wykorzystania informatyki do obliczeń wymaganych w naukach stosowanych.

• Informację naukową (information science)

Badającą problemy informacji w innych dziedzinach wiedzy, szczególnie w naukach społecznych, a nawet humanistycznych.

• Inżynierię oprogramowania (software engineering)

Definiowaną analogiczne jak w polskiej Wikipedii.

2. Teoria informacji

Twórcą prezentowanej w tym rozdziale teorii jest Claude E. Shannon[11]. Sama teoria nazywana jest ilościową teorią informacji i mimo że nie jest jedyna (znana jest na przykład jakościowa teoria informacji), pozostaje najpowszechniej uznawana.

2.1. Miara informacji

W poprzednim rozdziale określiliśmy najważniejszą własność informacji, sprowadzającą się do zmniejszenia niepewności. Jednak wspomniane określenie odzwierciedla wyłącznie fakt zmniejszenia niepewności, nie wnikając w relacje ilościowe. Mówiąc inaczej, jeżeli zachodzą dwa zdarzenia niosące informację (a więc zmniejszające niepewność), warto zadać pytanie, które zdarzenie daje więcej informacji, a które mniej.

Intuicyjne rozumienie ilości informacji oddaje słynne zdanie przypisywane Markowi Twainowi: Wiadomość, że pies pogryzł człowieka, to żadna wiadomość. Ale wiadomość, że człowiek pogryzł psa, to jest dopiero wiadomość. Mówiąc bardziej formalnie: jeżeli zdarzenie jest częste, to jego zachodzenie nie niesie zbyt wiele informacji (nie budzi zainteresowania), natomiast zajście zdarzenia rzadkiego niesie więcej informacji (wywołuje większe zainteresowanie).

Skojarzenie użycia przymiotników częste i rzadkie z rachunkiem prawdopodobieństwa jest w pełni uzasadnione, ponieważ miara informacji zawartej w zdarzeniu jest odwrotnie proporcjonalna do prawdopodobieństwa jego wystąpienia. Traktując rzecz czysto matematycznie, jeżeli przy oznaczeniu zdarzenia przez A oznaczymy prawdopodobieństwa zdarzenia A przez P(A), a niepewność zdarzenia A przez H(A) (H pochodzi od angielskiego słowa hesitance), to możemy ścisłe związki prawdopodobieństwa i niepewności sformułować w poniższych własnościach:

1. Jeżeli P(A) = 1, to H(A) = 0.

Zdarzenie pewne (wiadomo, że nastąpi lub już nastąpiło) nie wnosi żadnej informacji – właśnie z racji pewności jego zajścia.

2. Jeżeli P(A) < P(B), to H(A) > H(B).

Matematycznie wyrażona i opisana wcześniej intuicyjnie odwrotna zależność między prawdopodobieństwem a niepewnością. Zdarzenia mało prawdopodobne niosą większą niepewność (więcej informacji), podczas gdy zdarzenia bardziej prawdopodobne niosą mniejszą niepewność (mniej informacji).

3. Jeżeli zdarzenia A oraz B są zdarzeniami niezależnymi, to:

Powyższa równość wymyka się prostej intuicji, poprzestaniemy zatem na przybliżonym uzasadnieniu, w oderwaniu od wartości prawdopodobieństwa. Rozważmy dwa zdarzenia (zbiory zdarzeń elementarnych) wraz z towarzyszącymi im niepewnościami, załóżmy ich niezależność (nawet w potocznym rozumieniu) i rozpatrzmy zdarzenie będące ich mnogościowym iloczynem (nie należy przy tym ulegać pułapce utożsamiania niezależności z rozłącznością oraz pułapce utożsamiania części wspólnej z jednoczesnością lub wspólnością zachodzenia obu zdarzeń). Jeżeli wspólne zdarzenie zależy od obu wyjściowych zdarzeń, naturalne wydaje się, że na niepewność wspólnego zdarzenia mają wpływ niepewności obu zdarzeń składowych. Z niezależności zdarzeń wynika, że niepewność zdarzenia wspólnego musi być sumą niepewności zdarzeń składowych.

Teoria informacji zawiera jeszcze wiele innych interesujących własności, ale poprzestaniemy na powyższych, nieco arbitralnie uznając je za najistotniejsze.

Powyższe własności miary informacji (miary niepewności), opisując różnorodne jej zależności, nie podają samej miary w rozumieniu wartości liczbowej. Okazuje się, że odpowiednie właściwości określenia liczbowej miary informacji posiada każda funkcja logarytmiczna o podstawie większej od jedności, z odwrotności prawdopodobieństwa wystąpienia zdarzenia. Tym samym możemy zdefiniować:

Liczbową miarę ilości informacji zdarzenia A o prawdopodobieństwie wystąpienia P(A) wynoszącym p określa formuła:

Zauważmy, że jeżeli P(A) = 1, to

czyli spełniona jest pierwsza z podanych własności miary informacji. Ponadto jeżeli prawdopodobieństwa zdarzeń A oraz B wynoszą odpowiednio P(A) = pA oraz P(B) = pB i jednocześnie , wtedy (z racji dodatniej wartości prawdopodobieństw), a w konsekwencji (z racji rosnącej monotoniczności użytej funkcji logarytmicznej).

Ostatecznie otrzymujemy:

H(A) > H(B),

co oznacza drugą z podanych własności miary informacji. Dodatkowo przy niezależności zdarzeń A oraz B z definicji zdarzeń niezależnych wynika:

zatem:

Z kolei z własności funkcji logarytmicznej mamy:

W konsekwencji:

co oznacza spełnianie trzeciej z wymienionych własności miary informacji.

Wprowadzony wzór określający miarę informacji zależy wyłącznie od prawdopodobieństwa, będącego ponadto zawsze liczbą z przedziału jednostkowego. Dlatego wygodniejsze w użyciu jest operowanie wyłącznie prawdopodobieństwem dla określenia ilości informacji; w dalszych działaniach posługiwać się będziemy prostym przetworzeniem wprowadzonego wzoru. W zastępstwie podzbiorów zbioru zdarzeń elementarnych dziedziną będzie zbiór wartości funkcji prawdopodobieństwa i tylko na podstawie wartości prawdopodobieństwa będziemy określać ilość informacji.

Ilość informacji (oznaczana przez I) o prawdopodobieństwie wystąpienia wynoszącym p określa funkcja dana wzorem:

Jednostki miary informacji

Wprowadzone wzory miary informacji dopuszczają dowolność określenia podstawy logarytmu. Recz jasna, nie istnieje konieczność ogólnego ustalenia owej podstawy i można nawet każdorazowo przyjąć inną jej wartość; wystarczy jedynie pamiętać o niemieszaniu wartości podstaw w ramach jednej działalności. Jednak praktyka, inżynieria, a nawet teoria wyraźnie preferują wybraną wartość wynoszącą 2. Wybór tej, a nie innej wartości nie jest kwestią umowy, będzie szerzej omówiony w jednym z kolejnych rozdziałów, a aktualnie pozwala określić konkretną jednostkę informacji, czyli powszechnie znany bit.

Ilość bitów informacji niesioną przez zdarzenie o prawdopodobieństwie wystąpienia wynoszącym p określa funkcja:

Zwróćmy uwagę, że potoczne rozumienie bitu w postaci obiektu o ściśle dwoistej naturze jest wtórne w stosunku do definicji jednostki miary informacji, a nie na odwrót. Najpierw określono jednostkę informacji i nazwano ją bitem, by następnie zwyczajowo utożsamić obiekty dające dokładnie jeden bit informacji z nazwą jednostki miary informacji. Nazwa jednostki miary informacji nie pochodzi od wirtualnej czy rzeczywistej realizacji wspomnianego dwoistego obiektu. Właśnie dwoistość realizacji bitu w potocznym rozumieniu oznacza dwuelementowy zbiór zdarzeń elementarnych o połówkowych prawdopodobieństwach. Tym samym zdarzenie ustalenia dowolnej z dwóch wartości oznacza miarę informacji wynoszącą:

czyli dokładnie jeden bit informacji w rozumieniu miary.

Bit jest podstawową jednostką miary informacji, o szeroko uznawanym oznaczeniu b. Praktyka wymusiła wprowadzenie jednostek pokrewnych, z najpowszechniej znanym bajtem – czyli ilością informacji odpowiadającą ośmiu bitom – z równie powszechnym oznaczeniem B. Jednostkami pochodnymi od bajta są między innymi jednostki zwielokratniające ze standardowymi przedrostkami: kilo-, mega-, giga-, tera- i inne. W informatyce mają wartości bliskie tradycyjnym, jednak nieco się od nich różnią.

nazwa

informatyczna

oznaczenie

wartość informatyczna

nazwa

tradycyjna

wartość tradycyjna

kilobajt

KB

2^10 = 1 024

tysiąc

10^3 = 1 000

megabajt

MB

2^20 = 1 048 576

milion

10^6 = 1 000 000

gigabajt

GB

2^30 = 1 073 741 824

miliard

10^9 = 1 000 000 000

terabajt

TB

2^30 = 1 099 511 624 776

bilion

10^12 = 1 000 000 000 000

Powyższe zestawienie przedstawia najczęściej wykorzystywane jednostki informacji pochodne względem bajta w konfrontacji z ich tradycyjnymi wartościami. Kolejna jednostka nie jest określona przez mnożnik o wartości 10^3 = 1000, ale przez jej najbliższy odpowiednik potęgi dwójki, czyli wartość 1024 = 2^10. Łatwo zauważyć, że jednostka informatyczna od tradycyjnej może się różnić aż o niemal 10%.

Mimo że bit jest najpowszechniej stosowaną podstawową jednostką miary informacji, w wielu zastosowania spotkać można inne jednostki podstawowe. W zaawansowanych zagadnieniach matematycznych związanych z opisaną dalej entropią informacji stosowana jest jednostka o nazwie nit, nat lub nepit, określona wzorem:

a kryptografia i statystyka wykorzystuje jednostkę zwaną dit, ban lub hartley, określoną wzorem:

2.2. Entropia źródła informacji

Źródła informacji różnią się liczbą zdarzeń elementarnych lub układem prawdopodobieństw, dlatego zasadne wydaje się określenie kryterium pozwalającego wartościować źródła informacji między sobą. Poszukiwane kryterium będzie nosiło nazwę entropii źródła informacji. Słowo entropia może być w aktualnym kontekście nieco mylące, ponieważ najpowszechniejsze rozumienie entropii związane jest z termodynamiką (określając miarę nieuporządkowania), skąd przeniknęło do znaczenia niemal potocznego w rozumieniu ogólnego nieuporządkowania czy też komplikacji. W rozumieniu teorii informacji entropia źródła informacji nie ma związków z nieuporządkowaniem i intuicyjnie odzwierciedla przeciętną (w potocznym rozumieniu) ilość informacji źródła. Przeciętność mogłaby oznaczać średnią ilość informacji związaną z pojedynczym zdarzeniem elementarnym (sugerując średnią arytmetyczną), jednakże należy uwzględnić, że nie każda ilość informacji jest równie prawdopodobna.

Powyższe rozważania prowadzą do definicji entropii źródła informacji sformułowanej następująco:

Źródło informacji dysponujące n zdarzeniami elementarnymi z prawdopodobieństwami p_1, …, pn ma entropię źródła informacji (oznaczaną przez H) określoną formułą:

Łatwo zauważyć, że powyższy wzór jest ważoną średnią arytmetyczną ilości informacji, z wagami określonymi poprzez prawdopodobieństwa.

Jedną z inspiracji do napisania czytanego podrozdziału było określenie przeciętnej ilości informacji źródła oraz kryterium jakościowego pozwalającego różnicować źródła informacji. Intuicję „przeciętności” można nieco rozszerzyć, traktując ją jak wiarygodność i ustalając w ten sposób kryterium jakościowe. Lepszym (bardziej wiarygodnym) źródłem informacji jest źródło o większej entropii.

Dla wzmocnienia intuicji rozważmy dwa źródła informacji z pewną analogią do środków masowego przekazu. Pierwsze źródło (w potocznym rozumieniu „poważne”) nie goni za sensacją (sprawdza uważnie nieprawdopodobne informacje aż czasami przestają być one sensacjami), czyli nie publikuje zdarzeń o skrajnie niskim prawdopodobieństwie (bardzo interesujących). Zarazem pierwsze źródło nie publikuje rzeczy oczywistych (dla sztucznego zapełnienia łamów treścią), ale wyłącznie rzeczy coś wnoszące (w naszym przypadku omijające zdarzenia o dużym prawdopodobieństwie). Dla ułatwienia przyjmijmy, że pierwsze źródło dysponuje ośmioma zdarzeniami o równych prawdopodobieństwach wynoszących (być może jest źródłem bez sensacji, ale zarazem bez bzdur). Entropia pierwszego źródła wynosi:

Rozpatrzmy teraz drugie źródło informacji, również dysponujące ośmioma zdarzeniami o prawdopodobieństwach . Widzimy, że trzy zdarzenia dają mało informacji, jednak dwa inne są prawdziwymi sensacjami z uwagi na ich niskie prawdopodobieństwo. Tym samym drugie źródło wydaje się nieco tabloidyzujące. Entropia drugiego źródła wynosi:

Łatwo zauważyć, że z racji większej wartości entropii pierwsze źródło informacji, mniej sensacyjne, ale rzetelne, jest bardziej wiarygodne niż źródło informacji goniące za sensacjami.