Algorytmy_w_Perlu_alperl.pdf

(475 KB) Pobierz
IDZ DO
PRZYK£ADOWY ROZDZIA£
SPIS TRE CI
Algorytmy w Perlu
Autorzy: Jon Orwant, Jarkko Hietaniemi, John Macdonald
T³umaczenie: S³awomir Dzieniszewski, Marcin Jêdrysiak
ISBN: 83-7197-913-4
Tytu³ orygina³u:
Mastering Algorithms with Perl
Format: B5, stron: 680
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Wielu programistów poszukuje ksi¹¿ki, która przedstawi³aby implementacje znanych
algorytmów w Perlu. Niestety w podrêcznikach do tego jêzyka trudno znale æ informacje
na ten temat. Informatycy opracowali wiele technik zwi¹zanych z czêsto spotykanymi
problemami, takimi jak:
• Przybli¿one dopasowywanie tekstów (uwzglêdniaj¹ce literówki)
• Znajdowanie korelacji w zbiorach danych
• Algorytmy zwi¹zane z grami
• Przewidywanie zjawisk (np. obci¹¿enia serwera WWW)
• Dopasowywanie wielomianowe i za pomoc¹ funkcji sklejanych
• Szyfrowanie informacji
Dziêki algorytmom przedstawionym w niniejszej ksi¹¿ce bêdziesz móg³ poradziæ sobie
z tymi problemami u¿ywaj¹c wydajnego i ³atwego do nauczenia siê jêzyka, jakim jest Perl.
Autorzy zak³adaj¹, ¿e opanowa³e ju¿ sk³adniê Perla i znasz jego podstawowe funkcje.
Ksi¹¿ka „Algorytmy w Perlu” przystêpnie obja ni Ci, kiedy u¿ywaæ klasycznych technik
programistycznych i w jakich rodzajach aplikacji znajduj¹ one swoje zastosowanie,
a przede wszystkim poka¿e Ci, jak je implementowaæ w Perlu.
Je li jeste pocz¹tkuj¹cym programist¹, poznasz najwa¿niejsze algorytmy, które pozwol¹
Ci rozwi¹zywaæ problemy programistyczne w sposób profesjonalny. Nawet je li znasz ju¿
podstawy algorytmiki, bêdziesz zapewne zaskoczony z jak¹ ³atwo ci¹ mo¿na je
zastosowaæ w Perlu. W ksi¹¿ce znajdziesz nawet obowi¹zkowy program rysuj¹cy fraktale.
Jest to pierwsza ksi¹¿ka spo ród licznych pozycji po wiêconych algorytmom, która
demonstruje ich u¿ycie za pomoc¹ Perla.
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Autorami s¹ m.in. Jon Orwant, redaktor The Perl Journal i Jarkko Hietaniemi —
zarz¹dzaj¹cy bibliotek¹ modu³ów CPAN. Wszyscy autorzy s¹ sta³ymi wspó³pracownikami
CPAN, st¹d wiele z przytoczonych tu fragmentów kodu mo¿esz znale æ w tej bibliotece.
„Po wiêci³em lekturze wiele czasu przeznaczonego na sen — tak ekscytuj¹ca jest ta
ksi¹¿ka”
— Tom Christiansen
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWO CIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Spis treści
Przedmowa ............................................................................................................7
Rozdział 1.
Wprowadzenie..............................................................................15
Czym jest algorytm?.............................................................................................................15
Efektywność...........................................................................................................................23
Rekurencyjnie powracające problemy w nauce o algorytmach....................................35
Rozdział 2.
Podstawowe struktury danych.................................................39
Standardowe struktury danych Perla................................................................................40
Budowanie naszej własnej struktury danych...................................................................41
Prosty przykład.....................................................................................................................42
Tablice Perla: wiele struktur danych w jednej.................................................................52
Rozdział 3.
Zaawansowane struktury danych............................................61
Listy powiązane ....................................................................................................................62
Zapętlone listy powiązane ..................................................................................................73
Oczyszczanie pamięci w Perlu ...........................................................................................76
Listy dwustronnie powiązane ............................................................................................79
Listy nieskończone ...............................................................................................................85
Koszt trawersowania............................................................................................................86
Drzewa binarne.....................................................................................................................86
Sterty .....................................................................................................................................103
Sterty binarne ......................................................................................................................105
Sterta Janusowa...................................................................................................................112
Moduły CPAN dla stert.....................................................................................................112
Moduły CPAN, które pojawią się wkrótce.....................................................................114
4
Algorytmy w Perlu
Rozdział 4.
Sortowanie..................................................................................115
Wprowadzenie do sortowania .........................................................................................115
Wszystkie sorty sortowania ..............................................................................................132
Podsumowanie naszych rozważań na temat sortowania ............................................164
Rozdział 5.
Wyszukiwanie............................................................................171
Wyszukiwanie w tablicy asocjacyjnej i inne sposoby odszukiwania danych
bez wyszukiwania ..............................................................................................................172
Wyszukiwania przeglądowe.............................................................................................173
Wyszukiwania generujące.................................................................................................191
Rozdział 6.
Zbiory ..........................................................................................219
Diagramy Venna.................................................................................................................220
Tworzenie zbiorów.............................................................................................................221
Suma i część wspólna zbiorów.........................................................................................225
Dwa rodzaje odejmowania zbiorów................................................................................233
Zliczanie elementów zbiorów...........................................................................................238
Wzajemne relacje zbiorów.................................................................................................238
Moduły CPAN związane ze zbiorami.............................................................................243
Zbiory zbiorów....................................................................................................................248
Zbiory wielowartościowe..................................................................................................255
Podsumowanie informacji o zbiorach .............................................................................258
Rozdział 7.
Macierze ......................................................................................259
Tworzenie macierzy ...........................................................................................................261
Manipulowanie indywidualnymi elementami macierzy.............................................261
Ustalanie rozmiarów macierzy.........................................................................................262
Wyświetlanie macierzy......................................................................................................262
Dodawanie stałej wartości lub mnożenie przez stałą...................................................263
Przekształcanie macierzy...................................................................................................269
Mnożenie macierzy.............................................................................................................271
Wydobywanie podmacierzy.............................................................................................273
Łączenie macierzy...............................................................................................................274
Transpozycja macierzy.......................................................................................................275
Wyliczanie wyznacznika macierzy ..................................................................................276
Eliminacja Gaussa ...............................................................................................................277
Wartości własne i wektory własne ..................................................................................280
Problem mnożenia kilku macierzy ..................................................................................283
Dla tych, którzy chcieliby dowiedzieć się czegoś więcej .............................................286
Spis treści
5
Rozdział 8.
Grafy ............................................................................................287
Wierzchołki i krawędzie ....................................................................................................289
Grafy, które można wywieść z innych grafów ..............................................................295
Atrybuty grafu ....................................................................................................................300
Sposoby reprezentowania grafów w komputerach..........................................................301
Trawersowanie grafu .........................................................................................................313
Ścieżki i mosty .....................................................................................................................323
Biologia grafów: drzewa, lasy, skierowane grafy acykliczne, przodkowie i dzieci.......325
Klasy krawędzi i grafów.....................................................................................................329
Moduły CPAN dla grafów ................................................................................................362
Rozdział 9.
Łańcuchy .....................................................................................363
Narzędzia wbudowane w Perla.......................................................................................364
Algorytmy poszukujące wzorca w łańcuchu tekstu.........................................................368
Algorytmy fonetyczne .......................................................................................................398
Odnajdywanie rdzenia wyrazu i problem odmiany wyrazów...................................400
Analiza składniowa............................................................................................................404
Kompresja danych..............................................................................................................422
Rozdział 10.
Algorytmy geometryczne..........................................................435
Odległość..............................................................................................................................436
Pole, obwód i objętość........................................................................................................439
Kierunek...............................................................................................................................443
Przecięcie..............................................................................................................................444
Zawieranie punktów i wielokątów..................................................................................452
Granice..................................................................................................................................458
Najbliższa para punktów ..................................................................................................464
Algorytmy geometryczne — podsumowanie................................................................471
Moduły graficzne CPAN...................................................................................................471
Rozdział 11.
Systemy liczbowe ......................................................................475
Liczby całkowite i rzeczywiste .........................................................................................475
Inne systemy liczbowe.......................................................................................................486
Trygonometria.....................................................................................................................496
Ciągi i szeregi ......................................................................................................................497
Rozdział 12.
Teoria liczb.................................................................................503
Podstawy teorii liczb..........................................................................................................503
Liczby pierwsze ..................................................................................................................508
Nierozwiązane problemy ..................................................................................................525
6
Algorytmy w Perlu
Rozdział 13.
Kryptografia ...............................................................................529
Kwestie prawne ..................................................................................................................530
Autoryzacja użytkowników za pomocą haseł ...............................................................530
Autoryzacja danych — sumy kontrolne i inne metody ...............................................536
Ochrona danych — szyfrowanie......................................................................................540
Ukrywanie danych — steganografia ...............................................................................556
Odsiewanie i wprowadzanie zakłóceń............................................................................558
Zaszyfrowany kod Perla....................................................................................................562
Pozostałe kwestie................................................................................................................564
Rozdział 14.
Prawdopodobieństwo ...............................................................565
Liczby losowe ......................................................................................................................566
Zdarzenia .............................................................................................................................568
Permutacje i kombinacje ....................................................................................................570
Rozkłady prawdopodobieństwa ......................................................................................573
Rzut kostką — rozkład równomierny.............................................................................575
Nieciągłe rozkłady nierównomierne ...............................................................................580
Prawdopodobieństwo warunkowe..................................................................................587
Nieskończone rozkłady nieciągłe.....................................................................................588
Rozkłady ciągłe ...................................................................................................................589
Inne rodzaje rozkładów prawdopodobieństwa.............................................................590
Rozdział 15.
Statystyka...................................................................................595
Parametry statystyczne ......................................................................................................596
Testy istotności....................................................................................................................604
Korelacja...............................................................................................................................615
Rozdział 16.
Analiza numeryczna .................................................................621
Obliczanie pochodnych i całek.........................................................................................622
Rozwiązywanie równań ....................................................................................................629
Interpolacja, ekstrapolacja i dopasowywanie krzywej .................................................636
Dodatek A
Bibliografia.................................................................................643
Dodatek B
Zestaw znaków ASCII .............................................................647
Skorowidz ..........................................................................................................651

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin