Algorytmy w perlu

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Algorytmy w Perlu
SPIS TRECI
KATALOG KSI¥¯EK
Autorzy: Jon Orwant, Jarkko Hietaniemi, John Macdonald
T³umaczenie: S³awomir Dzieniszewski, Marcin Jêdrysiak
ISBN: 83-7197-913-4
Tytu³ orygina³
Format: B5, stron: 680
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 objani 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.
Jeli jeste pocz¹tkuj¹cym programist¹, poznasz najwa¿niejsze algorytmy, które pozwol¹
Ci rozwi¹zywaæ problemy programistyczne w sposób profesjonalny. Nawet jeli znasz ju¿
podstawy algorytmiki, bêdziesz zapewne zaskoczony z jak¹ ³atwoci¹ mo¿na je
zastosowaæ w Perlu. W ksi¹¿ce znajdziesz nawet obowi¹zkowy program rysuj¹cy fraktale.
Jest to pierwsza ksi¹¿ka sporód licznych pozycji powiêconych algorytmom, która
demonstruje ich u¿ycie za pomoc¹ Perla.
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.
„Powiêci³em lekturze wiele czasu przeznaczonego na sen — tak ekscytuj¹ca jest ta
ksi¹¿ka”
— Tom Christiansen
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
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
Zap0tlone listy powi!zane ..................................................................................................73
Oczyszczanie pami0ci w Perlu...........................................................................................76
Listy dwustronnie powi!zane ............................................................................................79
Listy niesko4czone ...............................................................................................................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! si0 wkrótce.....................................................................114
  4
Algorytmy w Perlu
Rozdział 4. Sortowanie..................................................................................115
Wprowadzenie do sortowania .........................................................................................115
Wszystkie sorty sortowania..............................................................................................132
Podsumowanie naszych rozwa?a4 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 cz0 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 wielowartociowe..................................................................................................255
Podsumowanie informacji o zbiorach.............................................................................258
Rozdział 7. Macierze......................................................................................259
Tworzenie macierzy...........................................................................................................261
Manipulowanie indywidualnymi elementami macierzy.............................................261
Ustalanie rozmiarów macierzy.........................................................................................262
Wywietlanie macierzy......................................................................................................262
Dodawanie stałej wartoci 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
Wartoci własne i wektory własne ..................................................................................280
Problem mno?enia kilku macierzy..................................................................................283
Dla tych, którzy chcieliby dowiedzie si0 czego wi0cej .............................................286
Spis treci
5
Rozdział 8. Grafy............................................................................................287
Wierzchołki i kraw0dzie....................................................................................................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
Dcie?ki i mosty .....................................................................................................................323
Biologia grafów: drzewa, lasy, skierowane grafy acykliczne, przodkowie i dzieci.......325
Klasy kraw0dzi i grafów.....................................................................................................329
Moduły CPAN dla grafów................................................................................................362
Rozdział 9. Ła&cuchy .....................................................................................363
Narz0dzia wbudowane w Perla.......................................................................................364
Algorytmy poszukuj!ce wzorca w ła4cuchu 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 obj0to........................................................................................................439
Kierunek...............................................................................................................................443
Przeci0cie..............................................................................................................................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łóce4............................................................................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 prawdopodobie4stwa......................................................................................573
Rzut kostk! — rozkład równomierny.............................................................................575
Nieci!głe rozkłady nierównomierne...............................................................................580
Prawdopodobie4stwo warunkowe..................................................................................587
Niesko4czone rozkłady nieci!głe.....................................................................................588
Rozkłady ci!głe...................................................................................................................589
Inne rodzaje rozkładów prawdopodobie4stwa.............................................................590
Rozdział 15. Statystyka...................................................................................595
Parametry statystyczne......................................................................................................596
Testy istotnoci....................................................................................................................604
Korelacja...............................................................................................................................615
Rozdział 16. Analiza numeryczna .................................................................621
Obliczanie pochodnych i całek.........................................................................................622
Rozwi!zywanie równa4....................................................................................................629
Interpolacja, ekstrapolacja i dopasowywanie krzywej.................................................636
Dodatek A Bibliografia.................................................................................643
Dodatek B
Zestaw znaków ASCII .............................................................647
Skorowidz ..........................................................................................................651
[ Pobierz całość w formacie PDF ]