Dobra książka matematyczna na temat algorytmów [zamknięte]

Jestem frajerem matematycznej elegancji i dyscypliny, a teraz szukam takiej literatury na temat algorytmów i analizy algorytmów. Teraz nie ma dla mnie znaczenia, jakie algorytmy są omawiane, ale bardzo, jak są one prezentowane i traktowane. ”Najbardziej cenię sobie bardzo jasny i precyzyjny język, który definiuje wszystkie używane pojęcia w sposób surowy i abstrakcyjny.

Odkryłem, że klasyczny Wprowadzenie do algorytmów autorstwa Cormena, Leisersona, Rivesta i Steina jest dość schludny, ale nie radzi sobie dobrze z matematyką i jest dość nieformalny z dowodami i definicjami. Wprowadzenie Sipsera do teorii obliczeń wydaje się lepsze pod tym względem, ale nadal nie zapewnia płynnego przejścia od matematyki do algorytmów.

Czy ktoś może coś polecić?

¹: Algorytmy powinny co najmniej ingerować w zarządzanie potrzebnymi danymi przy użyciu klasycznych nietrywialnych abstrakcyjnych struktur danych, takich jak wykresy, tablice, zbiory, listy, drzewa itd. - najlepiej również działających na takich strukturach danych. Nie byłbym zbyt zainteresowany, gdyby kwestia użytkowania i zarządzania strukturami danych została całkowicie zignorowana. Jednak nie dbam o rozwiązywane z nimi problemy.

Hendrik Lenstra napisał w 1992 roku :

Chociaż z ścisłego matematycznego punktu widzenia pożądane jest, aby zdefiniować, co mam na myśli przez algorytm i jego czas działania, nie zrobię tego. Moją główną wymówką jest to, że sam nie znam tych definicji. Co gorsza, nigdy nie widziałem traktowania odpowiedniej teorii, która byłaby precyzyjna, elegancka i wygodna w pracy. Wypełnienie tej widocznej luki w literaturze byłoby godnym pochwały przedsięwzięciem.

Nie wiem, czy od tego czasu poczyniono jakieś postępy, czy też w konsensusie uważa się to za „lukę”. Ale pozostaje faktem, że przynajmniej niektórzy wybitni matematycy byli niezadowoleni z matematycznego rygoru wyprowadzania algorytmów. Być może więc nie istnieje książka o pożądanym poziomie formalizmu PO.

Róg obfitości praktycznych perspektyw, jaki mamy dzięki Knuthowi, Griesowi , Stepanovowi i innym, ma na celu pomóc programistom bardziej niż matematykę, a zatem nieuchronnie nie spełnia rygorystycznych zasad i nie jest zbyt subiektywny.

Niemniej jednak praca Stepanova jest powszechnie uznawana w Dolinie Krzemowej za jedną z najlepszych prób syntezy naukowej.

W Elements of Programming Alexander Stepanov i Paul McJones próbują położyć abstrakcyjne algebraiczne podstawy algorytmów. Książka rozpoczyna się wprawdzie nieco nieformalnymi aksjomatycznymi definicjami bytów, wartości i ich atrybutów, ale na 288 stronach postępuje dedukcyjnie poprzez serię lematów do podstaw Standardowej Biblioteki Szablonów.

Spis treści, przedmowa i przykładowy rozdział na temat przemian i ich orbit można znaleźć tutaj , a wykład wprowadzający tutaj .

Nowsza i zrelaksowana książka Stepanova, od matematyki do programowania ogólnego , jest bardziej ułożona przez mapę drogową historii matematyki, od egipskiego mnożenia przez monoidy, półgrupy i twierdzenie Lagrange'a, ostatecznie opracowując nowoczesne struktury danych z ich iteratorami i algorytmami stosowanymi w STL.

Myślę, że opisywana książka ma nazwę. Jest w siedmiu tomach, z których tylko trzy i połowa została opublikowana. Nazywa się The Art of Computer Programming (TAOCP) i jest napisany przez Donalda Knutha.

Być może jednak czasami opisuje zastosowania. Ale zawsze możesz to pominąć, i wątpię, czy stanowi to znaczną część treści. Nie powinieneś być zbyt rozczarowany matematyką.