Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00049 007615 18991614 na godz. na dobę w sumie
Algorytmy dla bystrzaków - książka
Algorytmy dla bystrzaków - książka
Autor: , Liczba stron: 424
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-6076-1 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> python - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

Zestaw algorytmy z ich zastosowaniami

Zdobądź umiejętności posługiwania się algorytmami

Naucz się wykorzystywać Pythona do testowania algorytmów

Myśl za pomocą algorytmów

Ten jasny i przystępny przewodnik pokazuje, w jaki sposób algorytmy wpływają na nasze codzienne życie - od interakcji online po osobistą komunikację. Są również niezwykle ważne, jeśli chodzi o podejmowanie różnego rodzaju decyzji. Jeśli chcesz wiedzieć, jak korzystać z procedur rozwiązywania problemów w prawdziwym świecie, książka Algorytmy dla bystrzaków zagwarantuje Ci doskonałe wprowadzenie do tej fascynującej, wszechobecnej dziedziny.

W książce:

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

Darmowy fragment publikacji:

Tytuł oryginału: Algorithms For Dummies Tłumaczenie: Radosław Meryk ISBN: 978-83-283-6076-1 Original English language edition Copyright © 2017 by John Wiley Sons, Inc., Hoboken, New Jersey. All rights reserved including the right of reproduction in whole in part in any form. This translation published by arrangement with John Wiley Sons, Inc. Oryginalne angielskie wydanie © 2017 by John Wiley Sons, Inc., Hoboken, New Jersey. Wszelkie prawa, włączając prawo do reprodukcji całości lub części w jakiejkolwiek formie, zarezerwowane. Tłumaczenie opublikowane na mocy porozumienia z John Wiley Sons, Inc. Translation copyright © 2019 by Helion S.A. Wiley, the Wiley Publishing logo, For Dummies, Dla Bystrzaków, the Dummies Man logo, Dummies.com, Making Everything Easier and related trade dress are trademarks or registered trademarks of John Wiley and Sons, Inc. and/or its affiliates in the United States and/or other countries. Used under license. All other trademarks are the property of their respective owners. Wiley, the Wiley Publishing logo, For Dummies, Dla Bystrzaków, the Dummies Man logo, Dummies.com, Making Everything Easier i związana z tym szata graficzna są markami handlowymi John Wiley and Sons, Inc. i/lub firm stowarzyszonych w Stanach Zjednoczonych i/lub innych krajach. Wykorzystywane na podstawie licencji. Wszystkie pozostałe znaki handlowe są własnością ich właścicieli. Media and software compilation copyright © 2017 by John Wiley Sons, Inc. All rights reserved. Autor oraz HELION SA dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz HELION SA nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://dlabystrzakow.pl/user/opinie/algoby Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Pliki z przykładami omawianymi w książce można znaleźć pod adresem: ftp://ftp.helion.pl/przyklady/algoby.zip Wydawnictwo HELION ul. Kościuszki 1c, 44-100 Gliwice tel. 32 231 22 19, 32 230 98 63 e-mail: dlabystrzakow@dlabystrzakow.pl WWW: http://dlabystrzakow.pl Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:285)ci O autorach .......................................................................................15 Podzi(cid:219)kowania od autorów ...........................................................17 Wprowadzenie ................................................................................19 CZ(cid:218)(cid:284)(cid:200) I: ZACZYNAMY .................................................................25 ROZDZIA(cid:259) 1: Wprowadzenie do algorytmów ......................................27 Co to jest algorytm? .................................................................................................28 Zastosowania algorytmów ................................................................................30 Algorytmy s(cid:199) wsz(cid:219)dzie .......................................................................................32 Stosowanie komputerów do rozwi(cid:199)zywania problemów ...................................33 Wykorzystanie nowoczesnych procesorów i procesorów graficznych ........34 Wykorzystanie uk(cid:260)adów specjalnych ................................................................35 Wykorzystanie sieci ............................................................................................36 Wykorzystywanie dost(cid:219)pnych danych .............................................................37 Odró(cid:318)nianie problemów od rozwi(cid:199)za(cid:262) .................................................................38 Poprawno(cid:285)(cid:201) a skuteczno(cid:285)(cid:201) ...............................................................................38 Nie ma nic za darmo! .........................................................................................39 Dostosowanie strategii do problemu ..............................................................39 Zrozumia(cid:260)y opis algorytmów .............................................................................39 Stawianie czo(cid:260)a trudnym problemom ..............................................................40 Strukturyzacja danych w celu uzyskania rozwi(cid:199)zania ..........................................40 Zrozumienie punktu widzenia komputera ......................................................41 Uk(cid:260)ad danych robi ró(cid:318)nic(cid:219) .................................................................................41 Spis tre(cid:285)ci 5 Poleć książkęKup książkę ROZDZIA(cid:259) 2: Projekt algorytmu ............................................................43 Rozpocz(cid:219)cie rozwi(cid:199)zywania problemu ..................................................................44 Modelowanie rzeczywistych problemów .........................................................45 Znajdowanie rozwi(cid:199)za(cid:262) i kontrprzyk(cid:260)adów .....................................................47 Na ramionach olbrzymów .................................................................................48 Dziel i zwyci(cid:219)(cid:318)aj ........................................................................................................48 Unikanie rozwi(cid:199)za(cid:262) si(cid:260)owych ............................................................................49 Zacznij od uproszczenia .....................................................................................50 Rozwi(cid:199)zanie sk(cid:260)adowych problemu zwykle jest (cid:260)atwiejsze ni(cid:318) rozwi(cid:199)zanie ca(cid:260)ego problemu .........................................50 Zach(cid:260)anno(cid:285)(cid:201) mo(cid:318)e by(cid:201) dobra .................................................................................51 Stosowanie zach(cid:260)annego wnioskowania .........................................................51 Osi(cid:199)ganie dobrego rozwi(cid:199)zania .......................................................................52 Koszty obliczeniowe i korzystanie z heurystyk .....................................................53 Reprezentowanie problemu jako przestrzeni .................................................54 Wykonywanie losowych ruchów i liczenie na szcz(cid:219)(cid:285)cie .................................54 U(cid:318)ywanie heurystyki i funkcji kosztu ................................................................55 Ocena algorytmów ...................................................................................................56 Symulacje z wykorzystaniem maszyn abstrakcyjnych ...................................57 Wi(cid:219)cej abstrakcji .................................................................................................58 Wykorzystanie funkcji ........................................................................................59 ROZDZIA(cid:259) 3: Wykorzystanie Pythona do pracy z algorytmami ........63 Zalety Pythona ..........................................................................................................65 Dlaczego w tej ksi(cid:199)(cid:318)ce korzystamy z Pythona? ...............................................65 Korzystanie z MATLAB-a ....................................................................................67 Inne (cid:285)rodowiska testowania algorytmów ........................................................68 Dystrybucje Pythona ................................................................................................68 Pobieranie (cid:285)rodowiska Anaconda Analytics ....................................................69 Enthought Canopy Express ...............................................................................70 (cid:284)rodowisko pythonxy .........................................................................................70 WinPython ...........................................................................................................71 Instalowanie Pythona w systemie Linux ................................................................71 Instalowanie Pythona w systemie MacOS .............................................................72 Instalowanie Pythona w systemie Windows .........................................................74 Pobieranie zestawów danych i przyk(cid:260)adowego kodu ..........................................77 Korzystanie ze (cid:285)rodowiska Jupyter Notebook ................................................77 Definiowanie repozytorium kodu .....................................................................79 Zestawy danych wykorzystywane w tej ksi(cid:199)(cid:318)ce ..............................................84 6 Algorytmy dla bystrzaków Poleć książkęKup książkę ROZDZIA(cid:259) 4: Wprowadzenie do Pythona jako narz(cid:219)dzia do programowania algorytmów ....................................87 Dzia(cid:260)ania na liczbach i operacje logiczne ..............................................................89 Przypisywanie warto(cid:285)ci do zmiennych ............................................................90 Wykonywanie dzia(cid:260)a(cid:262) arytmetycznych ............................................................91 Porównywanie danych za pomoc(cid:199) wyra(cid:318)e(cid:262) boolowskich ............................92 Tworzenie ci(cid:199)gów znaków i pos(cid:260)ugiwanie si(cid:219) nimi ..............................................95 Dzia(cid:260)ania na datach ..................................................................................................97 Tworzenie i stosowanie funkcji ...............................................................................98 Tworzenie funkcji wielokrotnego u(cid:318)ytku .........................................................98 Wywo(cid:260)ywanie funkcji ..........................................................................................99 Stosowanie instrukcji warunkowych i p(cid:219)tli .........................................................102 Podejmowanie decyzji za pomoc(cid:199) instrukcji if .............................................102 Wybór pomi(cid:219)dzy wieloma opcjami z wykorzystaniem decyzji zagnie(cid:318)d(cid:318)onych ..............................................................................................103 Wykonywanie powtarzaj(cid:199)cych si(cid:219) zada(cid:262) za pomoc(cid:199) p(cid:219)tli for ....................104 Korzystanie z instrukcji while ..........................................................................105 Przechowywanie danych z wykorzystaniem zbiorów, list i krotek ...................106 Tworzenie zbiorów ...........................................................................................106 Tworzenie list ....................................................................................................107 Tworzenie i u(cid:318)ywanie krotek ...........................................................................108 Definiowanie przydatnych iteratorów .................................................................110 Indeksowanie danych z wykorzystaniem s(cid:260)owników .........................................111 ROZDZIA(cid:259) 5: Wykonywanie podstawowych operacji na danych za pomoc(cid:199) Pythona ....................................113 Wykonywanie oblicze(cid:262) za pomoc(cid:199) wektorów i macierzy ..................................114 Operacje na warto(cid:285)ciach skalarnych i na wektorach ...................................115 Mno(cid:318)enie wektorów .........................................................................................117 Najlepiej rozpocz(cid:199)(cid:201) od utworzenia macierzy ................................................118 Mno(cid:318)enie macierzy ..........................................................................................119 Definiowanie zaawansowanych operacji na macierzach .............................120 W(cid:260)a(cid:285)ciwe tworzenie kombinacji ...........................................................................122 Rozró(cid:318)nianie permutacji ..................................................................................122 Tasowanie kombinacji ......................................................................................123 Obs(cid:260)uga powtórze(cid:262) ..........................................................................................124 Uzyskiwanie po(cid:318)(cid:199)danych wyników za pomoc(cid:199) rekurencji ................................125 Co to jest rekurencja? .......................................................................................125 Eliminowanie rekurencji wywo(cid:260)a(cid:262) ogonowych .............................................128 Szybsze wykonywanie zada(cid:262) ................................................................................129 Dziel i zwyci(cid:219)(cid:318)aj .................................................................................................129 Rozró(cid:318)nianie mo(cid:318)liwych rozwi(cid:199)za(cid:262) ................................................................132 Spis tre(cid:285)ci 7 Poleć książkęKup książkę CZ(cid:218)(cid:284)(cid:200) II: ZNACZENIE SORTOWANIA I WYSZUKIWANIA ........135 ROZDZIA(cid:259) 6: Strukturyzowanie danych ............................................137 Niezb(cid:219)dno(cid:285)(cid:201) struktury ..........................................................................................138 (cid:259)atwiejsze ogl(cid:199)danie tre(cid:285)ci ..............................................................................138 Dopasowywanie danych z ró(cid:318)nych (cid:316)róde(cid:260) ....................................................139 Korygowanie danych ........................................................................................140 Uk(cid:260)adanie danych w stos .......................................................................................143 Porz(cid:199)dkowanie z wykorzystaniem stosów ....................................................143 Korzystanie z kolejek ........................................................................................145 Wyszukiwanie danych z wykorzystaniem s(cid:260)owników ...................................146 Drzewa .....................................................................................................................147 Podstawowe wiadomo(cid:285)ci o drzewach ...........................................................147 Budowanie drzewa ...........................................................................................148 Reprezentowanie relacji za pomoc(cid:199) grafu ..........................................................150 Wi(cid:219)cej ni(cid:318) drzewa .............................................................................................150 Budowanie grafów ...........................................................................................151 ROZDZIA(cid:259) 7: Organizowanie i wyszukiwanie danych ......................155 Sortowanie z wykorzystaniem algorytmów MergeSort i QuickSort .................156 Dlaczego wa(cid:318)ne jest sortowanie danych? .....................................................156 Naiwne sortowanie danych .............................................................................158 Lepsze techniki sortowania .............................................................................160 Korzystanie z drzew wyszukiwania i stert ...........................................................164 Potrzeba skutecznego wyszukiwania .............................................................165 Budowanie drzewa wyszukiwania binarnego ...............................................167 Wyspecjalizowane wyszukiwania za pomoc(cid:199) sterty binarnej .....................168 Korzystanie z tablic asocjacyjnych ........................................................................169 Pojemniki na dane ............................................................................................169 Zapobieganie kolizjom .....................................................................................171 Tworzenie w(cid:260)asnej funkcji haszuj(cid:199)cej ............................................................173 CZ(cid:218)(cid:284)(cid:200) III: (cid:284)WIAT GRAFÓW .......................................................175 ROZDZIA(cid:259) 8: Podstawowe informacje o grafach ..............................177 Znaczenie sieci ........................................................................................................178 Istota grafu ........................................................................................................178 Grafy s(cid:199) wsz(cid:219)dzie .............................................................................................180 Spo(cid:260)eczno(cid:285)ciowa strona grafów .....................................................................181 Podgrafy ............................................................................................................182 8 Algorytmy dla bystrzaków Poleć książkęKup książkę Definiowanie sposobu rysowania grafu ..............................................................183 Rozró(cid:318)nianie kluczowych atrybutów ..............................................................183 Rysowanie grafu ...............................................................................................185 Pomiar funkcjonalno(cid:285)ci grafu ...............................................................................186 Zliczanie kraw(cid:219)dzi i wierzcho(cid:260)ków ..................................................................186 Obliczanie centralno(cid:285)ci ....................................................................................188 Liczbowa reprezentacja grafu ...............................................................................190 Dodawanie grafu do macierzy ........................................................................191 U(cid:318)ywanie reprezentacji rzadkich ....................................................................192 Korzystanie z list do przechowywania grafu .................................................192 ROZDZIA(cid:259) 9: Po(cid:260)(cid:199)cz kropki ..................................................................195 Efektywne przechodzenie przez graf ...................................................................196 Tworzenie grafu ................................................................................................197 Przeszukiwanie najpierw wszerz ....................................................................198 Przeszukiwanie najpierw w g(cid:260)(cid:199)b .....................................................................199 Okre(cid:285)lanie, której aplikacji u(cid:318)y(cid:201) ......................................................................202 Sortowanie elementów grafu ...............................................................................202 Skierowane grafy acykliczne ............................................................................203 Sortowanie topologiczne .................................................................................204 Redukcja do minimalnego drzewa rozpinaj(cid:199)cego .............................................205 Wybór odpowiednich algorytmów .................................................................208 Kolejki z priorytetami .......................................................................................209 Wykorzystanie algorytmu Prima .....................................................................210 Testowanie algorytmu Kruskala .....................................................................211 Który algorytm dzia(cid:260)a najlepiej? ......................................................................213 Znalezienie najkrótszej trasy ................................................................................214 Co to znaczy znale(cid:316)(cid:201) najkrótsz(cid:199) (cid:285)cie(cid:318)k(cid:219)? .......................................................214 Wyja(cid:285)nienie algorytmu Dijkstry ......................................................................216 ROZDZIA(cid:259) 10: Odkrywanie tajemnic grafów .......................................219 Sieci spo(cid:260)eczno(cid:285)ciowe jako grafy ..........................................................................220 Klasteryzacja sieci .............................................................................................220 Odkrywanie spo(cid:260)eczno(cid:285)ci ................................................................................223 Poruszanie si(cid:219) po grafie ........................................................................................225 Zliczanie stopni separacji .................................................................................225 Losowe poruszanie si(cid:219) po grafie ....................................................................227 Spis tre(cid:285)ci 9 Poleć książkęKup książkę ROZDZIA(cid:259) 11: Pobieranie w(cid:260)a(cid:285)ciwej strony internetowej .................229 Odkrywanie (cid:285)wiata za pomoc(cid:199) wyszukiwarki .....................................................230 Wyszukiwanie danych w internecie ................................................................230 Jak znale(cid:316)(cid:201) w(cid:260)a(cid:285)ciwe dane? ..............................................................................230 Czym jest algorytm PageRank? .............................................................................232 Wnioskowanie w algorytmie PageRank .........................................................232 Szczegó(cid:260)y dzia(cid:260)ania algorytmu PageRank ......................................................234 Implementacja algorytmu PageRank ...................................................................234 Implementacja skryptu Pythona .....................................................................235 Rozwi(cid:199)zywanie problemów naiwnej implementacji ....................................238 Nuda i teleportacja ...........................................................................................240 Jak dzia(cid:260)a wyszukiwarka? .................................................................................242 Inne zastosowania algorytmu PageRank .......................................................242 Nie tylko paradygmat PageRank ..........................................................................243 Zapytania semantyczne ...................................................................................243 Stosowanie technik AI do tworzenia rankingu wyników wyszukiwania .....244 CZ(cid:218)(cid:284)(cid:200) IV: ZMAGANIA Z BIG DATA ...........................................245 ROZDZIA(cid:259) 12: Zarz(cid:199)dzanie obszernymi zbiorami danych .................247 Przekszta(cid:260)canie mocy obliczeniowej w dane ......................................................248 Implikacje prawa Moore’a ...............................................................................249 Dane s(cid:199) wsz(cid:219)dzie .............................................................................................251 Zastosowanie algorytmów w biznesie ...........................................................253 Strumieniowy przep(cid:260)yw danych ...........................................................................255 Analiza strumieni z wykorzystaniem odpowiednich receptur ....................256 Rezerwowanie w(cid:260)a(cid:285)ciwych danych .................................................................257 Szkicowanie odpowiedzi z danych strumienia ...................................................261 Filtrowanie elementów strumienia „na pami(cid:219)(cid:201)” ...........................................262 Przyk(cid:260)ad filtra Blooma ......................................................................................264 Znajdowanie liczby ró(cid:318)nych elementów ........................................................267 Zliczanie obiektów w strumieniu ....................................................................269 ROZDZIA(cid:259) 13: Wspó(cid:260)bie(cid:318)ne wykonywanie operacji ...........................271 Zarz(cid:199)dzanie ogromnymi ilo(cid:285)ciami danych ..........................................................272 Paradygmat przetwarzania równoleg(cid:260)ego .....................................................272 Dystrybucja plików i operacji ..........................................................................275 Zastosowanie rozwi(cid:199)zania MapReduce .........................................................277 Algorytmy dla techniki MapReduce .....................................................................280 Konfigurowanie symulacji MapReduce ..........................................................281 Zapytanie przez mapowanie ...........................................................................283 10 Algorytmy dla bystrzaków Poleć książkęKup książkę ROZDZIA(cid:259) 14: Kompresja danych .........................................................287 Zmniejszenie rozmiaru danych ............................................................................288 Kodowanie .........................................................................................................288 Efekty kompresji ...............................................................................................290 Wybór rodzaju kompresji ................................................................................291 Dobór kodowania .............................................................................................293 Kodowanie za pomoc(cid:199) kompresji Huffmana ................................................295 Zapami(cid:219)tywanie sekwencji za pomoc(cid:199) LZW .................................................297 CZ(cid:218)(cid:284)(cid:200) V: TRUDNE PROBLEMY .................................................303 ROZDZIA(cid:259) 15: Algorytmy zach(cid:260)anne ....................................................305 Kiedy lepiej jest by(cid:201) zach(cid:260)annym? ........................................................................306 Dlaczego zach(cid:260)anno(cid:285)(cid:201) mo(cid:318)e by(cid:201) dobra? .......................................................307 Zarz(cid:199)dzanie algorytmami zach(cid:260)annymi .........................................................308 Problemy NP-zupe(cid:260)ne ......................................................................................310 Dlaczego zach(cid:260)anno(cid:285)(cid:201) mo(cid:318)e by(cid:201) po(cid:318)yteczna? ....................................................312 Organizacja danych z wykorzystaniem pami(cid:219)ci podr(cid:219)cznej komputera ...312 Rywalizacja o zasoby ........................................................................................314 Kodowanie Huffmana raz jeszcze ...................................................................316 ROZDZIA(cid:259) 16: Programowanie dynamiczne ........................................321 Zasady programowania dynamicznego ..............................................................322 Baza historyczna ...............................................................................................322 Zmiana problemów na dynamiczne ...............................................................323 Dynamiczne rzutowanie rekurencji ................................................................325 Wykorzystanie memoizacji ..............................................................................327 Najlepsze procedury programowania dynamicznego .......................................329 Co jest w plecaku? ............................................................................................330 Zwiedzanie miast ..............................................................................................333 Przybli(cid:318)one wyszukiwanie ci(cid:199)gów znaków ....................................................338 ROZDZIA(cid:259) 17: Korzystanie z algorytmów losowych ...........................341 Jak dzia(cid:260)a randomizacja? .......................................................................................342 Dlaczego randomizacja jest potrzebna? ........................................................343 Czym jest prawdopodobie(cid:262)stwo? ..................................................................344 Rozk(cid:260)ady prawdopodobie(cid:262)stwa .....................................................................345 Symulacja u(cid:318)ycia metody Monte Carlo ..........................................................348 Wykorzystanie losowo(cid:285)ci w logice algorytmu .....................................................350 Obliczanie mediany za pomoc(cid:199) algorytmu Quickselect ..............................350 Symulacja przy u(cid:318)yciu algorytmu Monte Carlo .............................................353 Szybsze sortowanie dzi(cid:219)ki algorytmowi Quicksort ......................................355 Spis tre(cid:285)ci 11 Poleć książkęKup książkę ROZDZIA(cid:259) 18: Wyszukiwanie lokalne ...................................................357 Co to jest wyszukiwanie lokalne? .........................................................................358 Znajomo(cid:285)(cid:201) s(cid:199)siedztwa .....................................................................................358 Sztuczki stosowane w wyszukiwaniu lokalnym ..................................................361 Problem wspinaczki z n-królowymi ................................................................362 Symulowane wy(cid:318)arzanie .................................................................................364 Unikanie powtórze(cid:262) przy u(cid:318)yciu przeszukiwania tabu ................................366 Rozwi(cid:199)zywanie warunku spe(cid:260)nialno(cid:285)ci uk(cid:260)adów logicznych .............................367 Rozwi(cid:199)zywanie problemu 2-SAT z wykorzystaniem randomizacji .............368 Implementacja kodu w Pythonie ....................................................................369 Lepszy punkt wyj(cid:285)cia ........................................................................................371 ROZDZIA(cid:259) 19: Wykorzystanie programowania liniowego .................375 Stosowanie funkcji liniowych jako narz(cid:219)dzia ......................................................376 Podstawy matematyczne .................................................................................377 Upraszczanie podczas planowania .................................................................379 Geometria w metodzie simplex ......................................................................379 Ograniczenia .....................................................................................................381 Programowania liniowe w praktyce .....................................................................382 Konfigurowanie modu(cid:260)u PuLP ........................................................................383 Optymalizacja produkcji i przychodów ..........................................................383 ROZDZIA(cid:259) 20: Heurystyka .....................................................................389 Klasyfikacja heurystyk ............................................................................................390 Cele heurystyki ..................................................................................................390 Od genetyki do sztucznej inteligencji .............................................................391 Sterowanie robotem za pomoc(cid:199) heurystyki .......................................................392 Skauting w nieznanym terenie ........................................................................393 Wykorzystanie miar odleg(cid:260)o(cid:285)ci jako heurystyki ............................................394 Algorytmy wyszukiwania (cid:285)cie(cid:318)ki ...........................................................................395 Tworzenie labiryntu ..........................................................................................396 Szybkie wyszukiwanie najlepszej trasy ..........................................................398 Poruszanie si(cid:219) heurystyczne z wykorzystaniem algorytmu A* ...................402 12 Algorytmy dla bystrzaków Poleć książkęKup książkę CZ(cid:218)(cid:284)(cid:200) VI: DEKALOGI .................................................................407 ROZDZIA(cid:259) 21: Dziesi(cid:219)(cid:201) algorytmów, które zmieni(cid:260)y (cid:285)wiat ................409 Korzystanie z procedur sortowania .....................................................................410 Poszukiwanie informacji z wykorzystaniem procedur wyszukiwania ..............411 Zmienianie sytuacji za pomoc(cid:199) liczb losowych ...................................................411 Kompresja danych .................................................................................................412 Zachowanie poufno(cid:285)ci danych .............................................................................412 Zmiana dziedziny danych ......................................................................................413 Analiza powi(cid:199)za(cid:262) w danych ..................................................................................413 Wykrywanie wzorców w danych ...........................................................................414 Automatyzacja i automatyczne odpowiedzi .......................................................415 Tworzenie unikatowych identyfikatorów ............................................................415 ROZDZIA(cid:259) 22: Dziesi(cid:219)(cid:201) problemów algorytmicznych do rozwi(cid:199)zania ...............................................................417 Obs(cid:260)uga wyszukiwania tekstu ...............................................................................418 Rozró(cid:318)nianie s(cid:260)ów ..................................................................................................418 Ustalenie, czy aplikacja si(cid:219) zako(cid:262)czy ...................................................................419 Tworzenie i stosowanie funkcji jednokierunkowych .........................................419 Mno(cid:318)enie bardzo du(cid:318)ych liczb .............................................................................420 Równy podzia(cid:260) zasobów ........................................................................................420 Skrócenie czasu obliczania odleg(cid:260)o(cid:285)ci edycji ......................................................421 Szybkie rozwi(cid:199)zywanie problemów .....................................................................421 Gra w gr(cid:219) parzysto(cid:285)ci ............................................................................................422 Zrozumienie problemów przestrzennych ...........................................................422 (cid:3)(cid:3) Skorowidz .......................................................................423 Spis tre(cid:285)ci 13 Poleć książkęKup książkę 14 Algorytmy dla bystrzaków Poleć książkęKup książkę W TYM ROZDZIALE: (cid:27) Co rozumiemy przez algorytm? (cid:27) Wykorzystywanie komputerów do dostarczania rozwi(cid:199)za(cid:262) za pomoc(cid:199) algorytmów (cid:27) Ustalenie ró(cid:318)nic pomi(cid:219)dzy problemami a rozwi(cid:199)zaniami (cid:27) Operowanie na danych w celu znalezienia rozwi(cid:199)za(cid:262) Rozdzia(cid:260) (cid:1090) Wprowadzenie do algorytmów J e(cid:337)li jeste(cid:337) podobny do wi(cid:243)kszo(cid:337)ci ludzi, zapewne poczujesz si(cid:243) zagubiony, otwieraj(cid:241)c t(cid:243) ksi(cid:241)(cid:363)k(cid:243) i rozpoczynaj(cid:241)c przygod(cid:243) z algorytmami. W tekstach dotycz(cid:241)cych algorytmów przewa(cid:363)nie bowiem nie wspomina si(cid:243), czym s(cid:241) al- gorytmy, a tym bardziej po co si(cid:243) ich u(cid:363)ywa. W wi(cid:243)kszo(cid:337)ci tekstów zak(cid:251)ada si(cid:243), (cid:363)e ju(cid:363) czytelnik co(cid:337) wie o algorytmach i czyta o nich po to, aby wzbogaci(cid:289) swoj(cid:241) wiedz(cid:243). Co ciekawe, niektóre ksi(cid:241)(cid:363)ki wprowadzaj(cid:241) myl(cid:241)c(cid:241) definicj(cid:243) algorytmu, która w zasadzie go nie definiuje, a czasem nawet uto(cid:363)samia z jak(cid:241)(cid:337) inn(cid:241) form(cid:241) abstrakcyjnego, liczbowego lub symbolicznego wyra(cid:363)enia. Pierwsza cz(cid:243)(cid:337)(cid:289) tego rozdzia(cid:251)u ma za zadanie pomóc Ci zrozumie(cid:289), co to jest al- gorytm i dlaczego znajomo(cid:337)(cid:289) algorytmów jest przydatna. Algorytmy nie s(cid:241) wie- dz(cid:241) tajemn(cid:241) — u(cid:363)ywa si(cid:243) ich wsz(cid:243)dzie. Prawdopodobnie korzystasz z nich od lat, wcale o tym nie wiedz(cid:241)c. Algorytmy s(cid:241) kr(cid:243)gos(cid:251)upem, który wspiera i reguluje to, co jest wa(cid:363)ne w coraz bardziej z(cid:251)o(cid:363)onym i technicznym spo(cid:251)ecze(cid:321)stwie. W tym rozdziale przybli(cid:363)amy tak(cid:363)e, jak wykorzystywa(cid:289) komputery do tworzenia rozwi(cid:241)za(cid:321) problemów przy u(cid:363)yciu algorytmów, jak rozró(cid:363)nia(cid:289) problemy od roz- wi(cid:241)za(cid:321) oraz jak operowa(cid:289) danymi, aby znale(cid:361)(cid:289) rozwi(cid:241)zanie. Celem tego rozdzia(cid:251)u ROZDZIA(cid:259) 1 Wprowadzenie do algorytmów 27 Poleć książkęKup książkę jest pomoc w odró(cid:363)nieniu algorytmów od innych zada(cid:321), które ludzie wykonuj(cid:241) i które myl(cid:241) z algorytmami. Krótko mówi(cid:241)c, w tym rozdziale odkryjesz, do czego s(cid:241) Ci potrzebne algorytmy i jak je zastosowa(cid:289) do danych. Co to jest algorytm? Chocia(cid:363) ludzie stosowali algorytmy r(cid:243)cznie przez tysi(cid:241)ce lat, takie podej(cid:337)cie po- ch(cid:251)ania ogrom czasu i wymaga wielu oblicze(cid:321) numerycznych, w zale(cid:363)no(cid:337)ci od z(cid:251)o(cid:363)ono(cid:337)ci problemu, który chcemy rozwi(cid:241)za(cid:289). Algorytmy dotycz(cid:241) znajdowania rozwi(cid:241)za(cid:321) — im szybciej i (cid:251)atwiej, tym lepiej. Istnieje ogromna luka mi(cid:243)dzy al- gorytmami matematycznymi historycznie stworzonymi przez geniuszy swoich czasów, takich jak Euklides, Newton czy Gauss, a nowoczesnymi algorytmami opracowanymi na uniwersytetach i w prywatnych laboratoriach badawczo- rozwojowych. G(cid:251)ównym powodem tej luki jest wykorzystanie komputerów. Ich stosowanie do rozwi(cid:241)zywania problemów za pomoc(cid:241) odpowiednich algorytmów pozwala znacznie szybciej wykonywa(cid:289) zadania. W(cid:251)a(cid:337)nie dlatego — od czasów pojawienia si(cid:243) pot(cid:243)(cid:363)nych systemów komputerowych — rozwój nowych algoryt- mów post(cid:243)puje tak szybko. Prawdopodobnie zauwa(cid:363)y(cid:251)e(cid:337), (cid:363)e wspó(cid:251)cze(cid:337)nie poja- wia si(cid:243) coraz wi(cid:243)cej rozwi(cid:241)za(cid:321) problemów. Cz(cid:243)(cid:337)ciowo wynika to st(cid:241)d, (cid:363)e moc obliczeniowa komputerów jest zarówno tania, jak i stale ro(cid:337)nie. Komputery (cza- sami w postaci specjalnego sprz(cid:243)tu) staj(cid:241) si(cid:243) wszechobecne w(cid:251)a(cid:337)nie z powodu ich zdolno(cid:337)ci do rozwi(cid:241)zywania problemów przy u(cid:363)yciu algorytmów. Podczas pracy z algorytmami bierze si(cid:243) pod uwag(cid:243) dane wej(cid:337)ciowe, po(cid:363)(cid:241)dane dane wynikowe i proces (ci(cid:241)g dzia(cid:251)a(cid:321)) prowadz(cid:241)cy do uzyskania po(cid:363)(cid:241)danego wyniku na podstawie danych wej(cid:337)ciowych. Mo(cid:363)esz jednak (cid:361)le zrozumie(cid:289) terminologi(cid:243) i niew(cid:251)a(cid:337)ciwie postrzega(cid:289) algorytmy, poniewa(cid:363) nigdy nie zastanawia(cid:251)e(cid:337) si(cid:243) nad tym, jak w rzeczywisto(cid:337)ci dzia(cid:251)aj(cid:241). W trzecim podrozdziale tego rozdzia(cid:251)u omó- wili(cid:337)my algorytmy w (cid:337)wiecie rzeczywistym, to znaczy dokonali(cid:337)my przegl(cid:241)du terminologii stosowanej w celu zrozumienia algorytmów i zaprezentowali(cid:337)my algorytmy w sposób, który dowodzi, (cid:363)e rzeczywisty (cid:337)wiat jest cz(cid:243)sto daleki od do- skona(cid:251)o(cid:337)ci. Umiej(cid:243)tno(cid:337)(cid:289) realistycznego opisania algorytmu pozwala tak(cid:363)e z(cid:251)agodzi(cid:289) oczekiwania wobec algorytmów i odzwierciedli(cid:289) rzeczywisty stan tego, co faktycz- nie mo(cid:363)na za ich pomoc(cid:241) osi(cid:241)gn(cid:241)(cid:289). Ta ksi(cid:241)(cid:363)ka prezentuje algorytmy na wiele sposobów. Poniewa(cid:363) jednak dostarcza opisu sposobu, w jaki algorytmy si(cid:243) zmieniaj(cid:241) i wzbogacaj(cid:241) (cid:363)ycie ludzi, koncen- truje si(cid:243) na algorytmach wykorzystywanych do przetwarzania danych z u(cid:363)yciem komputerów. To one dostarczaj(cid:241) wymaganej mocy obliczeniowej. Maj(cid:241)c to na uwadze, algorytmy, z którymi pracujesz w tej ksi(cid:241)(cid:363)ce, wymagaj(cid:241) wprowadzania danych w okre(cid:337)lonej formie, co czasami oznacza modyfikowanie danych w celu ich dopasowania do wymaga(cid:321) algorytmu. Przetwarzanie danych nie zmienia ich zawarto(cid:337)ci. Zmienia jedynie prezentacj(cid:243) i form(cid:243) danych. Dzi(cid:243)ki temu algorytmy mog(cid:241) pomóc Ci zauwa(cid:363)y(cid:289) nowe wzorce — takie, które wcze(cid:337)niej nie by(cid:251)y widoczne (cho(cid:289) wyst(cid:243)powa(cid:251)y w danych przez ca(cid:251)y czas). 28 CZ(cid:218)(cid:284)(cid:200) I Zaczynamy Poleć książkęKup książkę (cid:449)ród(cid:251)a informacji o algorytmach cz(cid:243)sto przedstawiaj(cid:241) je w sposób, który jest myl(cid:241)cy — zbyt wyrafinowany lub wr(cid:243)cz niepoprawny. W tej ksi(cid:241)(cid:363)ce u(cid:363)yto na- st(cid:243)puj(cid:241)cych definicji dla terminów, które ludzie cz(cid:243)sto myl(cid:241) z algorytmami: (cid:27) Równanie — liczby i symbole, które w ca(cid:260)o(cid:285)ci s(cid:199) równe okre(cid:285)lonej warto(cid:285)ci. Równanie zawsze zawiera znak równo(cid:285)ci, dzi(cid:219)ki czemu wiemy, (cid:318)e liczby i symbole reprezentuj(cid:199) okre(cid:285)lon(cid:199) warto(cid:285)(cid:201) po drugiej stronie znaku równo(cid:285)ci. Równania na ogó(cid:260) zawieraj(cid:199) zmienne informacje zaprezentowane w symbolicznej formie, cho(cid:201) nie musz(cid:199) u(cid:318)ywa(cid:201) zmiennych. (cid:27) Wzór (formu(cid:260)a) — po(cid:260)(cid:199)czenie liczb i symboli stosowane do wyra(cid:318)enia informacji lub poj(cid:219)(cid:201). Wzory zazwyczaj przedstawiaj(cid:199) poj(cid:219)cia matematyczne lub logiczne, takie jak definiowanie najwi(cid:219)kszego wspólnego dzielnika (NWD) dwóch liczb ca(cid:260)kowitych (aby dowiedzie(cid:201) si(cid:219), co to jest, mo(cid:318)na obejrze(cid:201) film dost(cid:219)pny pod adresem https://www.khanacademy.org/math/in-sixth-grade-math/playing- -numbers/highest-common-factor/v/greatest-common-divisor). Ogólnie rzecz bior(cid:199)c, wzory pokazuj(cid:199) zwi(cid:199)zek pomi(cid:219)dzy co najmniej dwiema zmiennymi. Wi(cid:219)kszo(cid:285)(cid:201) osób uwa(cid:318)a wzory za specjalny rodzaj równa(cid:262). (cid:27) Algorytm — sekwencja dzia(cid:260)a(cid:262) zmierzaj(cid:199)cych do rozwi(cid:199)zania problemu. Sekwencja przedstawia unikatow(cid:199) metod(cid:219) podej(cid:285)cia do problemu poprzez dostarczenie konkretnego rozwi(cid:199)zania. Algorytm nie musi reprezentowa(cid:201) poj(cid:219)(cid:201) matematycznych lub logicznych. Algorytmy zaprezentowane w tej ksi(cid:199)(cid:318)ce cz(cid:219)sto nale(cid:318)(cid:199) jednak do tej kategorii, poniewa(cid:318) ludzie przewa(cid:318)nie stosuj(cid:199) algorytmy w taki sposób. Niektóre specjalne wzory, na przyk(cid:260)ad równania kwadratowe, to tak(cid:318)e algorytmy. Aby proces reprezentowa(cid:260) algorytm, musi by(cid:201): (cid:132) Sko(cid:262)czony — algorytm musi prowadzi(cid:201) do rozwi(cid:199)zania problemu. W tej ksi(cid:199)(cid:318)ce omawiamy problemy ze znanymi rozwi(cid:199)zaniami, dzi(cid:219)ki czemu mo(cid:318)emy oceni(cid:201), czy algorytm rozwi(cid:199)zuje problem poprawnie. (cid:132) (cid:284)ci(cid:285)le zdefiniowane — sekwencja kroków musi by(cid:201) precyzyjna i musi przedstawia(cid:201) kroki w sposób zrozumia(cid:260)y. Poniewa(cid:318) w wykorzystanie algorytmu s(cid:199) zaanga(cid:318)owane komputery, musz(cid:199) one by(cid:201) w stanie zrozumie(cid:201) kroki zmierzaj(cid:199)ce do stworzenia u(cid:318)ytecznego algorytmu. (cid:132) Skuteczny — algorytm musi uwzgl(cid:219)dnia(cid:201) wszystkie przypadki problemu, dla którego kto(cid:285) go zdefiniowa(cid:260). Algorytm powinien zawsze rozwi(cid:199)zywa(cid:201) problem, do którego rozwi(cid:199)zania jest przeznaczony. Nawet je(cid:285)li przewidujemy jakie(cid:285) awarie, cz(cid:219)sto(cid:285)(cid:201) awarii powinna by(cid:201) niska. Awarie wyst(cid:219)puje tylko w sytuacjach, które s(cid:199) dopuszczalne dla zamierzonego u(cid:318)ycia algorytmu. W dalszych podrozdzia(cid:251)ach staramy si(cid:243) opisa(cid:289) natur(cid:243) algorytmów z uwzgl(cid:243)dnie- niem powy(cid:363)szych definicji. Celem nie jest zapewnienie precyzyjnej definicji al- gorytmów, ale raczej pomoc w zrozumieniu ich istoty, dzi(cid:243)ki czemu b(cid:243)dziesz w stanie rozwija(cid:289) w(cid:251)asne rozumienie tego, czym s(cid:241) algorytmy i dlaczego s(cid:241) tak wa(cid:363)ne. ROZDZIA(cid:259) 1 Wprowadzenie do algorytmów 29 Poleć książkęKup książkę Zastosowania algorytmów Algorytm zawsze prezentuje sekwencj(cid:243) kroków, cho(cid:289) niekoniecznie wykonuje te kroki w celu rozwi(cid:241)zania matematycznego równania. Zakres algorytmów jest niewiarygodnie du(cid:363)y. Istniej(cid:241) algorytmy, które rozwi(cid:241)zuj(cid:241) problemy w nauce, medycynie, finansach, produkcji przemys(cid:251)owej, a tak(cid:363)e logistyce i komunikacji. Algorytmy zapewniaj(cid:241) wsparcie dla wszystkich aspektów codziennego (cid:363)ycia. Za ka(cid:363)dym razem, gdy sekwencja dzia(cid:251)a(cid:321), które do czego(cid:337) prowadz(cid:241), jest sko(cid:321)czona, dobrze zdefiniowana i skuteczna, mo(cid:363)emy postrzega(cid:289) j(cid:241) jako algorytm. Na przyk(cid:251)ad mo(cid:363)esz przekszta(cid:251)ci(cid:289) w algorytm nawet co(cid:337) tak trywialnego i prostego jak przy- gotowanie tostu. Procedura przygotowywania tostów cz(cid:243)sto pojawia si(cid:243) na lekcjach informatyki. Taki opis mo(cid:363)na znale(cid:361)(cid:289) na stronie http://brianaspinall.com/now-thats- -how-you-make-toast-using-computer-algorithms/. Niestety algorytm zaprezentowany na tej stronie jest wadliwy. Instruktor nigdy nie wyjmuje tostu z opakowania i nigdy nie wk(cid:251)ada go do tostera, w wyniku czego powstaje uszkodzona kromka wci(cid:241)(cid:363) w opakowaniu w niedzia(cid:251)aj(cid:241)cym tosterze (szczegó(cid:251)owe informacje mo(cid:363)na znale(cid:361)(cid:289) na stronie http://blog.johnmuellerbooks. com/2013/03/04/procedures-in-technicalwriting/). Mimo (cid:363)e koncepcja jest popraw- na, to aby algorytm by(cid:251) sko(cid:321)czony i skuteczny, wymaga pewnych drobnych, ale koniecznych zmian. Jednym z najcz(cid:243)stszych zastosowa(cid:321) algorytmów jest rozwi(cid:241)zywanie wzorów. Na przyk(cid:251)ad NWD dwóch liczb ca(cid:251)kowitych mo(cid:363)na obliczy(cid:289) r(cid:243)cznie. W tym celu nale(cid:363)y poda(cid:289) wszystkie dzielniki obu liczb ca(cid:251)kowitych, a nast(cid:243)pnie wybra(cid:289) najwi(cid:243)kszy dzielnik, który jest dla nich wspólny. Na przyk(cid:251)ad NWD(20, 25) wynosi 5, ponie- wa(cid:363) 5 jest najwi(cid:243)ksz(cid:241) liczb(cid:241) b(cid:243)d(cid:241)c(cid:241) dzielnikiem zarówno liczby 20, jak i 25. R(cid:243)czne obliczanie ka(cid:363)dego NWD (co w istocie jest rodzajem algorytmu) to jednak proces czasoch(cid:251)onny i stwarzaj(cid:241)cy okazje do pope(cid:251)nienia b(cid:251)(cid:243)dów. Z tych powo- dów grecki matematyk Euklides (https://pl.wikipedia.org/wiki/Euklides) stworzy(cid:251) algorytm do wykonania tego zadania. Z metod(cid:241) Euklidesa mo(cid:363)na zapozna(cid:289) si(cid:243) na stronie https://www.khanacademy.org/computing/computerscience/cryptography/modari- -thmetic/a/the-euclidean-algorithm. Pojedynczy wzór, który jest prezentacj(cid:241) symboli i liczb u(cid:363)ywanych do wyra(cid:363)enia informacji lub poj(cid:243)(cid:289), mo(cid:363)e mie(cid:289) wiele rozwi(cid:241)za(cid:321). Ka(cid:363)de z nich jest algorytmem. W przypadku NWD innym popularnym algorytmem jest algorytm Lehmera (zobacz https://www.imsc.res.in/~kapil/crypto/notes/node11.html i https://en.wikipedia.org/wiki/ Lehmer 27s_GCD_algorithm). Poniewa(cid:363) ka(cid:363)dy wzór mo(cid:363)na rozwi(cid:241)za(cid:289) na wiele sposobów, cz(cid:243)sto sp(cid:243)dzamy du(cid:363)o czasu, porównuj(cid:241)c algorytmy — aby znale(cid:361)(cid:289) taki algorytm, który najlepiej sprawdza si(cid:243) w okre(cid:337)lonej sytuacji (zobacz porówna- nie algorytmów Euklidesa i Lehmera pod adresem http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.31.693 rep=rep1 type=pdf). Poniewa(cid:363) nasze spo(cid:251)ecze(cid:321)stwo i towarzysz(cid:241)ca mu technologia nabieraj(cid:241) coraz wi(cid:243)kszego tempa, potrzebujemy algorytmów, które potrafi(cid:241) to tempo utrzyma(cid:289). W naszych czasach mo(cid:363)liwe sta(cid:251)y si(cid:243) takie osi(cid:241)gni(cid:243)cia naukowe jak sekwencjo- 30 CZ(cid:218)(cid:284)(cid:200) I Zaczynamy Poleć książkęKup książkę nowanie ludzkiego genomu dzi(cid:243)ki temu, (cid:363)e naukowcy znale(cid:361)li algorytmy dzia- (cid:251)aj(cid:241)ce wystarczaj(cid:241)co szybko, aby wykona(cid:289) to zadanie. Zmierzenie, który algo- rytm jest lepszy w danej sytuacji lub w przeci(cid:243)tnej sytuacji u(cid:363)ytkownika, to na- prawd(cid:243) powa(cid:363)ny problem i temat do dyskusji w(cid:337)ród informatyków. W informatyce ten sam algorytm mo(cid:363)e mie(cid:289) wiele postaci. Na przyk(cid:251)ad algorytm Euklidesa mo(cid:363)na zaprezentowa(cid:289) zarówno w sposób rekurencyjny, jak i iteracyjny, co obja(cid:337)niono na stronie http://cs.stackexchange.com/questions/1447/what-is-most- -efficient-for-gcd. Ogólnie rzecz bior(cid:241)c, algorytmy przedstawiaj(cid:241) metod(cid:243) rozwi(cid:241)zy- wania wzorów. B(cid:251)(cid:243)dem by(cid:251)oby jednak stwierdzenie, (cid:363)e istnieje tylko jeden ak- ceptowalny algorytm dla danego wzoru lub (cid:363)e istnieje tylko jedna akceptowalna posta(cid:289) algorytmu. Wykorzystywanie algorytmów do rozwi(cid:241)zywania ró(cid:363)nego ro- dzaju problemów ma d(cid:251)ug(cid:241) histori(cid:243) — to nie jest co(cid:337), co w(cid:251)a(cid:337)nie si(cid:243) wydarzy(cid:251)o. Nawet je(cid:337)li ograniczysz swoje poszukiwania do informatyki, in(cid:363)ynierii danych, sztucznej inteligencji i innych dziedzin technicznych, znajdziesz wiele rodzajów algorytmów — zbyt wiele jak na jedn(cid:241) ksi(cid:241)(cid:363)k(cid:243). Na przyk(cid:251)ad ksi(cid:241)(cid:363)ka The Art of Com- puter Programming Donalda E. Knutha (Addison-Wesley) ma 3168 stron w czterech tomach (zobacz http://www.amazon.com/exec/obidos/ASIN/0321751043/datacservip0f- 20/) i mimo to nie jest w stanie wyczerpa(cid:289) tematu (autor zamierza(cid:251) napisa(cid:289) wi(cid:243)cej tomów). Oto kilka interesuj(cid:241)cych zastosowa(cid:321) algorytmów: (cid:27) Wyszukiwanie — znajdowanie informacji lub sprawdzanie, czy informacje, które widzimy, s(cid:199) potrzebne, to zadanie o podstawowym znaczeniu. Bez takich mechanizmów nie by(cid:260)oby mo(cid:318)liwe wykonanie wielu zada(cid:262) w trybie online, takich jak na przyk(cid:260)ad znalezienie strony internetowej oferuj(cid:199)cej idealny dzbanek do kawy do Twojego biura. (cid:27) Sortowanie — ustalenie kolejno(cid:285)ci, w jakiej wykorzystujemy informacje, jest bardzo wa(cid:318)ne. Dla wielu osób nat(cid:260)ok informacji to du(cid:318)y problem, a uporz(cid:199)dkowanie ich jest jednym ze sposobów na zmniejszenie nap(cid:260)ywu danych. Prawdopodobnie b(cid:219)d(cid:199)c dzieckiem, nauczy(cid:260)e(cid:285) si(cid:219), (cid:318)e kiedy utrzymywa(cid:260)e(cid:285) porz(cid:199)dek w zabawkach, (cid:260)atwiej by(cid:260)o Ci je znale(cid:316)(cid:201) i pobawi(cid:201) si(cid:219) t(cid:199) zabawk(cid:199), która Ci(cid:219) akurat interesowa(cid:260)a, ni(cid:318) wtedy, gdy zabawki by(cid:260)y porozrzucane po ca(cid:260)ym domu. Wyobra(cid:316) sobie, (cid:318)e wchodzisz do serwisu Amazon i dowiadujesz si(cid:219), (cid:318)e ma sprzeda(cid:318)y ponad tysi(cid:199)c dzbanków do kawy i nie mo(cid:318)esz posortowa(cid:201) ich wed(cid:260)ug ceny lub najbardziej pozytywnej opinii. Co wi(cid:219)cej, wiele z(cid:260)o(cid:318)onych algorytmów wymaga danych w odpowiedniej kolejno(cid:285)ci do niezawodnego dzia(cid:260)ania, dlatego sortowanie jest wa(cid:318)nym wymogiem dla rozwi(cid:199)zania wielu problemów. (cid:27) Przekszta(cid:260)canie — konwersja jednego rodzaju danych na inny rodzaj danych ma kluczowe znaczenie dla ich efektywnego zrozumienia i wykorzystania. Na przyk(cid:260)ad mo(cid:318)esz dobrze rozumie(cid:201) wag(cid:219) w skali brytyjskiej, ale we wszystkich Twoich (cid:316)ród(cid:260)ach jest stosowany system metryczny. Konwersja pomi(cid:219)dzy tymi dwoma systemami pomaga je zrozumie(cid:201). Podobnie szybka transformata Fouriera (FFT) przekszta(cid:260)ca sygna(cid:260)y pomi(cid:219)dzy domen(cid:199) czasu a domen(cid:199) cz(cid:219)stotliwo(cid:285)ci, dzi(cid:219)ki czemu mo(cid:318)liwe staje si(cid:219) dzia(cid:260)anie takich urz(cid:199)dze(cid:262) jak router wi-fi. ROZDZIA(cid:259) 1 Wprowadzenie do algorytmów 31 Poleć książkęKup książkę (cid:27) Szeregowanie — doprowadzenie do sprawiedliwego podzia(cid:260)u zasobów przez wszystkie zainteresowane podmioty to kolejny obszar, w którym algorytmy znacz(cid:199)co ujawniaj(cid:199) swoj(cid:199) obecno(cid:285)(cid:201). Na przyk(cid:260)ad synchronizacja (cid:285)wiate(cid:260) na skrzy(cid:318)owaniach nie sprowadza si(cid:219) ju(cid:318) tylko do odliczania sekund pomi(cid:219)dzy zmianami (cid:285)wiate(cid:260). Nowoczesne urz(cid:199)dzenia uwzgl(cid:219)dniaj(cid:199) wiele czynników, takich jak pora dnia, warunki pogodowe czy nat(cid:219)(cid:318)enie ruchu. Szeregowanie ma jednak wiele postaci. Na przyk(cid:260)ad zastanów si(cid:219), w jaki sposób komputer wykonuje jednocze(cid:285)nie wiele zada(cid:262). Bez algorytmu szeregowania system operacyjny móg(cid:260)by pobra(cid:201) wszystkie dost(cid:219)pne zasoby i uniemo(cid:318)liwi(cid:201) aplikacji wykonanie po(cid:318)ytecznej pracy. (cid:27) Analiza grafów — wybór najkrótszej drogi pomi(cid:219)dzy dwoma punktami znajduje wiele ró(cid:318)nych zastosowa(cid:262). Na przyk(cid:260)ad bez tego konkretnego algorytmu nie mog(cid:260)aby funkcjonowa(cid:201) nawigacja GPS, poniewa(cid:318) nie potrafi(cid:260)aby skierowa(cid:201) Ci(cid:219) po ulicach miasta przy u(cid:318)yciu najkrótszej trasy z punktu A do punktu B. (cid:27) Kryptografia — utrzymywanie bezpiecze(cid:262)stwa danych to nieustanna walka z hakerami stale atakuj(cid:199)cymi (cid:316)ród(cid:260)a danych. Algorytmy umo(cid:318)liwiaj(cid:199) analiz(cid:219) danych, ich transformacj(cid:219) do okre(cid:285)lonej postaci, a nast(cid:219)pnie powrót do postaci pierwotnej. (cid:27) Generowanie liczb pseudolosowych — wyobra(cid:316) sobie, (cid:318)e grasz w gry, które nigdy si(cid:219) nie zmieniaj(cid:199). Przy ka(cid:318)dej rozgrywce zaczynasz w tym samym miejscu i w ten sam sposób wykonujesz te same kroki. Bez mo(cid:318)liwo(cid:285)ci generowania pozornie losowych liczb realizacja wielu komputerowych zada(cid:262) sta(cid:260)aby si(cid:219) niemo(cid:318)liwa. Powy(cid:363)sza lista to bardzo krótki przegl(cid:241)d zastosowa(cid:321) algorytmów. Algorytmów u(cid:363)ywa si(cid:243) do rozwi(cid:241)zywania wielu ró(cid:363)nych zada(cid:321) i na wiele ró(cid:363)nych sposobów. Stale powstaj(cid:241) nowe algorytmy do rozwi(cid:241)zania zarówno istniej(cid:241)cych, jak i no- wych problemów. Najwa(cid:363)niejsz(cid:241) kwesti(cid:241), któr(cid:241) nale(cid:363)y uwzgl(cid:243)dni(cid:289) w pracy z al- gorytmami, jest to, (cid:363)e przy danym wej(cid:337)ciu nale(cid:363)y oczekiwa(cid:289) okre(cid:337)lonego wyj(cid:337)cia. Problemy drugorz(cid:243)dne to ilo(cid:337)(cid:289) zasobów, których algorytm wymaga do wykona- nia swojego zadania, oraz czas potrzebny do jego wykonania. W zale(cid:363)no(cid:337)ci od rodzaju problemu i rodzaju zastosowanego algorytmu mo(cid:363)e by(cid:289) równie(cid:363) ko- nieczne uwzgl(cid:243)dnienie kwestii dok(cid:251)adno(cid:337)ci i spójno(cid:337)ci. Algorytmy s(cid:199) wsz(cid:219)dzie W poprzednim podrozdziale nieprzypadkowo wspomnieli(cid:337)my algorytm przygo- towywania tostów. Z jakiego(cid:337) powodu robienie tostów jest jednym z najpopular- niejszych algorytmów, jakie kiedykolwiek powsta(cid:251)y. Wielu uczniów szkó(cid:251) po- nadgimnazjalnych pisze odpowiedniki algorytmu przygotowywania tostów na d(cid:251)ugo przed tym, zanim rozwi(cid:241)(cid:363)(cid:241) najbardziej podstawowe zadanie z matematyki. Nietrudno sobie wyobrazi(cid:289), jak wiele odmian algorytmu tostowego istnieje i jakie 32 CZ(cid:218)(cid:284)(cid:200) I Zaczynamy Poleć książkęKup książkę s(cid:241) wyniki ka(cid:363)dego z nich. Prawdopodobnie wyniki s(cid:241) ró(cid:363)ne w zale(cid:363)no(cid:337)ci od osoby i poziomu kreatywno(cid:337)ci. Krótko mówi(cid:241)c, algorytmy pojawiaj(cid:241) si(cid:243) w du(cid:363)ej ró(cid:363)- norodno(cid:337)ci, cz(cid:243)sto w nieoczekiwanych miejscach. Algorytmy wykorzystuje si(cid:243) we wszystkich zadaniach wykonywanych na kom- puterach. Niektóre algorytmy s(cid:241) elementami sprz(cid:243)tu komputerowego (s(cid:241) wbu- dowane, dlatego cz(cid:243)sto mówimy o wbudowanych mikroprocesorach). Sam proces uruchamiania komputera obejmuje u(cid:363)ycie algorytmu. Algorytmy s(cid:241) wykorzysty- wane równie(cid:363) w systemach operacyjnych, aplikacjach i ka(cid:363)dym innym oprogra- mowaniu. Nawet u(cid:363)ytkownicy polegaj(cid:241) na algorytmach. Skrypty pomagaj(cid:241) u(cid:363)yt- kownikom wykonywa(cid:289) zadania w okre(cid:337)lony sposób, ale te same kroki mog(cid:241) mie(cid:289) posta(cid:289) pisemnych instrukcji lub tworzy(cid:289) strategi(cid:243) organizacji. Codzienne czynno(cid:337)ci cz(cid:243)sto zmieniaj(cid:241) si(cid:243) w algorytmy. Pomy(cid:337)l o tym, jak sp(cid:243)- dzasz dzie(cid:321). Zazwyczaj, jak wi(cid:243)kszo(cid:337)(cid:289) ludzi, wykonujesz ka(cid:363)dego dnia te same zadania w tej samej kolejno(cid:337)ci. W zwi(cid:241)zku z tym Twój dzie(cid:321) staje si(cid:243) algoryt- mem, który rozwi(cid:241)zuje problem wygodnego (cid:363)ycia przy u(cid:363)yciu mo(cid:363)liwie jak naj- mniejszej ilo(cid:337)ci energii. W ko(cid:321)cu w(cid:251)a(cid:337)nie taki cel spe(cid:251)nia rutyna — czyni nas skutecznymi. Na algorytmach cz(cid:243)sto bazuj(cid:241) procedury awaryjne. Instrukcj(cid:243) post(cid:243)powania w sytuacjach awaryjnych wyjmujesz z kieszeni znajduj(cid:241)cego si(cid:243) przed Tob(cid:241) fotela w samolocie. Ma ona posta(cid:289) serii piktogramów pokazuj(cid:241)cych, jak otworzy(cid:289) drzwi awaryjne i wysun(cid:241)(cid:289) awaryjn(cid:241) zje(cid:363)d(cid:363)alni(cid:243). Niekiedy algorytmy nie zawieraj(cid:241) nawet s(cid:251)ów. Same rysunki ilustruj(cid:241) procedur(cid:243) wymagan(cid:241) do wykonania zadania i roz- wi(cid:241)zania problemu awaryjnego wysiadania z samolotu. W tej ksi(cid:241)(cid:363)ce dla ka(cid:363)dego algorytmu zobaczymy te same trzy elementy: 1. Opisz problem. 2. Utwórz ci(cid:199)g (dobrze zdefiniowanych) kroków prowadz(cid:199)cych do rozwi(cid:199)zania problemu. 3. Wykonaj te kroki, aby uzyska(cid:201) po(cid:318)(cid:199)dany rezultat (sko(cid:262)czony i skuteczny). Stosowanie komputerów do rozwi(cid:199)zywania problemów S(cid:251)owo komputer brzmi do(cid:337)(cid:289) technicznie i mo(cid:363)e by(cid:289) nieco przyt(cid:251)aczaj(cid:241)ce dla nie- których osób. Wspó(cid:251)czesny cz(cid:251)owiek tkwi jednak w komputerach „po uszy” (a by(cid:289) mo(cid:363)e nawet g(cid:251)(cid:243)biej). Przez wi(cid:243)kszo(cid:337)(cid:289) czasu masz przy sobie przynajmniej jeden komputer — Twój smartfon. Je(cid:337)li masz jakie(cid:337) specjalne urz(cid:241)dzenie, na przyk(cid:251)ad rozrusznik serca, ono tak(cid:363)e zawiera komputer. Twój telewizor zawiera co naj- mniej jeden komputer. W komputery s(cid:241) równie(cid:363) wyposa(cid:363)one „inteligentne” urz(cid:241)dzenia AGD. Samochód mo(cid:363)e zawiera(cid:289) nawet 30 komputerów — maj(cid:241) one ROZDZIA(cid:259) 1 Wprowadzenie do algorytmów 33 Poleć książkęKup książkę posta(cid:289) wbudowanych mikroprocesorów steruj(cid:241)cych zu(cid:363)yciem paliwa, emisj(cid:241) spalin, dzia(cid:251)aniem skrzyni biegów i uk(cid:251)adu kierowniczego oraz stabilno(cid:337)ci(cid:241) (zobacz artyku(cid:251) z „New York Timesa” dost(cid:243)pny na stronie http://www.nytimes. com/2010/02/05/technology/05electronics.html) — i wi(cid:243)cej wierszy kodu ni(cid:363) od- rzutowy my(cid:337)liwiec. Pojawiaj(cid:241)ce si(cid:243) na rynku motoryzacyjnym samochody auto- nomiczne b(cid:243)d(cid:241) jeszcze bardziej wymaga(cid:251)y wbudowanych mikroprocesorów i algo- rytmów o jeszcze wi(cid:243)kszej z(cid:251)o(cid:363)ono(cid:337)ci. Komputer s(cid:251)u(cid:363)y do szybkiego rozwi(cid:241)zywania problemów i z mniejszym wysi(cid:251)kiem ni(cid:363) w przypadku rozwi(cid:241)zywania ich r(cid:243)cz- nie. Dlatego nie powinno Ci(cid:243) dziwi(cid:289), (cid:363)e w tej ksi(cid:241)(cid:363)ce jeszcze bardziej wykorzystu- jemy komputery po to, aby lepiej zrozumie(cid:289) algorytmy. Komputery ró(cid:363)ni(cid:241) si(cid:243) na wiele sposobów. Komputer w zegarku jest do(cid:337)(cid:289) ma(cid:251)y — ten, który znajduje si(cid:243) na Twoim biurku, jest stosunkowo du(cid:363)y. Superkompu- tery s(cid:241) ogromne i sk(cid:251)adaj(cid:241) si(cid:243) z wielu mniejszych komputerów — wszystkie one wspó(cid:251)pracuj(cid:241) ze sob(cid:241) podczas rozwi(cid:241)zywania z(cid:251)o(cid:363)onych problemów, takich jak opracowywanie prognozy pogody na jutro. Najbardziej z(cid:251)o(cid:363)one algorytmy bazuj(cid:241) na specjalnych funkcjonalno(cid:337)ciach komputerów. Za ich pomoc(cid:241) uzysku- jemy rozwi(cid:241)zania problemów, do których rozwi(cid:241)zywania te funkcjonalno(cid:337)ci zaprojektowano. To prawda, (cid:363)e mo(cid:363)na zu(cid:363)y(cid:289) mniejsze zasoby, aby wykona(cid:289) zada- nie, ale kosztem uzyskania odpowiedzi po znacznie d(cid:251)u(cid:363)szym czasie lub uzyska- nia odpowiedzi, która nie jest wystarczaj(cid:241)co dok(cid:251)adna, by by(cid:251)a u(cid:363)ytecznym roz- wi(cid:241)zaniem. W niektórych przypadkach na odpowied(cid:361) czekamy tak d(cid:251)ugo, (cid:363)e w momencie jej uzyskania nie jest ona ju(cid:363) wa(cid:363)na. Bior(cid:241)c pod uwag(cid:243)
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy dla bystrzaków
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ą: