Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00150 007848 11008889 na godz. na dobę w sumie
Algorytmy bez tajemnic - książka
Algorytmy bez tajemnic - książka
Autor: Liczba stron: 224
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-7482-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> techniki programowania
Porównaj ceny (książka, ebook, audiobook).

Poznaj świat algorytmów!

Każdy program działa według określonego algorytmu - Twoja nawigacja GPS, system płatności elektronicznych, wyszukiwarka Google. Algorytmy są jak przepisy kucharskie: zrób to, sprawdź tamto. Jednak konsekwencje popełnienia błędu w algorytmie są zupełnie inne niż w przypadku niesprawdzonego przepisu. To właśnie algorytmy decydują o czasie wykonania skomplikowanych operacji przez programy komputerowe, a ich odpowiednia lub nieodpowiednia implementacja może sprawić, że Twój projekt wart miliony odniesie sukces lub poniesie porażkę.

Dzięki tej książce będziesz mógł bezboleśnie wkroczyć w świat algorytmów. W trakcie lektury dowiesz się, czym tak naprawdę są algorytmy, jak się je projektuje i prezentuje. Po wstępie teoretycznym poznasz najpopularniejsze algorytmy sortowania i wyszukiwania, algorytmy znajdowania najkrótszej ścieżki oraz algorytmy operujące na ciągach znaków. Następnie przejdziesz do najciekawszych zagadnień związanych z kryptografią i kompresją danych. Zastanawiasz się, czy są miejsca, w których znane algorytmy nie radzą sobie zbyt dobrze? To problemy NP-zupełne - z nimi też będziesz mógł się zaznajomić. Książka ta jest interesującym przewodnikiem po świecie algorytmów, a zarazem przyjemną lekturą dla każdego programisty i pasjonata informatyki.

Poznaj algorytmy:

