Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1Podstawowepojęciainformatyki
7
Złożonośćczasowadanegoalgorytmuinformujebowiemotym,jakwrazze
wzrostemwielkościprzetwarzanychdanychzmieniasięliczbaelementarnych
operacjimaszynyniezbędnychdowykonaniazadania.Chodzi,rzeczjasna,
ozgrubneoszacowanietypufunkcjiwiążącejrozmiardanychzliczbąopera-
cji;wprzypadkualgorytmównajbardziejefektywnychsątofunkcjeliniowelub
wielomianowe,wprzypadkualgorytmównajmniejsprawnych-wykładnicze9.
Rozważmynakoniecsprawęrzekomejniezawodnościalgorytmów.Otóż
twierdzisięniejednokrotnie,główniewpublikacjachnie-informatycznych,że
algorytm-opisującypewnegorodzajumetodęrozwiązywaniaproblemów-jest
toschematniezawodny,awięcgwarantującyrozwiązanieproblemudanego
typuwskończonejliczbiekroków(Por.[Szaniawski1994],[Kozielecki1992]).
Czyopiniataznajdujeswojepotwierdzeniewaktualnejpraktycejęzykowej
informatyków?Okazujesię,żenie.Współcześniebowiemmówisięodwóch
ważnychrodzajachalgorytmów,któreniewkażdymwypadkuzapewniająro-
związanieskojarzonegoznimiproblemu.Popierwsze,sątoalgorytmypro-
babilistyczne,czylitakie,wktórychpewneoperacjesąwywoływanelosowo,
zzałożonymzgórylubstopniowomodyfikowanymprawdopodobieństwem(ich
ważnąpodklasęstanowiąalgorytmyewolucyjne).Podrugie,sątoalgorytmy
heurystyczne,czylitakie,któresprawdzająsięwystarczającodobrzedla
większościdanychpoczątkowych,leczniedająstuprocentowejpewnościcodo
każdorazowegorozwiązaniaproblemu;najczęściejzaichpomocąrozwiązujesię
tzw.zagadnieniaoptymalizacyjne,gdziedążysiędorozwiązaniaoptymalnego
(czyliwystarczającodobrego),anieidealnego10.
1.1.3Automat
Ogólnacharakterystykainformatykijakonaukioalgorytmicznymprzetwarza-
niuinformacjibyłabyniepełna,gdybyśmyniepodkreślilifaktu,żesystemy
informatycznesązdolnedodziałanianienadzorowanego,czyliauto-
matycznego.Automatyzacja,októrejmowa,madwaaspekty:symulacyjny
9Ponieważalgorytmyopisująpewnegorodzajumetodyrozwiązywaniaproblemów,
funkcjazłożonościczasowejdostarczawygodnegokryteriumpodziałuproblemów.
Itak:problemy,dlaktórychistniejąalgorytmyozłożonościliniowejnazywasięli-
niowymi,problemy,dlaktórychniemaalgorytmówlepszychniżteozłożoności
wielomianowej-wielomianowymiitd.Faktemjest,żeistniejąitakieproblemy,co
doktórychudowodniononiemożnośćzaprojektowaniajakichkolwiekalgorytmów.
Przynajmniejtakwyglądasprawawprzypadkualgorytmówtradycyjnych(tj.nie
zawierającychelementówprobabilistycznych).Por.[Harel2000(1987)]
10Przykłademzagadnieniaoptymalizacyjnegojestnastępującyproblemkomiwoja-
żera:dladanejsiecinmiastopodanychodległościachmiędzyposzczególnymi
miastamiznaleźćnajkrótsząspośróddróg,któreprzebiegająprzezkażdezmiast
dokładnieraz.Ponieważproblemtenmazłożonośćwykładniczą,dlaodpowiednio
dużychnnieistniejeefektywnyalgorytmrozwiązania.Dlategoteżproponujesię
różnealgorytmyheurystyczne,którepozwalajądrogimożliwienajkrótsze(znaj-
dująwięcrozwiązaniaoptymalne,anieidealne).Por.[Bolc,Cytowski1989i1991]
