Książka do Algorytmiki Opcje

[sztosz]

Kuleje jeśli chodzi o kwestie wynajdywania odpowiednich algorytmów żeby rozwiązać dany problem, czasem czytam o jakimś algorytm w necie i nie mam pojęcia jak go ugryźć.

Stąd moje pytanie: Czy jest jakaś książka z której dowiem się sprawnie tworzyć algorytmy, na czym to dokładnie polega? Ale tak od podstaw? W ogóle nie wiem czy w dobrym kierunku szukam, ale trochę błądzę po omacku. Nigdy nie kończyłem studiów informatycznych, ani matematycznych, więc mam w głowie tylko strzępki informacji na ten temat z liceum (IMG:style_emoticons/default/winksmiley.jpg)

[thek]

A popatrz sobie na wyjaśnienie moje oraz chłopaków. My nie sprawdzamy czy ma dokładnie tylko 2 dzielniki (IMG:style_emoticons/default/winksmiley.jpg) Bierzemy sobie jakąś liczbę i lecimy w pętlach usuwając jej kolejne wielokrotności (algorytm L0uda) lub sprawdzając czy liczba dzieli się przez tę, która wybraliśmy (algorytm wookieb). Różnica pomiędzy tymi dwoma polega na tym, że w przypadku pierwszego ważne jest to, czy dane są ustawione jako ciąg kolejnych liczb naturalnych. Jeśli tak nie będzie to algorytm jest bezużyteczny. Wystarczy, że liczby będą nieco przemieszane i będzie klops, bo przez to usunąć można liczby pierwsze z wyników. Algorytm drugi na mieszanie jest odporniejszy, ale też nie bez wad. W wyniku przemieszania pokaże nie tylko liczby pierwsze. Największym spowalniaczem kodu drugiego jest ciągłe robienie modulo i jego sprawdzanie. Tymczasem algorytm pierwszy ma to kompletnie gdzieś (IMG:style_emoticons/default/winksmiley.jpg) Po prostu kasuje hurtem bez sprawdzania zawartości. Dlatego jest taki szybki (IMG:style_emoticons/default/smile.gif) Gdyby jednak zaczynał nie od 0 ale 1 lub 2, to trzeba by go zmodyfikować tak jak opisałem w moim poście wyżej: pobrać wartość znajdującą się w elemencie tablicy o danym indeksie i o tyle indeksów przeskakiwać. Algorytm ten ma jeszcze jedną zaletę. Jest bardzo podatny na zrównolegnianie. Od około 21 do północy wymieniałem z wookiemb PW i część z nich poświęciłem na prezentację działania tego algorytmu na 5 procesorach (IMG:style_emoticons/default/winksmiley.jpg) By było to ładnie widoczne zrobiłem niezwykle uproszczony przykład szukania liczb pierwszych od 2 do 25. Hipotetycznie wszystkie liczby dla algorytmu wookiego były znalezione po 15 operacjach, algorytm pierwszy puszczony na 5 prockach zrobiłby to w 11 operacjach. Zapewne na 4 by to zrobił w 11, ale wprowadziłem bardzo wiele uproszczeń, które i tak działały na korzyść algorytmu wookiego (wszystkie operacje niemalże pomijane i tylko kasowanie uwzględniałem), czyli całość operacji sprawdzania, modulo, kasowania była równa temu samemu co samego kasowania, co jest jawnym naciąganiem, gdyż zajmuje to różne ilości czasu procesora, ale nie chciałem utrudniać odbioru idei. Przebiegi czasowe wykonywane jednocześnie dla kilku procesorów to dla wielu abstrakcja i konieczne są uproszczenia.

Co do algorytmów i ich pisania to sie już wypowiedziałem jak sądzę. Trzeba zrozumieć istotę problemu, złapać zależności występujące i układać to w bloczki. Nieraz w trakcie się okazuje, że o czymś zresztą zapomnieliśmy, czegoś nie uwzględniliśmy. Zresztą podczas pisania dowolnej aplikacji szybko się o tym programiści przekonują. Zwłaszcza Ci, którzy siedzą w obiektówce (IMG:style_emoticons/default/smile.gif)