Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1Podstawowezasady
analizyalgorytmów
W
ściobliczeniowej.Omawiamyelementarnestrukturydanychdefiniowaneabstrakcyjnie
tymrozdzialeprzedstawiamypodstawowepojęciastosowaneprzybadaniualgo-
rytmówistrukturdanych.Przedewszystkimwyjaśniamy,naczympolegaanaliza
algorytmuwdwóchgłównychaspektach:poprawnościsemantycznejizłożono-
(jakolisty,zbiory,grafy,drzewaitd.),zmożliwymiróżnymikonkretnymiimplementacjami
(reprezentacjami).Nakońcurozdziałuprzedstawiamypodstawowemetodykonstruowania
efektywnychalgorytmów(metodandzielizwyciężaj”,programowaniedynamiczne,metoda
zachłanna,metodakolejnychtransformacji).
Analizaalgorytmówtodziałinformatykizajmującysięszukaniemnajlepszychalgoryt-
mówdlazadańkomputerowych.Polegaonamiędzyinnyminaznalezieniuodpowiedzina
następującepytania.
1.Czydanyproblemmożebyćrozwiązanynakomputerzewdostępnymczasieipamięci?
2.Któryzeznanychalgorytmównależyzastosowaćwdanychokolicznościach?
3.Czyistniejelepszyalgorytmodrozważanego?Amożejestonoptymalny?
4.Jakuzasadnić,żestosującdanyalgorytm,rozwiążesięzamierzonezadanie?
Dokonującanalizyalgorytmu,zwracamyuwagęnajegopoprawnośćsemantyczną,prostotę,
czasdziałania,ilośćwykorzystywanejpamięci,optymalnośćorazokoliczności,wjakich
należygoużywać,awjakichnie.
1.1.
Złożonośćobliczeniowa
Złożonośćobliczeniowąalgorytmudefiniujesięjakoilośćzasobówkomputerowych
potrzebnychdojegowykonania.Podstawowymizasobamirozważanymiwanaliziealgoryt-
mówsączasdziałaniaiilośćwykorzystywanejpamięci.