Dowiedz się, jak działają aplikacje kompresujące i szyfrujące!

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Tytuł oryginału: Algorithms Unlocked Tłumaczenie: Zdzisław Płoski ISBN: 978-83-246-7482-4 © Helion 2013. All rights reserved. © 2013 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Wydawnictwo HELION dołożyło wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie bierze jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Wydawnictwo HELION nie ponosi również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/algbet Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:318)ci Przedmowa 1 Co to s(cid:160) algorytmy i dlaczego warto po(cid:318)wi(cid:164)ca(cid:247) im uwag(cid:164)? Poprawno(cid:314)(cid:243) U(cid:343)ytkowanie zasobów Algorytmy komputerowe dla niekomputerowców Algorytmy komputerowe dla komputerowców Co czyta(cid:243) dalej 2 Jak opisywa(cid:247) i ocenia(cid:247) algorytmy komputerowe Jak opisywa(cid:243) algorytmy komputerowe Jak charakteryzowa(cid:243) czasy dzia(cid:167)ania Niezmienniki p(cid:163)tli Rekursja Co czyta(cid:243) dalej 3 Algorytmy sortowania i wyszukiwania Wyszukiwanie binarne Sortowanie przez wybieranie Sortowanie przez wstawianie Sortowanie przez scalanie Sortowanie szybkie Podsumowanie Co czyta(cid:243) dalej 4 Dolne ograniczenie sortowania i sposoby jego przezwyci(cid:164)(cid:349)enia Regu(cid:167)y sortowania Dolne ograniczenie sortowania przez porównania Pokonywanie ograniczenia dolnego w sortowaniu przez zliczanie Sortowanie pozycyjne Co czyta(cid:243) dalej 9 15 16 17 19 20 21 23 23 29 33 34 36 37 39 43 46 50 59 66 69 71 71 72 73 79 81 Kup książkęPoleć książkę 6 Algorytmy bez tajemnic 5 Skierowane grafy acykliczne Skierowane grafy acykliczne Sortowanie topologiczne Jak reprezentowa(cid:243) graf skierowany Czas dzia(cid:167)ania sortowania topologicznego (cid:313)cie(cid:343)ka krytyczna w diagramie PERT Najkrótsza (cid:314)cie(cid:343)ka w skierowanym grafie acyklicznym Co czyta(cid:243) dalej 6 Najkrótsze (cid:318)cie(cid:349)ki Algorytm Dijkstry Algorytm Bellmana-Forda Algorytm Floyda-Warshalla Co czyta(cid:243) dalej 7 Algorytmy napisowe Najd(cid:167)u(cid:343)szy wspólny podci(cid:159)g Zamiana napisu na inny Dopasowywanie napisów Co czyta(cid:243) dalej 8 Podstawy kryptografii Proste szyfry podstawieniowe Kryptografia z kluczem symetrycznym Kryptografia z kluczem jawnym Kryptosystem RSA Kryptosystemy hybrydowe Obliczanie liczb losowych Co czyta(cid:243) dalej 9 Kompresja danych Kody Huffmana Faksy Kompresja LZW Co czyta(cid:243) dalej 83 87 87 90 92 92 96 100 101 102 111 115 123 125 125 130 137 144 145 146 147 151 153 160 161 162 163 164 170 171 180 Kup książkęPoleć książkę 10 Trudne (?) problemy Br(cid:159)zowe furgonetki Klasy P i NP oraz NP-zupe(cid:167)no(cid:314)(cid:243) Problemy decyzyjne i redukcje Problem matka Próbnik problemów NP-zupe(cid:167)nych Ogólne strategie Perspektywy Problemy nierozstrzygalne Podsumowanie Co czyta(cid:243) dalej Literatura Skorowidz Spis tre(cid:315)ci 7 181 181 184 186 189 191 204 206 208 210 211 213 215 Kup książkęPoleć książkę 8 Algorytmy bez tajemnic Kup książkęPoleć książkę 1 Co to s(cid:160) algorytmy i dlaczego warto po(cid:318)wi(cid:164)ca(cid:247) im uwag(cid:164)? Zacznijmy od pytania, które mi cz(cid:163)sto zadaj(cid:159): „Co to jest algorytm?”1. Ogólna odpowied(cid:341) mog(cid:167)aby by(cid:243) taka: „zbiór kroków prowadz(cid:159)cych do wyko- nania zadania”. Na co dzie(cid:295) stosujesz ró(cid:343)ne algorytmy. Masz algorytm mycia z(cid:163)bów: otwierasz tubk(cid:163) z past(cid:159), bierzesz szczoteczk(cid:163) do r(cid:163)ki, wyciskasz na szczoteczk(cid:163) tyle pasty, ile trzeba, zamykasz tubk(cid:163), wk(cid:167)adasz szczoteczk(cid:163) do jednej (cid:243)wiartki paszczy, przesuwasz ni(cid:159) w gór(cid:163) i w dó(cid:167) (oraz w prawo i w lewo) przez N sekund itd. Je(cid:314)li mu- sisz doje(cid:343)d(cid:343)a(cid:243) do pracy, masz swój algorytm dojazdu do pracy. I tak dalej. Jednak ta ksi(cid:159)(cid:343)ka zajmuje si(cid:163) algorytmami, które dzia(cid:167)aj(cid:159) na komputerach, a ogól- nie rzecz ujmuj(cid:159)c — na urz(cid:159)dzeniach obliczeniowych. Z algorytmami wykonywa- nymi na komputerach jest podobnie jak z tymi, które wykonujesz na co dzie(cid:295). Korzystasz z GPS-u, (cid:343)eby znale(cid:341)(cid:243) drog(cid:163)? (cid:342)eby j(cid:159) odnale(cid:341)(cid:243), wykonuje on algorytm, który nazywamy „najkrótsza (cid:314)cie(cid:343)ka”. Kupujesz co(cid:314) w Internecie? U(cid:343)ywasz wtedy (a przynajmniej nale(cid:343)a(cid:167)oby!) bezpiecznej witryny sieciowej, która wykonuje algo- rytm szyfrowania. Gdy kupujesz jakie(cid:314) towary w Sieci, kto Ci je dostarcza? Firma kurierska? Korzysta ona z algorytmów przydzielaj(cid:159)cych paczki do furgonetek, a po- tem ustalaj(cid:159)cych kolejno(cid:314)(cid:243), w jakiej ka(cid:343)dy kierowca powinien te paczki rozwozi(cid:243). Algorytmy dzia(cid:167)aj(cid:159) w komputerach na ka(cid:343)dym kroku: w Twoim laptopie, smartfonie, na serwerach lub w systemach wbudowanych (np. w Twoim samochodzie czy w mi- krofalówce, w systemach klimatyzacji) — wsz(cid:163)dzie! Co ró(cid:343)ni algorytmy wykonywane na komputerach od algorytmu wykonywa- nego przez Ciebie? Ty potrafisz tolerowa(cid:243) algorytm, je(cid:314)li jest on niedok(cid:167)adnie opisany, a komputer nie. Na przyk(cid:167)ad, je(cid:314)li jedziesz do pracy, Twój algorytm jed(cid:341)-do-pracy móg(cid:167)by zawiera(cid:243) tak(cid:159) klauzul(cid:163): „je(cid:314)li jest t(cid:167)oczno, wybierz inn(cid:159) tras(cid:163)”. Ty mo(cid:343)esz wiedzie(cid:243), co rozumiesz pod okre(cid:314)leniem „jest t(cid:167)oczno”, natomiast komputer tego nie pojmie. Dlatego algorytm komputerowy jest zbiorem kroków prowadz(cid:159)cych do wyko- nania zadania, opisanym na tyle precyzyjnie, (cid:343)e potrafi go wykona(cid:243) komputer. Na czym polega ta precyzja, wiesz, je(cid:314)li masz cho(cid:243) troch(cid:163) do(cid:314)wiadczenia w programo- waniu komputerów w Javie, C, C++, Pythonie, Fortranie, Mathlabie lub w czym(cid:314) podobnym. Je(cid:314)li nie masz w dorobku ani jednego programu komputerowego, to niewykluczone, (cid:343)e poczujesz ten stopie(cid:295) dok(cid:167)adno(cid:314)ci, przygl(cid:159)daj(cid:159)c si(cid:163), jak opisuj(cid:163) algorytmy w tej ksi(cid:159)(cid:343)ce. Przejd(cid:341)my do nast(cid:163)pnego pytania: „Czego oczekujemy od algorytmu komputero- wego?”. 1 Lub, jak by rzek(cid:167) mój kolega, z którym gram w hokeja: „What’s a nalgorithm?”. Kup książkęPoleć książkę 16 Algorytmy bez tajemnic Algorytmy komputerowe rozwi(cid:159)zuj(cid:159) problemy obliczeniowe. Od algorytmu komputerowego oczekujemy dwóch rzeczy: maj(cid:159)c dane do problemu, powinien zawsze wytwarza(cid:243) poprawne rozwi(cid:159)zanie tego problemu, a robi(cid:159)c to, powinien oszcz(cid:163)dnie zu(cid:343)ywa(cid:243) zasoby obliczeniowe. Przyjrzyjmy si(cid:163) obu tym postulatom. Poprawno(cid:318)(cid:247) Co oznacza poprawne rozwi(cid:159)zanie problemu? Na ogó(cid:167) potrafimy precyzyjnie okre- (cid:314)li(cid:243), co powinno zawiera(cid:243) poprawne rozwi(cid:159)zanie. Na przyk(cid:167)ad, je(cid:314)li Twój GPS wy- twarza poprawne rozwi(cid:159)zanie, gdy chodzi o znalezienie najlepszej trasy podró(cid:343)y, to mog(cid:167)oby to polega(cid:243) na wybraniu takiej trasy spo(cid:314)ród wszystkich mo(cid:343)liwych do wytyczenia mi(cid:163)dzy miejscem Twojego pobytu a miejscem docelowym, któr(cid:159) dotrzesz tam najszybciej. Albo trasy mo(cid:343)liwie najkrótszej. Albo takiej, która nie tylko po- prowadzi Ci(cid:163) do celu najszybciej, lecz równie(cid:343) pozwoli unikn(cid:159)(cid:243) p(cid:167)acenia myta. Ja- sne, (cid:343)e informacje, których Twój GPS u(cid:343)ywa do wyznaczenia trasy, mog(cid:159) nie od- powiada(cid:243) rzeczywisto(cid:314)ci. O ile nie ma on dost(cid:163)pu w czasie rzeczywistym do danych o ruchu drogowym, móg(cid:167)by przyj(cid:159)(cid:243), (cid:343)e czas potrzebny do przebycia drogi równa si(cid:163) d(cid:167)ugo(cid:314)ci drogi podzielonej przez dopuszczaln(cid:159) na niej pr(cid:163)dko(cid:314)(cid:243). Je(cid:314)li jednak droga jest zat(cid:167)oczona, GPS móg(cid:167)by Ci (cid:341)le doradzi(cid:243) w poszukiwaniach najszybszej trasy. Mimo to nadal mo(cid:343)emy uzna(cid:243), (cid:343)e algorytm wytyczania trasy dzia(cid:167)a poprawnie — nawet je(cid:314)li nie mo(cid:343)na tego powiedzie(cid:243) o jego danych wej(cid:314)ciowych; dla zadanego wej(cid:314)cia algorytm trasuj(cid:159)cy okre(cid:314)la tras(cid:163) najszybsz(cid:159). Z kolei dla pewnych problemów ustalenie, czy dany algorytm wytwarza po- prawne rozwi(cid:159)zanie, mo(cid:343)e si(cid:163) okaza(cid:243) trudne lub nawet niemo(cid:343)liwe. Jako przyk(cid:167)ad we(cid:341)my optyczne rozpoznawanie znaków. Czy ten obrazek o wymiarach 11 (cid:117) 6 piksli jest cyfr(cid:159) 5, czy liter(cid:159) S? Niektórzy powiedz(cid:159), (cid:343)e to pi(cid:159)tka, podczas gdy inni — (cid:343)e S, jak zatem mogliby- (cid:314)my uzna(cid:243) poprawno(cid:314)(cid:243) lub niepoprawno(cid:314)(cid:243) decyzji komputerowej? Nie da si(cid:163). W tej ksi(cid:159)(cid:343)ce skoncentrujemy si(cid:163) na algorytmach komputerowych, których rozwi(cid:159)zania s(cid:159) znane. Czasami jednak godzimy si(cid:163) z tym, (cid:343)e algorytm komputerowy produkuje nie- poprawn(cid:159) odpowied(cid:341), o ile tylko potrafimy panowa(cid:243) nad tym, jak cz(cid:163)sto mu si(cid:163) to zdarza. Dobry przyk(cid:167)ad stanowi szyfrowanie. Powszechnie u(cid:343)ywany krypto- system RSA polega na okre(cid:314)laniu, czy du(cid:343)e liczby — naprawd(cid:163) du(cid:343)e, maj(cid:159)ce setki cyfr — s(cid:159) pierwsze. Je(cid:314)li zdarzy(cid:167)o Ci si(cid:163) pisa(cid:243) programy komputerowe, to jednym z nich by(cid:167) pewnie taki, który sprawdza(cid:167), czy liczba n jest pierwsza. Móg(cid:167) on bada(cid:243) wszystkie potencjalne podzielniki od 2 do n – 1 i je(cid:314)li który(cid:314) z nich okaza(cid:167) si(cid:163) rzeczywi(cid:314)cie podzielnikiem n, to n by(cid:167)a liczb(cid:159) z(cid:167)o(cid:343)on(cid:159). Je(cid:314)li (cid:343)adna liczba mi(cid:163)dzy 2 a n – 1 nie jest podzielnikiem n, to n jest pierwsza. Je(cid:314)li jednak n ma setki cyfr, to potencjalnych podzielników jest mnóstwo — tak du(cid:343)o, (cid:343)e nawet naprawd(cid:163) szybki Kup książkęPoleć książkę Rozdzia(cid:167) 1. • Co to s(cid:159) algorytmy i dlaczego warto po(cid:315)wi(cid:163)ca(cid:244) im uwag(cid:163)?(cid:31) 17 dn / n (bo je(cid:314)li d jest wi(cid:163)ksze ni(cid:343) n i d jest podzielnikiem n, to komputer nie da(cid:167)by rady tego sprawdzi(cid:243) w rozs(cid:159)dnym czasie. Oczywi(cid:314)cie móg(cid:167)by(cid:314) dokona(cid:243) pewnych ulepsze(cid:295), na przyk(cid:167)ad wyeliminowa(cid:243) wszystkie kandydatki pa- rzyste po wykazaniu, (cid:343)e 2 nie jest podzielnikiem, lub poprzesta(cid:243) na dotarciu do jest mniejsze ni(cid:343) n i równie(cid:343) jest podzielnikiem n; je(cid:314)li wi(cid:163)c n ma podzielnik, to znajdziesz go nim dojdziesz do n ). Je(cid:314)li n ma setki cyfr, to chocia(cid:343) n ma oko(cid:167)o o po(cid:167)ow(cid:163) cyfr mniej ni(cid:343) n, nadal jest naprawd(cid:163) wielk(cid:159) liczb(cid:159). I tu dobra wiadomo(cid:314)(cid:243): znamy al- gorytm, który szybko sprawdza, czy liczba jest pierwsza. Z(cid:167)(cid:159) wiadomo(cid:314)ci(cid:159) jest to, (cid:343)e mo(cid:343)e on pope(cid:167)nia(cid:243) b(cid:167)(cid:163)dy. W szczególno(cid:314)ci, je(cid:314)li o(cid:314)wiadcza, (cid:343)e n jest z(cid:167)o(cid:343)ona, to n jest na pewno z(cid:167)o(cid:343)ona, lecz je(cid:314)li o(cid:314)wiadcza, (cid:343)e n jest pierwsza, to istnieje pew- na szansa, (cid:343)e n jest jednak z(cid:167)o(cid:343)ona. Lecz owe z(cid:167)e wiadomo(cid:314)ci nie s(cid:159) a(cid:343) tak z(cid:167)e: mo(cid:343)emy utrzymywa(cid:243) wska(cid:341)nik b(cid:167)(cid:163)du na naprawd(cid:163) niskim poziomie, wynosz(cid:159)- 502 razy. Jest to na tyle rzadko — jeden b(cid:167)(cid:159)d cym na przyk(cid:167)ad jeden b(cid:167)(cid:159)d na ka(cid:343)de raz na ka(cid:343)de sto oktylionów — (cid:343)e wi(cid:163)kszo(cid:314)(cid:243) z nas ze spokojem przyjmuje w RSA okre(cid:314)lanie t(cid:159) metod(cid:159), czy liczba jest pierwsza. Poprawno(cid:314)(cid:243) jest delikatnym zagadnieniem w innej klasie algorytmów, nazywa- nych aproksymacyjnymi. Algorytmy aproksymacyjne (przybli(cid:343)ania pewnej warto- (cid:314)ci — przyp. t(cid:167)um.) s(cid:159) stosowane w problemach optymalizacyjnych, w których chce- my znale(cid:341)(cid:243) najlepsze rozwi(cid:159)zanie wzgl(cid:163)dem pewnej miary ilo(cid:314)ciowej. Znajdowanie najszybszej trasy, wykonywane przez GPS, jest jednym z przyk(cid:167)adów — tu miar(cid:159) ilo(cid:314)ciow(cid:159) jest czas podró(cid:343)y. Dla niektórych problemów nie mamy dobrych algoryt- mów znajduj(cid:159)cych optymalne rozwi(cid:159)zanie w rozs(cid:159)dnym czasie, znamy natomiast algorytm aproksymacyjny, który w zadowalaj(cid:159)cym czasie potrafi znale(cid:341)(cid:243) rozwi(cid:159)za- nie prawie optymalne. Przez „prawie optymalne” zazwyczaj rozumiemy, (cid:343)e ilo(cid:314)ciowa miara rozwi(cid:159)zania znajdowana przez algorytm aproksymacyjny ró(cid:343)ni si(cid:163) pewnym znanym czynnikiem od optymalnej miary ilo(cid:314)ciowej rozwi(cid:159)zania. Je(cid:314)li tylko okre- (cid:314)limy, ile ów po(cid:343)(cid:159)dany czynnik wynosi, mo(cid:343)emy mówi(cid:243), (cid:343)e poprawnym rozwi(cid:159)za- niem algorytmu aproksymacyjnego jest ka(cid:343)de rozwi(cid:159)zanie ró(cid:343)ni(cid:159)ce si(cid:163) tym czynni- kiem od rozwi(cid:159)zania optymalnego. U(cid:349)ytkowanie zasobów Co to znaczy w odniesieniu do algorytmu efektywne u(cid:346)ytkowanie zasobów oblicze- niowych? O jednej z miar efektywno(cid:314)ci wspomnieli(cid:314)my, omawiaj(cid:159)c algorytmy aprok- symacyjne — by(cid:167) ni(cid:159) czas. Algorytm, który daje poprawne rozwi(cid:159)zanie, lecz zu(cid:343)ywa du(cid:343)o czasu na jego wytworzenie, mo(cid:343)e mie(cid:243) znikom(cid:159) warto(cid:314)(cid:243) lub by(cid:243) bezwarto- (cid:314)ciowy. Gdyby Twój GPS przez godzin(cid:163) wyznacza(cid:167) zalecan(cid:159) tras(cid:163), chcia(cid:167)oby Ci si(cid:163) go w ogóle w(cid:167)(cid:159)cza(cid:243)? Rzeczywi(cid:314)cie, czas jest podstawow(cid:159) miar(cid:159) efektywno(cid:314)ci, której u(cid:343)ywamy do oceny algorytmu, kiedy ju(cid:343) wyka(cid:343)emy, (cid:343)e daje poprawne rozwi(cid:159)zanie. Lecz nie jest to miara jedyna. Mo(cid:343)e nas interesowa(cid:243) ilo(cid:314)(cid:243) pami(cid:163)ci komputerowej wymaganej przez algorytm („(cid:314)lad” jaki odciska w pami(cid:163)ci), poniewa(cid:343) algorytm musi dzia(cid:167)a(cid:243) w dost(cid:163)pnej pami(cid:163)ci. Inne zasoby, które mog(cid:159) by(cid:243) u(cid:343)ywane przez al- gorytm, to: komunikacja sieciowa, losowe bity (poniewa(cid:343) algorytmy, które dokonuj(cid:159) Kup książkęPoleć książkę 18 Algorytmy bez tajemnic losowych wyborów, potrzebuj(cid:159) (cid:341)ród(cid:167)a liczb losowych) lub operacje dyskowe (dla algorytmów przeznaczonych do pracy z danymi przechowywanymi na dysku). W tej ksi(cid:159)(cid:343)ce, tak jak w wi(cid:163)kszo(cid:314)ci literatury o algorytmach, koncentrujemy si(cid:163) tylko na jednym zasobie — jest nim czas. Jak rozs(cid:159)dzamy o czasie wymaganym przez algorytm? W odró(cid:343)nieniu od poprawno(cid:314)ci, niezale(cid:343)(cid:159)cej od konkretnego kom- putera, na którym dzia(cid:167)a algorytm, faktyczny czas algorytmów zale(cid:343)y od kilku czynników zewn(cid:163)trznych wzgl(cid:163)dem samego algorytmu: szybko(cid:314)ci komputera, j(cid:163)zyka programowania, w którym algorytm jest zrealizowany, kompilatora lub interpretera t(cid:167)umacz(cid:159)cego program na kod wykonywany w komputerze, umiej(cid:163)tno(cid:314)ci osoby pi- sz(cid:159)cej dany program i innych dzia(cid:167)a(cid:295) i zdarze(cid:295) zachodz(cid:159)cych w komputerze rów- nolegle z wykonywanym programem. Przy tym wszystkim zak(cid:167)ada si(cid:163), (cid:343)e algorytm jest wykonywany tylko przez jeden komputer, mieszcz(cid:159)cy w pami(cid:163)ci wszystkie jego dane. Gdyby(cid:314)my mieli ocenia(cid:243) szybko(cid:314)(cid:243) algorytmu zrealizowanego w prawdziwym j(cid:163)- zyku programowania, wykonuj(cid:159)c go na konkretnym komputerze dla okre(cid:314)lonych danych i mierz(cid:159)c jego czas dzia(cid:167)ania, nie dowiedzieliby(cid:314)my si(cid:163) niczego o tym, jak szybko dzia(cid:167)a(cid:167)by ten algorytm z danymi innego rozmiaru, a mo(cid:343)e nawet z innymi danymi o tym samym rozmiarze. A gdyby(cid:314)my chcieli porówna(cid:243) wzgl(cid:163)dn(cid:159) szybko(cid:314)(cid:243) danego algorytmu z innym, dla tego samego problemu, musieliby(cid:314)my zaimplemen- towa(cid:243) oba i wykona(cid:243) ka(cid:343)dy z nich z ró(cid:343)nymi danymi, o ró(cid:343)nych rozmiarach. Jak zatem mo(cid:343)emy oceni(cid:243) szybko(cid:314)(cid:243) algorytmu? Otó(cid:343) robimy to, (cid:167)(cid:159)cz(cid:159)c dwa pomys(cid:167)y. Po pierwsze, okre(cid:314)lamy, jak d(cid:167)ugo dzia(cid:167)a algorytm w funkcji rozmiaru jego danych. W przyk(cid:167)adzie ze znajdowaniem trasy dane wej(cid:314)ciowe by(cid:167)yby pewn(cid:159) reprezentacj(cid:159) mapy drogowej, a ich rozmiar zale(cid:343)a(cid:167)by od liczby skrzy(cid:343)owa(cid:295) i liczby dróg (cid:167)(cid:159)cz(cid:159)cych skrzy(cid:343)owania na mapie. (Fizyczny rozmiar sieci dróg nie ma znaczenia, poniewa(cid:343) wszystkie odleg(cid:167)o(cid:314)ci mo(cid:343)emy przed- stawi(cid:243) za pomoc(cid:159) liczb, a wszystkie liczby zajmuj(cid:159) tyle samo miejsca na wej(cid:314)ciu; d(cid:167)u- go(cid:314)(cid:243) drogi nie wp(cid:167)ywa na rozmiar danych wej(cid:314)ciowych). W prostszym przyk(cid:167)adzie — przeszukiwaniu zadanej listy elementów w celu sprawdzenia, czy okre(cid:314)lony ele- ment jest na niej obecny — rozmiarem danych by(cid:167)aby liczba pozycji na li(cid:314)cie. Po drugie, skupiamy si(cid:163) na tym, jak szybko funkcja charakteryzuj(cid:159)ca czas dzia- (cid:167)ania ro(cid:314)nie z rozmiarem danych wej(cid:314)ciowych, tzn. na tempie wzrostu czasu dzia(cid:167)ania. W rozdziale 2 zapoznamy si(cid:163) z notacj(cid:159), której u(cid:343)ywamy do scharakteryzowania czasu dzia(cid:167)ania algorytmu, lecz to, co jest w naszym podej(cid:314)ciu najbardziej interesuj(cid:159)ce, to uwzgl(cid:163)dnianie w czasie dzia(cid:167)ania tylko dominuj(cid:159)cego sk(cid:167)adnika; nie zwracamy przy tym uwagi na wspó(cid:167)czynniki. Koncentrujemy si(cid:163) zatem na rz(cid:164)dzie wzrostu czasu dzia(cid:167)ania. Za(cid:167)ó(cid:343)my na przyk(cid:167)ad, (cid:343)e uda(cid:167)o si(cid:163) nam ustali(cid:243), i(cid:343) dana realizacja pewnego algorytmu przeszukiwania listy n elementów zajmuje 50n + 125 cykli maszyno- wych. Sk(cid:167)adnik 50n zdominuje sk(cid:167)adnik 125, je(cid:314)li n stanie si(cid:163) dostatecznie du(cid:343)e, po- czynaj(cid:159)c od n (cid:116) 3 i zwi(cid:163)kszaj(cid:159)c jeszcze t(cid:163) przewag(cid:163) dla list o wi(cid:163)kszych rozmiarach. Wobec tego, opisuj(cid:159)c czas dzia(cid:167)ania tego hipotetycznego algorytmu, nie bierzemy pod uwag(cid:163) sk(cid:167)adnika 125 ma(cid:167)ego rz(cid:163)du. Mo(cid:343)e si(cid:163) zdziwisz, ale odrzucamy te(cid:343) wspó(cid:167)czynnik 50. Prowadzi to do okre(cid:314)lenia czasu dzia(cid:167)ania jako rosn(cid:159)cego liniowo Kup książkęPoleć książkę Rozdzia(cid:167) 1. • Co to s(cid:159) algorytmy i dlaczego warto po(cid:315)wi(cid:163)ca(cid:244) im uwag(cid:163)?(cid:31) 19 z rozmiarem danych n. Oto inny przyk(cid:167)ad: gdyby algorytm zu(cid:343)ywa(cid:167) 20n3 + 100n2 + 300n + 200 cykli maszynowych, to powiedzieliby(cid:314)my, (cid:343)e jego czas dzia(cid:167)ania ro(cid:314)nie jak n3. Równie(cid:343) w tym przypadku sk(cid:167)adniki ni(cid:343)szego rz(cid:163)du: 100n2, 300n i 200, staj(cid:159) si(cid:163) coraz mniej istotne ze wzrostem rozmiaru n danych wej(cid:314)ciowych. W praktyce lekcewa(cid:343)one przez nas wspó(cid:167)czynniki maj(cid:159) jednak znaczenie. Zale- (cid:343)(cid:159) one jednak w tak du(cid:343)ym stopniu od czynników zewn(cid:163)trznych, (cid:343)e jest prawie pewne, i(cid:343) przy porównywaniu dwóch algorytmów A i B, maj(cid:159)cych ten sam rz(cid:159)d wzrostu i dzia(cid:167)aj(cid:159)cych na tych samych danych, A mo(cid:343)e dzia(cid:167)a(cid:243) szybciej ni(cid:343) B dla pewnej kombinacji maszyny, j(cid:163)zyka programowania, kompilatora (lub interpretera) i programisty, a B zadzia(cid:167)a szybciej ni(cid:343) A dla innej kombinacji. Oczywi(cid:314)cie, je(cid:343)eli oba algorytmy A i B produkuj(cid:159) poprawne rozwi(cid:159)zania i A zawsze dzia(cid:167)a dwa razy szybciej ni(cid:343) B, to je(cid:314)li wszystko inne jest takie samo, b(cid:163)dziemy zawsze preferowali wykonywanie A zamiast B. Jednak(cid:343)e z punktu widzenia abstrakcyjnego porówny- wania algorytmów zawsze koncentrujemy si(cid:163) na rz(cid:163)dzie wzrostu, nie przystrajaj(cid:159)c go wspó(cid:167)czynnikami lub sk(cid:167)adnikami niskiego rz(cid:163)du. I ostatnie pytanie, które stawiamy w tym rozdziale: „Dlaczego mia(cid:167)oby mi si(cid:163) op(cid:167)a- ca(cid:243) zajmowanie algorytmami komputerowymi?”. Odpowied(cid:341) na nie zale(cid:343)y od tego, kim jeste(cid:314). Algorytmy komputerowe dla niekomputerowców Nawet je(cid:314)li w sferze komputerów nie uwa(cid:343)asz si(cid:163) za osob(cid:163) dobrze poinformowan(cid:159), algorytmy komputerowe stanowi(cid:159) dla Ciebie du(cid:343)(cid:159) warto(cid:314)(cid:243). W ko(cid:295)cu, wyj(cid:159)wszy sytuacj(cid:163), w której podró(cid:343)ujesz po bezdro(cid:343)ach bez GPS-u, zapewne u(cid:343)ywasz go co dnia. Szuka(cid:167)e(cid:314) czego(cid:314) dzisiaj w Internecie? W u(cid:343)ywanej przez Ciebie wyszukiwarce — Google, Bing lub jakiejkolwiek innej — s(cid:159) stosowane wyrafinowane algorytmy przeszukiwania Sieci i rozstrzygania, w jakiej kolejno(cid:314)ci nale(cid:343)y przedstawia(cid:243) ich wyniki. Prowadzi(cid:167)e(cid:314) dzi(cid:314) samochód? O ile nie je(cid:341)dzisz klasycznym wehiku(cid:167)em, jego komputery pok(cid:167)adowe podj(cid:163)(cid:167)y podczas Twej podró(cid:343)y miliony decyzji, a wszystkie oparte by(cid:167)y na algorytmach. Móg(cid:167)bym tak wymienia(cid:243) bez ko(cid:295)ca. Jako docelowy u(cid:343)ytkownik algorytmów sobie zawdzi(cid:163)czasz ch(cid:163)(cid:243) dowiedzenia si(cid:163) czego(cid:314) o tym, jak projektujemy, charakteryzujemy i oceniamy algorytmy. Zak(cid:167)a- dam, (cid:343)e przejawiasz przynajmniej umiarkowane zainteresowanie, skoro ta ksi(cid:159)(cid:343)ka trafi(cid:167)a do Twoich r(cid:159)k i czytasz j(cid:159) do tego miejsca. Powodzenia! Zobaczmy, czy uda si(cid:163) nam rozkr(cid:163)ci(cid:243) Ci(cid:163) na tyle, (cid:343)e na nast(cid:163)pnym spotkaniu towarzyskim dotrzymasz tonu innym, gdy rozmowa zejdzie na algorytmy2. 2 No tak, przyznaj(cid:163), je(cid:314)li nie mieszkasz w Dolinie Krzemowej, temat algorytmów rzadko wyp(cid:167)ynie podczas koktajli, w których bierzesz udzia(cid:167), niemniej z pewnych wzgl(cid:163)dów my, profesorowie informatyki, uwa(cid:343)amy, (cid:343)e jest wa(cid:343)ne, aby nasi studenci nie konsternowali nas na spotkaniach towarzyskich brakiem wiedzy z poszczególnych dziedzin informatyki. Kup książkęPoleć książkę 20 Algorytmy bez tajemnic Algorytmy komputerowe dla komputerowców Je(cid:314)li jeste(cid:314) za pan brat z komputerami, to masz wi(cid:163)ksze obowi(cid:159)zki wobec algoryt- mów! One nie tylko znajduj(cid:159) si(cid:163) w centrum wszystkiego, co si(cid:163) dzieje w Twoim kom- puterze — algorytmy s(cid:159) technologi(cid:159), i to równie istotn(cid:159) jak wszystko, co wspó(cid:167)- tworzy Twój komputer. Mo(cid:343)esz zap(cid:167)aci(cid:243) dodatkow(cid:159) cen(cid:163) za komputer z najnowszym i najwi(cid:163)kszym procesorem, lecz aby te pieni(cid:159)dze okaza(cid:167)y si(cid:163) trafionym wydatkiem, potrzebujesz, by w tym komputerze dzia(cid:167)a(cid:167)y realizacje dobrych algorytmów. Oto przyk(cid:167)ad ilustruj(cid:159)cy, (cid:343)e algorytmy rzeczywi(cid:314)cie stanowi(cid:159) technologi(cid:163). W trze- cim rozdziale przyjrzymy si(cid:163) trzem ró(cid:343)nym algorytmom sortowania w porz(cid:159)dku ro- sn(cid:159)cym listy n warto(cid:314)ci. Niektóre z tych algorytmów b(cid:163)d(cid:159) osi(cid:159)ga(cid:167)y czasy dzia(cid:167)ania rosn(cid:159)ce jak n2, lecz inne b(cid:163)d(cid:159) dzia(cid:167)a(cid:243) w czasie rosn(cid:159)cym tylko jak n lg n. Co to jest lg n? Jest to logarytm przy podstawie 2 z n, czyli log2 n. Informatycy u(cid:343)ywaj(cid:159) lo- garytmów z podstaw(cid:159) 2 tak cz(cid:163)sto, (cid:343)e podobnie jak matematycy i naukowcy, któ- rzy dla skrócenia stosuj(cid:159) zapis ln n na oznaczenie logarytmu naturalnego — loge n, równie(cid:343) oni u(cid:343)ywaj(cid:159) w(cid:167)asnego skrótu dla logarytmów przy podstawie 2. I tak, poniewa(cid:343) funkcja lg n jest odwrotno(cid:314)ci(cid:159) funkcji wyk(cid:167)adniczej, ro(cid:314)nie ona bardzo powoli z n. Je(cid:314)li n = 2x, to x = lg n. Na przyk(cid:167)ad 210 = 1024, wi(cid:163)c lg 1024 wynosi tylko 10, podobnie 220 = 1 048 576, zatem lg 1 048 576 wynosi zaledwie 20, a 230 = 1 073 741 824, co oznacza, (cid:343)e lg 1 073 741 824 wynosi raptem 30. Tak wi(cid:163)c we wzro(cid:314)cie n lg n w porównaniu ze wzrostem n2 zachodzi wymiana czynnika n na je- dynie ln n, a to ju(cid:343) jest gra warta (cid:314)wieczki. Skonkretyzujmy nieco bardziej ten przyk(cid:167)ad, wystawiaj(cid:159)c szybszy komputer (komputer A) wykonuj(cid:159)cy algorytm sortowania, którego czas dzia(cid:167)ania dla n war- to(cid:314)ci ro(cid:314)nie jak n2, przeciw wolniejszemu komputerowi B, wykonuj(cid:159)cemu algo- rytm sortowania w czasie rosn(cid:159)cym jak n lg n. Ka(cid:343)dy z komputerów musi posor- towa(cid:243) 10 milionów liczb. (Cho(cid:243) mo(cid:343)e si(cid:163) wydawa(cid:243), (cid:343)e 10 milionów liczb to du(cid:343)o, je(cid:314)li s(cid:159) to 8-bajtowe liczby ca(cid:167)kowite, ich rozmiar na wej(cid:314)ciu zajmie oko(cid:167)o 80 me- gabajtów, co zmie(cid:314)ci si(cid:163) w pami(cid:163)ci nawet niedrogiego laptopa sprzed wielu lat). Przypu(cid:314)(cid:243)my, (cid:343)e komputer A wykonuje 10 miliardów operacji na sekund(cid:163) (jest szyb- szy od ka(cid:343)dego sekwencyjnego komputera w chwili, gdy pisz(cid:163) te s(cid:167)owa), a komputer B wykonuje tylko 10 milionów operacji na sekund(cid:163), czyli komputer A jest 1000 razy szybszy od komputera B, bior(cid:159)c pod uwag(cid:163) sam(cid:159) moc obliczeniow(cid:159). Aby powi(cid:163)k- szy(cid:243) jeszcze ró(cid:343)nic(cid:163), za(cid:167)ó(cid:343)my, (cid:343)e (cid:314)wiatowej s(cid:167)awy programistka koduje komputer A w j(cid:163)zyku maszynowym, a kod wynikowy wymaga do posortowania n liczb 2n2 rozkazów. Za(cid:167)ó(cid:343)my dalej, (cid:343)e program dla komputera B pisze programista zupe(cid:167)nie przeci(cid:163)tny, korzystaj(cid:159)c z j(cid:163)zyka wysokiego poziomu i ma(cid:167)o efektywnego kompila- tora, w wyniku czego powstaje kod z(cid:167)o(cid:343)ony z 50n lg n rozkazów. Aby posortowa(cid:243) 10 milionów liczb, komputer A zu(cid:343)ywa 7 2 rozkazów )10(2 (cid:152) rozkazów 10 10 / sekund(cid:266) sekund, 000 20 (cid:32) co stanowi wi(cid:163)cej ni(cid:343) 5 i pó(cid:167) godziny, podczas gdy komputerowi B zabiera to Kup książkęPoleć książkę Rozdzia(cid:167) 1. • Co to s(cid:159) algorytmy i dlaczego warto po(cid:315)wi(cid:163)ca(cid:244) im uwag(cid:163)?(cid:31) 21 7 50 10 7 lg 10 10 (cid:152) rozkazów 7 rozkazów sekund(cid:266) / sekundy 163 1 (cid:124) — równowarto(cid:314)(cid:243) mniej ni(cid:343) 20 minut. Stosuj(cid:159)c algorytm, którego czas dzia(cid:167)ania ro(cid:314)nie znacznie wolniej, nawet z marnym kompilatorem, komputer B dzia(cid:167)a 17 razy szybciej ni(cid:343) komputer A! Przewaga algorytmu n lg n by(cid:167)aby jeszcze wyra(cid:341)- niejsza, gdyby(cid:314)my sortowali 100 milionów liczb. Komputerowi A zabra(cid:167)oby to ponad 23 dni, algorytm n lg n na komputerze B upora(cid:167)by si(cid:163) z robot(cid:159) w cztery godziny. Uogólniaj(cid:159)c, wraz ze wzrostem rozmiaru problemu ro(cid:314)nie wzgl(cid:163)dna przewaga algorytmu n lg n. Nawet mimo imponuj(cid:159)cego post(cid:163)pu, który nieustannie obserwujemy w sprz(cid:163)cie komputerowym, ca(cid:167)o(cid:314)ciowa produktywno(cid:314)(cid:243) systemu zale(cid:343)y w równym stopniu od doboru efektywnych algorytmów, co od doboru szybkiego sprz(cid:163)tu lub sprawnie dzia- (cid:167)aj(cid:159)cych systemów operacyjnych. B(cid:167)yskawiczny post(cid:163)p, jaki dokona(cid:167) si(cid:163) w innych technologiach komputerowych, dotyczy tak(cid:343)e algorytmów. Co czyta(cid:247) dalej W moim bardzo subiektywnym odczuciu najklarowniejszym i najbardziej u(cid:343)ytecz- nym (cid:341)ród(cid:167)em wiedzy o algorytmach komputerowych jest Wprowadzenie do algoryt- mów [CLRS09], napisane przez czterech diabelnie przystojnych facetów. Ksi(cid:159)(cid:343)ka ta jest powszechnie okre(cid:314)lana jako „CLRS”, od inicja(cid:167)ów autorów. Si(cid:163)ga(cid:167)em do niej po wi(cid:163)kszo(cid:314)(cid:243) materia(cid:167)u pomieszczonego w tej ksi(cid:159)(cid:343)ce. Jest ona nieporównanie bar- dziej kompletna od tej ksi(cid:159)(cid:343)ki, lecz zak(cid:167)ada si(cid:163) w niej, (cid:343)e masz cho(cid:243) troch(cid:163) do(cid:314)wiad- czenia w programowaniu komputerów i jeste(cid:314) za pan brat z matematyk(cid:159). Je(cid:314)li uznasz, (cid:343)e odpowiada Ci poziom matematyczny niniejszej ksi(cid:159)(cid:343)ki, i masz odwag(cid:163) ruszy(cid:243) g(cid:167)(cid:163)biej w temat, nie mo(cid:343)esz post(cid:159)pi(cid:243) lepiej, ni(cid:343) si(cid:163)gn(cid:159)(cid:243) po CLRS. (W mojej skromnej opinii, ma si(cid:163) rozumie(cid:243)). Ksi(cid:159)(cid:343)ka Johna MacCormica Nine Algorithms That Changed the Future [Mac12] zawiera opis kilku algorytmów i zwi(cid:159)zanych z nimi kwestii obliczeniowych, które oddzia(cid:167)uj(cid:159) na nasze codzienne (cid:343)ycie. Uj(cid:163)cie zastosowane przez MacCormica jest mniej techniczne ni(cid:343) w tej ksi(cid:159)(cid:343)ce. Je(cid:314)li dojdziesz do wniosku, (cid:343)e tutaj by(cid:167)o „zbyt matematycznie”, to polecam Ci skosztowanie lektury MacCormica. Zdo(cid:167)asz przy- swoi(cid:243) z niej wiele, nawet je(cid:314)li masz w(cid:159)t(cid:167)e przygotowanie matematyczne. W ma(cid:167)o prawdopodobnym przypadku, gdy uznasz, (cid:343)e CLRS jest zbyt rozwod- nione, mo(cid:343)esz spróbowa(cid:243) zaczerpn(cid:159)(cid:243) z wielotomowego zbioru Donalda Knutha The Art of Computer Programming [Knu97, Knu98a, Knu98b, Knu11]. Chocia(cid:343) tytu(cid:167) serii sugeruje, (cid:343)e skupia si(cid:163) ona na pisaniu kodu, ksi(cid:159)(cid:343)ki te zawieraj(cid:159) wspania(cid:167)(cid:159), g(cid:167)(cid:163)bok(cid:159) analiz(cid:163) algorytmów3. Ostrzegam jednak: materia(cid:167) zawarty w TAOCP si(cid:163)ga g(cid:167)(cid:163)boko. Przy okazji, je(cid:314)li zastanawiasz si(cid:163), sk(cid:159)d si(cid:163) wzi(cid:163)(cid:167)o s(cid:167)owo „algorytm”, to Knuth powia- da, (cid:343)e pochodzi ono od imienia „al-Khowârizmî” perskiego matematyka z IX wieku. 3 Sztuka programowania, WNT, Warszawa 2002 – 2007. Jak dot(cid:159)d ukaza(cid:167)y si(cid:163) 4 ksi(cid:159)(cid:343)ki z jeszcze nie uko(cid:295)czonego cyklu, który Donald Knuth zaplanowa(cid:167) na 7 tomów — przyp. t(cid:167)um. Kup książkęPoleć książkę 22 Algorytmy bez tajemnic Oprócz CLRS przez lata ukaza(cid:167)o si(cid:163) kilka innych (cid:314)wietnych tekstów o algoryt- mach komputerowych. Noty do rozdzia(cid:167)u 1 w CLRS zawieraj(cid:159) odwo(cid:167)ania do wielu takich tekstów. Zamiast powiela(cid:243) je tutaj, kieruj(cid:163) Ci(cid:163) wprost do CLRS. Kup książkęPoleć książkę Skorowidz A abstract data type, Patrz: ADT abstrahowanie, 107 adjacency matrix, Patrz: macierz s(cid:159)siedztwa adjacency-list represention, Patrz: lista s(cid:159)siedztwa reprezentacja Adleman Leonard, 153 ADT, 107 Advanced Encryption Standard, Patrz: AES AES, 150, 160 algorytm, 15, 21 aproksymacyjny, 17, 208 Bellmana-Forda, 102, 111, 183, 186 czas dzia(cid:167)ania, Patrz: czas dzia(cid:167)ania algorytmu Bellmana-Forda czas dzia(cid:167)ania, Patrz: czas dzia(cid:167)ania Dijkstry, 102, 104, 105, 107, 110, 169, 210 czas dzia(cid:167)ania, 106 Euklidesa, 157 Floyda-Warshalla, 102, 115, 116, 117, 118, 122, 210 czas dzia(cid:167)ania, 116, 121 KMP, 143 Knutha-Morrisa-Pratta, 143 komputerowy, 19, 20 opisywanie, 23 o czasie wielomianowym, Patrz: algorytm wielomianowy przybli(cid:343)aj(cid:159)cy, Patrz: algorytm aproksymacyjny redukcji w czasie wielomianowym, 187, 189 rekurencyjny, 35 sortowania, Patrz: sortowanie szybko(cid:314)(cid:243), 18 wielomianowy, 183, 184, 186, 187, 193, 194, 196, 202, 210 zach(cid:167)anny, 169 znajdowania najkrótszej (cid:314)cie(cid:343)ki, 94 all-pairs shortest-paths, Patrz: problem najkrótszych (cid:314)cie(cid:343)ek mi(cid:163)dzy wszystkimi parami wierzcho(cid:167)ków alternatywa wykluczaj(cid:159)ca, Patrz: XOR approximation algorithm, Patrz: algorytm aproksymacyjny arbitrage opportunity, Patrz: mo(cid:343)liwo(cid:314)(cid:243) arbitra(cid:343)u arbitra(cid:343), Patrz: mo(cid:343)liwo(cid:314)(cid:243) arbitra(cid:343)u array, Patrz: tablica arytmetyka modularna, 153, 156 modulo, Patrz: arytmetyka modularna assigns, Patrz: procedura przypiswyanie authentication, Patrz: uwierzytelnienie automat sko(cid:295)czony, 138, 139, 141 B Bacon Kevin, 101 base cases, Patrz: przypadek bazowy Bellman Richard, 111 Bellmana-Forda algorytm, Patrz: algorytm Bellmana-Forda binary heap, Patrz: kopiec binarny binary tree, Patrz: drzewo binarne biologia obliczeniowa, 125, 131 block cipher, Patrz: szyfr blokowy bloczek jednorazowy, Patrz: podk(cid:167)adka jednorazowa Boole George, 190 boolean formula, Patrz: formu(cid:167)a boolowska boolean formula satisfiability problem, Patrz: problem spe(cid:167)nialno(cid:314)ci formu(cid:167)y boolowskiej branch and bound method, Patrz: metoda podzia(cid:167)u i ogranicze(cid:295) C certificate, Patrz: certyfikat certyfikat, 185, 186, 195, 197 CGF, 210 child, Patrz: dziecko ci(cid:159)g, 125 cipher block chaining, Patrz: (cid:167)a(cid:295)cuchowanie bloków szyfru Kup książkęPoleć książkę 216 Algorytmy bez tajemnic ciphertext, Patrz: tekst zaszyfrowany clause, Patrz: klauzula common subsequence, Patrz: podci(cid:159)g comparison sort, Patrz: sortowanie wspólny porównanie complete graph, Patrz: graf pe(cid:167)ny composite number, Patrz: liczba z(cid:167)o(cid:343)ona concatenation, Patrz: z(cid:167)(cid:159)czenie connected graph, Patrz: graf spójny contex-free grammar problem, Patrz: CGF counting sort, Patrz: sortowanie zliczanie critical path, Patrz: (cid:314)cie(cid:343)ka krytyczna cykl, 87, 94, 101 Eulera, 183, 184, 186 Hamiltona, 183, 184, 185, 186, 196, 197, 198, 204, 205, 206 z wag(cid:159) ujemn(cid:159), 113 czas, 17, 18 dzia(cid:167)ania, 20 algorytmu Bellmana-Forda, 113, 183 algorytmu Dijkstry:, 106 algorytmu Floyda-Warshalla, 116, 121 algorytmu redukcji, 187 dopasowywania napisów, 143 notacja, 23 ograniczenie, Patrz: ograniczenie ograniczony przez funkcj(cid:163) liniow(cid:159), 30 operacji, 29 rosn(cid:159)cy liniowo, 18 rz(cid:159)d wzrostu, 18, 19 tempo wzrostu, 18 wielomianowy, Patrz: algorytm wielomianowy wyszukiwanie binarne, Patrz: wyszukiwanie binarne czas dzia(cid:167)ania liniowy, 210 podliniowy, 210 sortowania, 38 pozycyjne, 71 scalanie, 50, 58, 59, 67, 71 szybkie, 59, 65, 67, 71 topologiczne, 92 wstawianie, 49, 50, 67, 71 wybieranie, 45, 46, 50, 67, 71 zliczanie, 71, 78 weryfikacji certyfikatu, 185 wielomianowy, Patrz: algorytm wielomianowy D dag, 87, 92, 96, 101 sortowanie topologiczne, Patrz: sortowanie topologiczne dane dekompresja, Patrz: dekompresja kompresja, Patrz: kompresja nadmiarowe, 164 satelickie, Patrz: dane towarzysz(cid:159)ce struktura, 107, 179 tablica, Patrz: tablica towarzysz(cid:159)ce, 38, 39, 71, 73, 78 typ abstrakcyjny, Patrz: ADT wej(cid:314)ciowe, 24 kopia, 51 rozmiar, 18, 29 wyj(cid:314)ciowe, Patrz: wynik data structure, Patrz: dane struktura decidable problem, Patrz: problem podatny decision problems, Patrz: problem decyzyjny decryption, Patrz: deszyfrowanie dekompresja, 163, 165, 169, 170 LZW, 176, 177 dense graph, Patrz: graf g(cid:163)sty deszyfrowanie, 145 d(cid:167)ugiego komunikatu, 160 diagram, 83, 87 PERT, 92, 93, 100 z zanegowanymi czasami, 95 digraf, Patrz: graf skierowany Dijkstra Edsger, 102 directed acyclic graph, Patrz: dag directed edge, Patrz: kraw(cid:163)d(cid:341) skierowana directed graph, Patrz: graf skierowany divide-and-conquer, Patrz: metoda dziel i zwyci(cid:163)(cid:343)aj DNA, 125, 164 doubly linked list, Patrz: lista powi(cid:159)zana dwukierunkowa droga Eulera, Patrz: cykl Eulera drzewo binarne, 108, 109, 166 aktualizacja, 170 dynamic programming, Patrz: programowanie dynamiczne dziecko, 109 Kup książkęPoleć książkę osiowy, 59, 62, 63 rozdzielaj(cid:159)cy, Patrz: element osiowy uporz(cid:159)dkowanie, Patrz: uporz(cid:159)dkowanie encryption, Patrz: szyfrowanie entry, Patrz: wpis Erdös Paul, 101 escape code, Patrz: kod sygna(cid:167)owy Euler Leonhard, 183 Euler tour, Patrz: cykl Eulera Eulera cykl, Patrz: cykl Eulera exclusive-or, Patrz: XOR E F efektywno(cid:314)(cid:243), Patrz: rozwi(cid:159)zanie efektywne miara, 17 element faks, 164, 170 Fermata twierdzenie, Patrz: twierdzenie finite automaton, Patrz: automat Fermata ma(cid:167)e sko(cid:295)czony F-kopiec, Patrz: kopiec Fibonacciego Floyd Robert, 116 Ford Lester, 111 formal language, Patrz: j(cid:163)zyk formalny format JPEG, Patrz: MP3 MP3, Patrz: MP3 formu(cid:167)a boolowska, 190, 199, 205 posta(cid:243) 3-koniunkcyjn(cid:159) normalna, 191 koniunkcja klauzul, 191 logiczna, Patrz: formu(cid:167)a boolowska spe(cid:167)nialna, 190 spe(cid:167)nialno(cid:314)ci, 189 funkcja, Patrz: procedura Skorowidz 217 nieskierowany, 183, 192, 195, 199 pe(cid:167)ny, 198 rzadki, 110, 116 skierowany, 87 acykliczny, Patrz: dag reprezentacja, 90 wa(cid:343)ony, 94, 95, 101 spójny, 183 nieskierowany, 183, 184 grafika komputerowa, 38 grafu, 108 gramatyka bezkontekstowa, 210 greedy algorithm, Patrz: algorytm zach(cid:167)anny H halting problem, Patrz: problem stopu Hamilton William, 184 hamiltonian cycle, Patrz: cykl Hamiltona hamiltonian-path problem, Patrz: problem (cid:314)cie(cid:343)ki Hamiltona hash table, Patrz: tablica z haszowaniem heap property, Patrz: klucz w(cid:167)asno(cid:314)(cid:243) kopca heapsort, Patrz: sortowanie na kopcu Huffman David, 165 Huffmana kod, Patrz: kod Huffmana I in place, Patrz: sortowanie na miejscu incident edge, Patrz: kraw(cid:163)d(cid:341) incydentna in-degree, Patrz: stopnie(cid:295) wej(cid:314)ciowy initialization vector, Patrz: wektor insertion sort, Patrz: sortowanie pocz(cid:159)tkowy wstawianie internal node, Patrz: w(cid:163)ze(cid:167) wewn(cid:163)trzny iteracja, 26, 43, 49 G J gad(cid:343)et, 197, 206 generator liczb pseudolosowych, Patrz: PRNG graf, 186 acykliczny, 207 cykliczny, 101 g(cid:163)sty, 110, 116 j(cid:163)zyk formalny, 210 programowania, 156 Python, Patrz: Python Juliusz Cezar, 146 Kup książkęPoleć książkę knapsack problem, Patrz: problem 218 Algorytmy bez tajemnic K karta kredytowa, 145, 147 key, Patrz: klucz klauzula, 191, 194, 199, 201 klika, 192, 194 problem, 192 rozmiar, 192 klucz, 37, 71, 74 jawny, Patrz: klucz publiczny kryptograficzny, 146 podk(cid:167)adka, 149 potomka, 109 prywatny, Patrz: klucz tajny publiczny, 151, 160 symetryczny, 147, 150, 160 tajny, 151, 152 w(cid:163)z(cid:167)a, 109 w(cid:167)asno(cid:314)(cid:243) kopca, 109 plecakowy Knuth Donald, 21 kod bezprzedrostkowy, 165, 166 Huffmana, 165, 171, 179 adaptacyjny, 170 seria-d(cid:167)ugo(cid:314)(cid:243), 170 sygna(cid:167)owy, 170 kolejka priorytetowa, 107 kompresja, 163, 170 bezstratna, 163, 164, 171 LZW, 171, 173, 176, 179 stratna, 163, 164 koniunkcja, 191 konkatenacja, Patrz: z(cid:167)(cid:159)czenie kopiec binarny, 109 Fibonacciego, 111 kraw(cid:163)d(cid:341), 91, 183 incydentna, 183, 184 o ujemnych wagach, 102 os(cid:167)abianie, Patrz: os(cid:167)abianie skierowana, 87 waga, 94 krok os(cid:167)abiaj(cid:159)cy, 97 kryptografia, 145 z kluczem jawnym, 151, 153 z kluczem symetrycznym, 147, 150 kryptosystem hybrydowy, 151, 160 RSA, 145, Patrz: RSA z kluczem jawnym, 153, 159 kube(cid:167)kowanie, Patrz: szufladkowanie L last in first out, Patrz: porz(cid:159)dek LIFO LCS, 125, 126, 127, 129 leaf, Patrz: li(cid:314)(cid:243) lexicographic ordering, Patrz: uporz(cid:159)dkowanie leksykograficzne liczba Bacona, 101 Erdösa, 102 Erdösa-Bacona, 102 losowa, 161 pierwsza, 16, 153, 154 du(cid:343)a, 156 twierdzenie, 156 wzgl(cid:163)dnie pierwsza, 155, 157 z(cid:167)o(cid:343)ona, 154 linear search, Patrz: wyszukiwanie liniowe linked list, Patrz: lista powi(cid:159)zana lista, 23 longest common subsequence, Patrz: LCS longest-acyclic-path problem, Patrz: problem najd(cid:167)u(cid:343)szej (cid:314)cie(cid:343)ki prostej loop, Patrz: p(cid:163)tla loop body, Patrz: p(cid:163)tla tre(cid:314)(cid:243) loop invariant, Patrz: p(cid:163)tla niezmiennik loop variable, Patrz: zmienna p(cid:163)tli lossless compression, Patrz: kompresja bezstratna lossy compression, Patrz: kompresja stratna z dowi(cid:159)zaniami, Patrz: lista powi(cid:159)zana powi(cid:159)zana, 91, 92 dwukierunkowa, 92 jednokierunkowa, 92 s(cid:159)siedztwa, 91 reprezentacja, 91, 92 li(cid:314)(cid:243), 109, 166 g(cid:167)(cid:163)boko(cid:314)(cid:243), 167 literal, Patrz: litera(cid:167) litera(cid:167), 191, 194, 199 logarytm, 20 naturalny, 20 przy podstawie 2, 20 Kup książkęPoleć książkę (cid:167) (cid:167)a(cid:295)cuch, Patrz: napis (cid:167)a(cid:295)cuchowanie bloków szyfru, 150 (cid:167)uk, Patrz: kraw(cid:163)d(cid:341) skierowana M MacCormic John, 21 macierz s(cid:159)siedztwa, 90, 91 merge sort, Patrz: sortowanie scalanie metoda, Patrz: procedura 2-opt, 207 dziel i zwyci(cid:163)(cid:343)aj, 51, 59 podzia(cid:167)u i ogranicze(cid:295), 207 przeszukiwanie s(cid:159)siedztwa, 207 rekurencji uniwersalnej, 59 modular arithmetic, Patrz: arytmetyka modularna Mother Problem, Patrz: problem matka mo(cid:343)liwo(cid:314)(cid:243) arbitra(cid:343)u, 115 N nadmiarowo(cid:314)(cid:243), 164 napis, 125, 209 dopasowywanie, 125, 137, 141, 143 czas dzia(cid:167)ania, 143 wzorcowy, 137 z tekstem, 137 zamiana na inny, 125, 130, 131, 132 z(cid:167)(cid:159)czenie, Patrz: z(cid:167)(cid:159)czenie neighborhood search, Patrz: metoda przeszukiwanie s(cid:159)siedztwa nierówno(cid:314)(cid:243) trójk(cid:159)ta, 208 node, Patrz: w(cid:163)ze(cid:167), wierzcho(cid:167)ek notacja (cid:52), 30, 31, 32, 43, 45, 73, 116 asymptotyczna, 32, 46 O, 31, 32, 43 NP-complete problem, Patrz: problem NP- zupe(cid:167)ny NP-hard problem, Patrz: problem NP-trudny O ograniczenie dolne, 32, 45, 46, 73, 78 egzystencjalne, 73 uniwersalne, 73 górne, 30, 31, 32, 45, 46 Skorowidz 219 one-time pad, Patrz: podk(cid:167)adka jednorazowa operacja alternatywy wykluczaj(cid:159)cej, 148, 149 czas dzia(cid:167)ania, 29 koszt, 131, 134 operator „i”, 48 krótko spinaj(cid:159)cy, 48 optymalizacja, 17 os(cid:167)abianie, 97, 98, 104, 107, 111, 169 out-degree, Patrz: stopie(cid:295) wyj(cid:314)ciowy output, Patrz: wynik P pad, Patrz: podk(cid:167)adka paradygmat dziel i zwyci(cid:163)(cid:343)aj, Patrz: metoda dziel i zwyci(cid:163)(cid:343)aj paradygmat paradygmat algorytmiczny, Patrz: algorytm parametr, 24 partition problem, Patrz: problem podzia(cid:167)u partitioning, Patrz: rozdzielanie path, Patrz: (cid:314)cie(cid:343)ka pattern string, Patrz: napis wzorcowy PCP, 209, 210 pel, 164, 171 p(cid:163)tla, 26 niezmiennik, 33, 45, 105, 106 inicjowanie, 33, 42 utrzymanie, 33, 42 zako(cid:295)czenie, 33, 42 tre(cid:314)(cid:243), 26 zmienna, 26 pivot, Patrz: element osiowy plaintext, Patrz: tekst jawny podci(cid:159)g, 125 wspólny, 126 najd(cid:167)u(cid:343)szy, Patrz: LCS podk(cid:167)adka, 149 jednorazowa, 147, 149 podnapis, 126 podnoszenie do kwadratu powtarzane, 159 podstruktura optymalna, 122, 126, 127 pod(cid:314)cie(cid:343)ka, 117 podtablica, 40, 47 pokrycie wierzcho(cid:167)kowe, 195, 196, 206 problem, 195 rozmiar, 195 Kup książkęPoleć książkę 220 Algorytmy bez tajemnic polynomial-time algorithm, Patrz: algorytm wielomianowy polynomial-time reduction algorithm, Patrz: algorytm redukcji w czasie wielomianowym poprawno(cid:314)(cid:243), Patrz: rozwi(cid:159)zanie poprawne poprzednik, 97, 118 porz(cid:159)dek, 84 LIFO, 89 liniowy, 87 ostatni przychodzi, pierwszy wychodzi, Patrz: porz(cid:159)dek LIFO Post’s correspondence problem, Patrz: PCP post(cid:163)p arytmetyczny, 45 potomek, 108 klucz, 109 predecessor, Patrz: poprzednik prefix, Patrz: przedrostek prefix-free code, Patrz: kod bezprzedrostkowy prime number, Patrz: liczba pierwsza priority queue, Patrz: kolejka priorytetowa PRNG, 161 problem cyklu Hamiltona, Patrz: cykl Hamiltona decyzyjny, 186, 187 dopasowywania napisów, 125, 137, 141, 143 gramatyki bezkontekstowej, Patrz: CGF kliki, 192, 195, 206 komiwoja(cid:343)era, 182, 197, 198, 204, 205, 206, 207, 208 matka, 189, 191, 205 najd(cid:167)u(cid:343)szej (cid:314)cie(cid:343)ki acyklicznej, Patrz: problem najd(cid:167)u(cid:343)szej (cid:314)cie(cid:343)ki prostej najd(cid:167)u(cid:343)szej (cid:314)cie(cid:343)ki prostej, 199 najkrótszych (cid:314)cie(cid:343)ek mi(cid:163)dzy wszystkimi parami wierzcho(cid:167)ków, 115 nierozstrzygalny, 208, 209, 210 NP-trudny, 186, 187, 189, 197, 198, 203, 204 NP-zupe(cid:167)ny, 183, 184, 185, 186, 187, 189, 192, 197, 204, 205, 206, 207, 208 odpowiednio(cid:314)ci Posta, Patrz: PCP optymalizacyjny, 186, 204, 207 plecakowy, 204 podatny, 184, 185 podzia(cid:167)u, 203, 204 pokrycia wierzcho(cid:167)kowego, 195, 206 automat sko(cid:295)czony, 141 Bellmana-Forda, 111 cykl z wag(cid:159) ujemn(cid:159), 114 dekompresja LZW, 177 Dijkstra, 104 dopasowywania napisów, 141 drzewo Huffmana, 168, 169 Euklidesa, 157 Floyda-Warshalla, 119 kompresja LZW, 174, 179 LCS, 128 rekurencyjna, 129 parametr, Patrz: parametr przypisywanie, 26 rozdzielanie, 63, 66 sortowanie na kopcu, 110 scalanie, 51, 52, 57 szybkie, 60 topologiczne, 88 wstawianie, 47 wybieranie, 44 spe(cid:167)nialno(cid:314)ci 3-CNF, 192, 193 spe(cid:167)nialno(cid:314)ci formu(cid:167)y boolowskiej, 190, 191 stopu, 208 sumy podzbioru, 199, 203 (cid:314)cie(cid:343)ki Hamiltona, 197 w klasie NP, 185, 186, 187, 198 w klasie P, 184, 185 zatrzymania, Patrz: problem stopu procedura, 24 wyszukiwanie binarne, 41 wywo(cid:167)anie, 24 program deterministyczny, 161 programowanie dynamiczne, 121, 122, 123, 126 przedrostek, 126, 142, 165 przegl(cid:159)darka, 145 przegródka, 39 przep(cid:167)yw sterowania, 23 przeszukiwanie s(cid:159)siedztwa, Patrz: metoda przeszukiwanie s(cid:159)siedztwa przypadek bazowy, 35, 51 przyrostek, 142 pseudokod, 23 pseudorandom number generator, Patrz: PRNG public key, Patrz: klucz publiczny Kup książkęPoleć książkę public key cryptography, Patrz: kryptografia z kluczem jawnym Q quicksort, Patrz: sortowanie szybkie R recurrence equation, Patrz: rekurencja recursion, Patrz: rekursja reduction, Patrz: redukcja redukcja, 187, 188, 191, 194, 197, 202, 203, 204, 205 rekurencja, 58 uniwersalna, 59, 65 rekursja, 34, 52 relacja przechodnia, 83 relaksacja, Patrz: os(cid:167)abianie relative prime number, Patrz: liczba wzgl(cid:163)dnie pierwsza relaxation step, Patrz: krok os(cid:167)abiaj(cid:159)cy Rivest Ronald, 153 rozdzielanie, 60, 62 procedura, 63, 66 rozwi(cid:159)zanie efektywne, 16, 17 oszcz(cid:163)dne, Patrz: rozwi(cid:159)zanie efektywne poprawne, 16, 17 prawie optymalne, 17 RSA, 16, 153, 154, 156, 159 run-length encoding, Patrz: kod seria- d(cid:167)ugo(cid:314)(cid:243) S satellite data, Patrz: dane towarzysz(cid:159)ce satisfiable formula, Patrz: formu(cid:167)a spe(cid:167)nialna secret key, Patrz: klucz tajny seed, Patrz: ziarno selection sort, Patrz: sortowanie wybieranie sentinel, Patrz: wartownik sequence, Patrz: ci(cid:159)g Shamir Adi, 153 shift cipher, Patrz: szyfr z przesuni(cid:163)ciem short circuiting, Patrz: operator krótko spinaj(cid:159)cy shortest of path, Patrz: (cid:314)cie(cid:343)ka najkrótsza Skorowidz 221 sieci (cid:314)rednica, 116 simple substitution cipher, Patrz: szyfr prosty podstawieniowy single-pair shortest path, Patrz: (cid:314)cie(cid:343)ka najkrótsza mi(cid:163)dzy jedn(cid:159) par(cid:159) wierzcho(cid:167)ków single-source shortest paths, Patrz: (cid:314)cie(cid:343)ka najkrótsza z jednym (cid:341)ród(cid:167)em singly linked list, Patrz: lista powi(cid:159)zana jednokierunkowa slot, Patrz: przegródka sort key, Patrz: sortowanie klucz sortowanie, 39 binarne, 210 czas dzia(cid:167)ania, 38, 45, 46, 49, 50, 59, 62, 65, 67, 71, 78, 92, 210 deterministyczne, 68 klucz, 38, 39 na kopcu, 110 na miejscu, 51, 56, 59 porównanie, 72 pozycyjne, 79, 80, 81, 210 czas dzia(cid:167)ania, 71 scalanie, 38, 50, 58, 67, 210 czas dzia(cid:167)ania, 50, 58, 59, 67, 71 stabilne, 79, 80 szybkie, 38, 59, 62, 67, 210 czas dzia(cid:167)ania, 59, 65, 67, 71 topologiczne, 87, 88, 89, 210 czas dzia(cid:167)ania, 92 w porz(cid:159)dku rosn(cid:159)cym, 20 wstawianie, 38, 46, 47, 50, 67, 210 czas dzia(cid:167)ania, 49, 50, 67, 71 wybieranie, 38, 43, 46, 67, 210 czas dzia(cid:167)ania, 45, 46, 50, 67, 71 zliczanie, 79, 80, 81, 210 czas dzia(cid:167)ania, 71, 78 procedura, 78 source vertex, Patrz: wierzcho(cid:167)ek (cid:341)ród(cid:167)owy sparse graph, Patrz: graf rzadki spe(cid:167)nialno(cid:314)(cid:243) 3-CNF, 191, 192, 199, 205, 206 stack, Patrz: stos stan, 139 state, Patrz: stan Stinson Douglas, 146 stopie(cid:295) wej(cid:314)ciowy, 88, 90, 94 wyj(cid:314)ciowy, 88, 94 Kup książkęPoleć książkę kryptografia z kluczem symetrycznym test prymarno(cid:314)ci 222 Algorytmy bez tajemnic stos, 89 string, Patrz: napis string matching, Patrz: problem dopasowywania napisów subsequence, Patrz: podci(cid:159)g subset-sum problem, Patrz: problem sumy podzbioru substring, Patrz: podnapis suffix, Patrz: przyrostek symbol (cid:134), 148 symmetric-key cryptography, Patrz: system AES, Patrz: AES szufladkowanie, 39 szyfr blokowy, 149, 150 (cid:167)a(cid:295)cuchowanie bloków, Patrz: (cid:167)a(cid:295)cuchowanie bloków szyfru prosty podstawieniowy, 146 z kluczem symetrycznym, 147, 150 z przesuni(cid:163)ciem, 146 szyfrowanie, 16, 145 d(cid:167)ugiego komunikatu, 160 standard zaawansowany, Patrz: AES (cid:317) (cid:314)cie(cid:343)ka, 93 krytyczna, 92, 93, 94 najkrótsza, 94, 95, 96 wierzcho(cid:167)ków, 115 pod(cid:314)cie(cid:343)ka, 117, 118 waga, 117 z jednym (cid:341)ród(cid:167)em, 97, 101 waga, 95, 117 (cid:314)rednica sieci, 116 (cid:314)wiadectwo, Patrz: certyfikat T tabela indeks pozycji, Patrz: wpis tablica, 24, 40, 90, 107 b(cid:167)(cid:159)d indeksowania, 48 element, 24 indeksowanie, 78 odwrotnie uporz(cid:159)dkowana, 67 permutowanie, 43 posortowana, 37, 38, Patrz te(cid:346): sortowanie prawie posortowana, 50 przeszukiwanie, 25 z haszowaniem, 179 target vertex, Patrz: wierzcho(cid:167)ek docelowy tekst jawny, 146, 149 kostkowanie bloków, 150 plasterkowanie bloków, 150 zaszyfrowany, 146, 149, 152 AKS, 154 Millera-Rabina, 154, 156 oparty na ma(cid:167)ym twierdzeniu Fermata, 159 text string, Patrz: napis z tekstem traveling-salesman problem, Patrz: problem triangle inequality, Patrz: nierówno(cid:314)(cid:243) komiwoja(cid:343)era trójk(cid:159)ta trie, 179 Turing Alan, 208 twierdzenie Fermata ma(cid:167)e, 156, 160 o liczbach pierwszych, 156 U nieskierowany uporz(cid:159)dkowanie, 37 leksykograficzne, 37 uwierzytelnienie, 145 V variable, Patrz: zmienna vertex, Patrz: wierzcho(cid:167)ek vertex cover, Patrz: pokrycie wierzcho(cid:167)kowe vertex cover problem, Patrz: pokrycie wierzcho(cid:167)kowe problem vertex degree, Patrz: wierzcho(cid:167)ek stopie(cid:295) mi(cid:163)dzy jedn(cid:159) par(cid:159) wierzcho(cid:167)ków, 101 mi(cid:163)dzy wszystkimi parami nierozstrzygalny undirected graph, Patrz: graf undecidable problem, Patrz: problem Kup książkęPoleć książkę W Warshall Stephen, 116 warto(cid:314)ciowanie, 192 wartownik, 28 weight, Patrz: kraw(cid:163)d(cid:341) waga weight of path, Patrz: (cid:314)cie(cid:343)ka waga weighted directed graph, Patrz: graf skierowany wa(cid:343)ony wektor pocz(cid:159)tkowy, 150 wetware, 23 w(cid:163)ze(cid:167), 108, Patrz: wierzcho(cid:167)ek klucz, 109 wewn(cid:163)trzny, 166 wierzcho(cid:167)ek, 87 docelowy, 96 stopie(cid:295), 184 (cid:341)ród(cid:167)owy, 96 wpis, 24 Skorowidz 223 wyszukiwanie binarne, 37, 39, 40, 41, 67 czas dzia(cid:167)ania, 39, 43, 67 zapis rekurencyjny, 42 liniowe, 25, 26, 27, 67, 210 czas dzia(cid:167)ania, 29, 30, 31, 67 z wartownikiem, 28, 29, 32 zapis rekurencyjny, 35 XOR, 148, 149 X Z zale(cid:343)no(cid:314)(cid:243) rekurencyjna, Patrz: rekurencja zasoby obliczeniowe, 16, 17 ziarno, 161 z(cid:167)(cid:159)czenie, 142 zmienna, 26, 27 p(cid:163)tli, 26 znak (cid:134), 148 zdekodowany, 170 Kup książkęPoleć książkę 224 Algorytmy bez tajemnic Kup książkęPoleć książkę
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy bez tajemnic
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: