Informatyka i nauki pokrewne.pdf

1 Informatyka i nauki pokrewne.

Na ka ż dym kroku słyszymy nazw ę informatyka. Wszystko, co wi ąż esi ę z komputerami,

skłonni jeste ś my okre ś la ć jako informatyk ę . Wprowadzamy do szkół przedmiot o nazwie

„informatyka”... Czym zajmuje si ę ta dziedzina wiedzy? Artykuły na tematy

informatyczne w prasie najcz ęś ciej dotycz ą technologii budowy komputerów lub

oprogramowania u ż ytkowego i tak naprawd ę nic wspólnego z informatyk ą nie maj ą .W

tym krótkim rozdziale spróbuj ę przedstawi ć podstawowe koncepcje informatyki, jej

zwi ą zek ze ś wiatem komputerów i ich zastosowa ń . Jest to najbardziej „teoretyczny” z

rozdziałów tej ksi ąż ki.

Jak ju ż wspominałem w poprzednim rozdziale informatyka jest dyscyplin ą całkiem

młod ą ,powstał ą w połowie lat 60-tych dzi ę ki rozwojowi matematyki i elektroniki. Ten

podział istnieje z grubsza do dzisiaj: informatyka teoretyczna, uprawiana na uniwersy-

tetach, zwi ą zana jest z matematyk ą , podczas gdy informatyka techniczna, uprawiana na

politechnikach, zwi ą zana jest z mikroelektronik ą i zastosowaniami metod

komputerowych. Silne zespoły badawcze informatyków pracuj ą

równie ż

w wielkich

firmach komputerowych.

Najwi ę ksz ą i najstarsz ą (zało ż on ą w 1947 roku) organizacj ą

skupiaj ą c ą informatyków jest ACM, A ssociation for C omputing

M achinery (dosłownie „Stowarzyszenie zajmuj ą ce si ę maszyneri ą

obliczeniow ą ). Wła ś nie to stowarzyszenie opublikowało w 1968

roku zalecenia dla nowo powstaj ą cych programów studiów

informatycznych, daj ą cpocz ą tek „naukom komputerowym”

(computer science) w USA i „informatyce” w Europie. Nie s ą to

zbyt szcz ęś liwe nazwy: nauka o komputerach bardzo zaw ęż a

istot ę algorytmiki , wiedzy, dotycz ą cej sposobów rozwi ą zywania

zagadnie ń w oparciu o szczegółowe przepisy, czyli algorytmy .

Algorytmika to fundament informatyki, a jednocze ś nie bardzo wa ż na dyscyplina dla

techniki, ekonomii oraz wszystkich nauk matematyczno-przyrodniczych. Do

sprawdzenia, dok ą d doprowadzi nas dany algorytm, najłatwiej jest u ż ywa ć komputerów,

ale w zasadzie mo ż na to równie ż zrobi ć przy pomocy ołówka i kartki papieru. W tym

sensie informatyka teoretyczna wcale nie zale ż y od istnienia komputerów a „prawdziwy

informatyk” komputerami si ę brzydzi (do niedawna była to do ść cz ę sto spotykana

postawa w ś ród informatyków, dzisiaj prawie wszyscy u ż ywaj ą komputerów przynajmniej

jako maszyn do pisania).

Fascynuj ą cy ś wiat komputerów

Z drugiej strony informatyka skupia si ę na poj ę ciu „informacji”, równie ż nie oddaj ą cej

istoty zagadnienia. 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 ść ztego,

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 ć ”. Jest to wi ę cnaukaotym,como ż na osi ą gn ąć przy pomocy procesów

przetwarzania informacji (procesów obliczeniowych) i w tym sensie jest niezale ż na od

sprz ę tu, umo ż liwiaj ą cego wykonywanie oblicze ń . W pismach popularnonaukowych jak i

w prasie codziennej pod okre ś leniem „informatyka” rozumie si ę najcz ęś ciej zupełnie co ś

innego. Omawiaj ą c odkrycia minionego roku w astronomii, biologii, chemii, fizyce i

informatyce nawet w pismach na wysokim poziomie czytamy z jednej strony o czarnych

dziurach i kwarkach, a wi ę c prawdziwych odkryciach naukowych, a z drugiej o

wprowadzeniu nowych mikroprocesorów czy nowego systemu operacyjnego firmy

Microsoft. Z prawdziw ą informatyk ą nie ma to jednak wiele wspólnego.

1.1

Czym zajmuje si ę informatyka?

Zainteresowania informatyki jako gał ę zi nauki skupiaj ą si ę wokół rozwi ą zywania zada ń

algorytmicznych , czyli takich zada ń , dla których mo ż na znale źć jakie ś formalne

sposoby post ę powania, przepisy, prowadz ą ce do ich rozwi ą zania. Na pierwszy rzut oka

prawie wszystko da si ę zalgorytmizowa ć (tj. znale źć algorytm dla danego zagadnienia),

chocia ż nie zawsze znane algorytmy zapewniaj ą dokładne rozwi ą zania. Wiele zagadnie ń

matematycznych da si ę zalgorytmizowa ć ,w ę kszo ść zagadnie ń zwi ą zanych z

wyszukiwaniem, przesyłaniem i przetwarzaniem informacji, przetwarzaniem d ź wi ę ku i

obrazu równie ż . Nie zawsze jednak mo ż na znale źć algorytmy efektywne ,aw ę c

prowadz ą ce do rozwi ą zania w rozs ą dnym czasie. Niektóre algorytmy s ą wprawdzie

proste, ale wymagaj ą ogromnych oblicze ń , w praktyce trwaj ą cych niesko ń czenie długo.

Informatyka zajmuje si ę wi ę c ocen ą zło ż ono ś ci obliczeniowej algorytmów,

poszukiwaniem efektywnych algorytmów, oraz testowaniem i dowodzeniem ich

poprawno ś ci .

W tych zagadnieniach, dla których ś cisłe rozwi ą zania nie s ą znane, poszukuje si ę

przybli ż onych metod rozwi ą zywania czyli szuka si ę algorytmów heurystycznych ,

metod, które nie gwarantuj ą rozwi ą zania ale cz ę sto mog ą by ć pomocne. Ten ostatni

rodzaj algorytmów rozwijany jest przez specjalistów od sztucznej inteligencji , działu

Fascynuj ą cy ś wiat komputerów

informatyki, zajmuj ą cego si ę procesami dla których nie znamy (by ć mo ż e nie istniej ą )

efektywnych algorytmów rozwi ą za ń . Sztucznej inteligencji po ś wi ę ciłem osobny rozdział.

Załó ż my, ż e chcemy rozwi ą za ć zagadnienie, w którym mamy do czynienia z pewn ą

liczb ą N elementów. Problemy algorytmiczne dzieli si ę na łatwo rozwi ą zywalne, czyli

takie, dla których istniej ą (chocia ż nie musz ą by ć znane, to czasami mo ż na udowodni ć ,

ż eistniej ą ) algorytmy efektywne, pozwalaj ą ce rozwi ą za ć problem w czasie nie wi ę kszym

ni ż jaka ś pot ę ga liczby N , np. proporcjonalnym do N lubdokwadratu N .Oczywi ś cie

nale ż y szuka ć najbardziej efektywnych algorytmów, których zale ż no ść od liczby

elementów jest najni ż sza. Dla przykładu, jest wiele algorytmów sortowania

(porz ą dkowania) listy obiektów. Typowe algorytmy wymagaj ą około N 2 operacji dla N

obiektów, s ą jednak i takie, które porz ą dkuj ą w znacznie krótszym czasie, proporcjonal-

nym do ni ż szej pot ę gi N . Odkryto jednak blisko 1000 interesuj ą cych problemów

trudnych, czyli takich, dla których czas potrzebny do ich rozwi ą zania ro ś nie szybciej ni ż

