Gorąco polecamy wszystkim studentom zaczynającym swoją przygodę z informatyką (także na Politechnice Rzeszowskiej) książkę autorstwa Lekh Raj Vermani i Shalini Vermani pt. An elementary approach to design and analysis of algorithms.
Lekh Raj Vermani jest emerytowanym profesorem matematyki z Kurukshetra University, Kurukshetra. Po przejściu na emeryturę był profesorem i dyrektorem w Jai Prakash Mukand Lal Institute of Technology, Radaur (Yamuna Nagar) oraz Panipat Institute of Engieneering and Technology, Smalkha (Panipat). Pełnił funkcję Commonwealth Post-doctoral Fellowship dla program stypendialnego na University of Exeter w Anglii, a także był gościem/naukowcem/profesorem w: Tata Institute of Fundamental Research w Bombaju; University of Manitoba, Winnipeg, Kanada; Techlov Institute of Mathematics, Moskwa; Uniwersytet Panjab, Chandigarh; Harish-Chandra Research Institute, Allahabad; Indyjski Instytut Statystyczny, Delhi; oraz Himachal Pradesh University, Shimla. Jest członkiem National Academy of Sciences w Indiach. Jest autorem: Lectures in Cohomology of Groups, Elements of Algebraic Coding Theory, An Elementary Approach to Homological Algebra oraz A Course in Discrete Mathematical Structures – opracowanie we współpracy z dr Shalini Vermani. Uzyskał tytuł magistra matematyki i doktorat na Uniwersytcie Kurukshetra.
Shalini Vermani jest profesorem nadzwyczajnym w Apeejay School of Management, New Delhi w Departamencie Informatyki i Zarządzania Operacyjnego. Ma ponad 17 lat doświadczenia w nauczaniu. Zajmuje się bezpieczeństwem informacji i kryptografią. Opublikowała różne artykuły w czasopismach krajowych i międzynarodowych, a także napisała książkę, A Course on Discrete Mathematical Structures, wydaną przez Imperial College Press, Londyn. Dr Vermani recenzowała także różne artykuły do krajowych i międzynarodowych czasopism oraz konferencji.
Rozwój informatyki w latach 60. i 70. XX wieku dla wielu był wielkim szokiem, szczególnie gdy dekada lat 80. popularyzowała komputery jako powszechne urządzenie, z którego w każdym domu mogą korzystać nawet dzieci. W latach 90. było jasne, że nie ma od tej drogi odwrotu i ważne jest nie tylko zapoznanie się z komputerami i korzystanie z nich bez żadnych zahamowań i obaw, ale także podejmowanie odważnych prób bycia zaawansowanym użytkownikiem komputera (na przykład programistą). Jednak komunikacja z tą maszyną wymagała nie tylko wiedzy o jej interfejsach, ale także podstawowych (na początku) umiejętności programowania. Ale programowanie jest tylko etapem pośrednim: potrzebna jest dobra wiedza i umiejętności w zakresie języków programowania i algorytmów.
Kiedy byłem młodym studentem informatyki, moja wiedza na temat algorytmów była bardzo ograniczona. Wynika to głównie z faktu, że ogólnie ten termin nie był powszechnie znany wielu moim nauczycielom w technikum; my (ja i moi koledzy) byliśmy świadomi, że informatyka stworzy naszą przyszłość, ale dostęp do tej zagadkowej wiedzy był bardzo ograniczony. Oczywiście były książki o algorytmach, ale po pierwszym kontakcie większość z nas była przekonana, że są na bardzo wysokim poziomie, co wymagało zaawansowanej wiedzy z matematyki. Prawdopodobnie było to spowodowane faktem, że książki te zostały napisane przez tych, którzy w latach 60. i 70. zrobili wyżej wspomniany znaczący postęp. Nawet podczas studiów na uczelni dla wielu z nas analiza algorytmów i zrozumienie ich działania były bardzo trudne. Mieliśmy kilka cennych książek, ale w większości z nich mogliśmy znaleźć tylko pseudokod algorytmów, ale nie było szczegółowych przykładów pokazujących, jak dokładnie działają. Dlatego wiele razy musieliśmy „odkryć” coś, co w końcu okazało się bardzo proste i oczywiste. Jednak ostatnio wszechobecność Internetu zmieniła tę sytuację i około 15 lat temu wielu młodych ludzi otrzymało możliwość zrozumienia, jak działają algorytmy na bardzo szczegółowym poziomie; krok po kroku spowodowało to, że nawet w szkole podstawowej wielu młodych uczniów ma podstawową wiedzę i umiejętności dotyczące pisania prostych algorytmów. W tym czasie napisano również wiele interesujących i cennych książek na temat algorytmów i ich analizy. Ale nadal istnieje duża potrzeba posiadania książek przedstawiających niektóre ważne tematy (na przykład informatyka) na poziomie podstawowym z podstawowym podejściem. Książka zatytułowana An Elementary Approach to Design and Analysis of Algorytm, napisana przez Lekh Raj Vermani i Shalini Vermani jest interesującą propozycją, która wypełnia w bibliotekach luki w zakresie zwięźle napisanych i przyjaznych studentom książek o podstawach algorytmiki.
Rozważana książka składa się z 19 rozdziałów. Większość z nich ma prawie taką samą budowę: opis tematu, przykłady i ćwiczenia. Jest to bardzo przydatne rozwiązanie, a czytelnik trzyma w ręku książkę, po której można łatwo się poruszać. Oczywiście pierwsze rozdziały zaczynają się od bardzo prostych algorytmów. Na początku (rozdział 1) mamy sortowanie. Można powiedzieć, że jest to tak oczywisty i dobrze znany problem w informatyce, że nie trzeba nic więcej mówić, ale zauważmy, że sortowanie jest nadal jednym z najczęściej rozwiązywanych problemów w systemach komputerowych. Sortowanie jest również bardzo przydatne do wprowadzenia problemu analizy wydajności algorytmów (złożoności). Na podstawie sortowania bardzo łatwo jest wyjaśnić wszystkie niezbędne szczegóły w tym temacie (rozdział 2), wprowadzając notacje matematyczne i wyjaśniając, co dokładnie oznacza wydajność algorytmów. Jednak nie tylko dobrze jest wiedzieć coś o różnych typach algorytmów, ale także wiedzieć, jaką strategię należy wziąć pod uwagę, aby rozwiązać różne problemy. W ten sposób pokazano technikę algorytmów z nawrotami (rozdział 3), podejście dziel i zwyciężaj (rozdział 4), algorytmy zachłanne (rozdział 5) i programowanie dynamiczne (rozdział 6). Ponieważ od wielu lat znamy pojęcie grafów, to wiele problemów obliczeniowych jest reprezentowanych przez zbiory węzłów połączonych krawędziami, dlatego rozdziały 7–11 poświęcone są algorytmom grafowym. Jest to wyszukiwanie w grafie (rozdział 7), drzewa rozpinające (rozdział 8), najkrótsze ścieżki (rozdziały 9 i 10) oraz przepływy w sieci (rozdział 11). Następnie mamy (Rozdział 12) z rozwiązywaniem wielomianów i transformacją Fouriera, dopasowywanie ciągów (Rozdział 13), sieci sortujące (Rozdział 14), a na końcu dość krótko, ale wystarczająco dobrze wyjaśniony problem P vs NP w rozdziale 15. Ten zestaw rozdziałów jest wystarczający, aby pokazać wszystkie podstawy i podstawowe algorytmy, które wydają się niezbędne na początku dla każdego, kto zaczyna swoją przygodę z informatyką. Oczywiste jest, że dzisiaj w informatyce stale szukamy nowych algorytmów, ale dobre zrozumienie nie tylko, jak działają inne algorytmy, ale także, jakie techniki i rozwiązania mogą być wykorzystane do osiągnięcia ostatecznego celu, jest bardzo pomocne.
Książka jest pełna przykładów i szczegółowych wyjaśnień na temat działania różnych algorytmów. W wielu książkach o algorytmach można zauważyć, że nawet jeśli istnieją przykłady, są one zwykle bardzo proste i podane bez wielu ważnych szczegółów; tutaj liczba szczegółów jest imponująca. Oczywiście czasami bardzo dobrze jest (ponownie) odkryć, jak działają rozpatrywane algorytmy (jeśli ktoś na początku jest w stanie zrozumieć ideę prostych analizowanych procedur, wtedy zrozumie znacznie więcej), jednak wiele razy musimy znaleźć tylko informacje o jednej interesującej procedurze. W tej książce autorzy pokazują wiele szczegółów wraz ze wszystkimi niezbędnymi wyjaśnieniami, wymaganymi krokami, podprocedurami i przedstawiają prawie wszystko za pomocą prostych, ale bardzo dobrze dobranych danych liczbowych, wykresów i tabel. We wstępie autorzy napisali, że książka nie jest tak zaawansowana jak wiele innych, a ich celem było przedstawienie materiału na poziomie elementarnym. Należy napisać, że dotrzymują tych obietnic. Oczywiście czytelnicy muszą mieć podstawową wiedzę na temat algebry i teorii grafów.
Polecam tę książkę każdemu, kto chciałby studiować algorytmy, dużo dowiedzieć się o informatyce lub po prostu chciałby pogłębić posiadaną wiedzę. Oczywiście można byłoby omówić wybór innych algorytmów, ale nie jest to tak ważne. Najważniejsze jest to, że podczas czytania tej książki mamy pewność, że od samego początku jesteśmy wprowadzani krok po kroku do fantastycznego świata algorytmów, które są wielkim osiągnięciem ludzkości, nawet jeśli niektóre z nich były znane od stuleci. Ale rozwój informatyki w XX wieku zgromadził je razem i stworzył fantastyczną część nauki zwaną informatyką.
Mam nadzieję, że wkrótce ta książka będzie miała wiele tłumaczeń na różne języki, ponieważ jest tego warta. Książka jest napisana bardzo prostym językiem angielskim i może być zrozumiała nawet dla tych, którzy za bardzo nie znają tego języka. Z technicznego punktu widzenia należy podkreślić, że pomimo faktu, iż książka składa się z wielu przykładów, wzorów matematycznych i twierdzeń, bardzo trudno jest znaleźć pomyłki, błędy lub literówki.
Gratulacje dla autorów!
Z recenzją książki w języku angielskim można zapoznać się na stronie
https://zbmath.org/?q=an%3A06973982
lub czytając załączony plik pdf.
L. R. Vermani; S. Vermani: An elementary approach to design and analysis of algorithms. Primers in Electronics and Computer Science 4. Hackensack, NJ: World Scientific, (2019).
an_elementary_approach_to_design_and_analysis_of_algorithms_-_review.pdf (1.35 MB, pdf)