dowolna pot ę ga N . Takie trudne zagadnienia okre ś la si ę jako NP-trudne. NP to skrót od

„nie-wielomianowa” (zale ż no ść czasu rozwi ą zania od rozmiaru problemu).

Wiele prostych w sformułowaniu zagadnie ń optymalizacji nale ż y do zagadnie ń trudnych,

np. „problem w ę druj ą cego komiwoja ż era”: jak znale źć najkrótsz ą drog ę ,ł ą cz ą c ą N miast

odwiedzaj ą cka ż de tylko jeden raz. Ciekaw ą klas ą zło ż ono ś ci s ą problemy „NP-zupełne”.

Dodanie przymiotnika „zupełne” wi ąż es ę ze zdumiewaj ą cym twierdzeniem, i ż

wszystkieteproblemymo ż na by rozwi ą za ć w łatwy sposób, gdyby chocia ż jeden dał si ę

łatwo rozwi ą za ć !Czytakierozwi ą zanie istnieje? Do dzisiaj nie udało si ę tego nikomu

udowodni ć . Wiadomo natomiast, ż eistniej ą zagadnienia, dla których nie mo ż na wcale

znale źć algorytmu rozwi ą zania, zagadnienia nierozstrzygalne, a nawet problemy wysoce

nierozstrzygalne. Czytelników zainteresowanych problemami klas zło ż ono ś ci musz ę

jednak odesła ć do literatury dotycz ą cej podstaw informatyki.

Algorytmy wymagaj ą danych pocz ą tkowych i tworz ą nowe dane, b ę d ą ce rozwi ą zaniem

problemu. Dane mog ą mie ć skomplikowan ą struktur ę ,st ą djednazgał ę zi informatyki

zajmuje si ę strukturami danych , czyli organizacj ą danych ró ż nych typów w logicznie

powi ą zane ze sob ą struktury. Do najprostszych struktur danych nale żą tablice liczb, do

bardzo zło ż onych nale żą struktury danych zapisuj ą ce informacje o całym prze-

dsi ę biorstwie, czyli wzorce, według których zorganizowana jest informacja

przechowywana w bazach danych. Przedmiotem bada ń informatyków s ą sposoby

reprezentacji danych, szyfrowanie i sposoby zabezpieczenia danych przed odczytaniem

przez niepowołane osoby a tak ż e okre ś laniem ilo ś ci informacji, zawartej w danych.

Do najprostszych danych nale żą liczby, czyli dane numeryczne: mog ą to by ć liczby

całkowite nale żą ce do ograniczonego zakresu, mog ą to by ć liczby wymierne zapisane z

okre ś lon ą

dokładno ś ci ą

(okre ś lane te ż

niezbyt precyzyjnie jako „liczby rzeczywiste”),

Fascynuj ą cy ś wiat komputerów

Syn

Córka

Wnuk-1

Wnuk-2

Wnuk-3

Wnuk-4

Prawnuk-1

Prawnuk-2

Cz ę sto stosowan ą struktur ą w informatyce s ą drzewa, wychodz ą ce od w ę za zwanego

korzeniem, od którego wybiegaj ą w ę zy potomne. W ę zy na najni ż szym poziomie, nie

maj ą ce potomstwa, nazywa si ę li ść mi.

mog ą to by ć równie ż tablice liczb. Jednowymiarowe tablice nazywamy wektorami ,

dwuwymiarowe tablicami a wielowymiarowe po prostu tabelami . Bardzo ogóln ą

struktur ą danych jest lista . Uproszczone listy, dla których dozwala si ę jedynie na

operacje dokładania lub usuwania ostatniego elementu nazywa si ę stosami (podobnie jak

stos naczy ń ), natomiast listy, dla których dozwala si ę na operacje dokładania elementów

na ko ń cu i usuwania elementów na pocz ą tku listy nazywamy kolejkami . Kolejki nazywa

si ę te ż listami FIFO, od angielskiej nazwy „First-In-First-Out”, czyli ten element, który

pierwszy wszedł na list ę zejdzie z niej pierwszy.

Dane mog ą mie ć bardziej zło ż one struktury, których elementy powi ą zane s ą ze sob ą w

skomplikowanych sposób. Cz ę sto stosowan ą struktur ą jest drzewo , podobne do drzewa

genealogicznego (por. rysunek), zawieraj ą ce powi ą zane ze sob ą w ę zły. Jeden wyró ż niony

w ę zeł pocz ą tkowy nazywa si ę korzeniem . Odchodz ą od niego w ę zły potomne ,maj ą ce z

kolei swoje potomstwo, a ż dochodzimy do li ś ci drzewa ,czyliw ę złów bez potomstwa.

Drzewo, w którym dany w ę zeł ma co najwy ż ej dwa w ę zły potomne nazywa si ę drzewem

binarnym. Drzewa nie mog ą zawiera ć p ę tli wewn ę trznych, mog ą si ę jedynie rozrasta ć .

Bardziej zło ż onymi strukturami, dopuszczaj ą cymi dowolne powi ą zania w ę złów ze sob ą ,

s ą

grafy . Linie ł ą cz ą ce ze sob ą

w ę zły grafu nazywa si ę

łukami. Mog ą

one mie ć

Fascynuj ą cy ś wiat komputerów

wyró ż niony kierunek okre ś laj ą cy

dozwolon ą kolejno ść przechodzenia

od w ę zła do w ę zła przy w ę drowaniu

po grafie. Informatycy wyró ż niaj ą

wiele rodzajów grafów.

Start

i=1

Jedn ą zw ż niejszych dyscyplin

informatyki jest teoria j ę zyków

programowania , zwana równie ż

teori ą j ę zyków algorytmicznych,

teori ą j ę zyków formalnych lub teori ą

j ę zyków sztucznych. Formalne

zapisanie algorytmu wymaga

zdefiniowania jakiego ś zestawu

symboli-instrukcji wraz z regułami

ich u ż ycia. Reguły te nazywa si ę

gramatyk ą lub składni ą i razem z

zestawem symboli tworz ą one pewien

j ę zyk programowania. Algorytm

zapisany w takim j ę zyku nazywa si ę

programem .Nauk ę reguł składni i

symboli j ę zyka programowania,

konstruowania struktur danych

dopuszczalnych przez te reguły i

zapisywania algorytmów w tym

j ę zyku formalnym nazywa si ę nauk ą

programowania. Formalne

okre ś lenie wymaga ń , ą cych

struktur danych nazywa si ę

specyfikacj ą . Z pisaniem

specyfikacji i dowodzeniem, ż edany

program je spełnia zwi ą zanych jest

wiele wa ż nych problemów.

a=a(1)

Tak

i=N ?

max=a

Nie

i=i+1

Koniec

Tak

a>a(i)?

Nie

a=a(i)

Diagram przedstawiaj ą cy algorytm szukania

maksymalnego elementu dla N-wymiarowego

wektora a(i). Test przedstawione s ą w ramkach

typurombuaprosteinstrukcjewramkach

prostok ą tnych.

Programy realizowane s ą przez procesory . Dla teoretyka informatyki procesory s ą

matematycznie opisanymi urz ą dzeniami przyjmuj ą ce sko ń czon ą liczb ę ró ż nych stanów,

nazywanymi automatami sko ń czonymi lub automatami Turinga, gdy ż do zagadnie ń

obliczalno ś ci wprowadził je jeszcze w 1936 roku angielski matematyk Alan Turing.

Teoria automatów sko ń czonych nale ż y do podstaw informatyki i odpowiada na pytania,

jakiego rodzaju problemy mo ż na przy pomocy oblicze ń rozwi ą za ć , oraz jakie klasy

urz ą dze ń s ą do tego potrzebne. Chocia ż prawdziwe mikroprocesory spotykane w

komputerach s ą bardzo zło ż one ich mo ż liwo ś ci obliczeniowe nie odbiegaj ą od tych, które

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: