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.

— k.stm
źródło

To jest subiektywne; zdefiniuj „dobry”. Ponadto, chociaż nie mamy ścisłej zasady dotyczącej pytań z listy, istnieje ogólna niechęć . Proszę zwrócić uwagę również na tę i tę dyskusję; możesz poprawić swoje pytanie, aby uniknąć opisanych tam problemów. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, może pomożemy Ci na czacie z informatyki ?

— Raphael

Powiązane pytanie .

— Raphael

@Raphael Thanks. Użyłem tylko słowa „dobry” w tytule, w swoim pytaniu określiłem, czego chcę. Chociaż celowo nie podałem zbyt szczegółowych informacji, powinno być przynajmniej jasne, że moim celem jest (jak wskazano) matematyczna elegancja i dyscyplina . Nie sądzę, by ta odpowiedź brzmiała jak lista książek, ponieważ nie powinno być zbyt wielu książek należących do tej kategorii, a nawet jeśli tak, nie wierzę w to „zachowanie czystości ścisłego pytania” struktura odpowiedzi ”dzieje się tutaj na kilku stronach wymiany stosów - ale chyba nie na mój telefon. Nie jestem pewien, czy mogę poprawić to pytanie.

— k.stm

Ponadto nie sądzę, aby „prośba o referencje” była odpowiednia do tego pytania. Przynajmniej nie zgodnie z jego opisem: Nie szukam dokumentów ani nie jestem zainteresowany konkretnym i wąskim zagadnieniem. W rzeczywistości jestem dość otwarty na to, jakie treści są objęte, patrz moje drugie zdanie. Czy mogę ponownie usunąć tag? Może mógłbym i powinien zawęzić się z jakim algorytmem byłbym zadowolony?

— k.stm

Być może powinieneś rozważyć semantykę denotacyjną i weryfikację programu.

— Yuval Filmus

Odpowiedzi:

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.

?!? „obecnie nie ma precyzyjnego, eleganckiego i wygodnego matematycznego wyprowadzenia pojęcia algorytmu ...” co powiesz na maszynę Turinga!

— vzn

Lenstra zajmuje się maszynami Turinga w powiązanym dokumencie, ale myślę, że pomysł polega na tym, że nie zapewniają one pełnej analizy algebraicznej. Cytat jest dosłownie dosłowny, w tym część „luki”, jeśli chcesz go przeczytać sam. Zedytuję post, aby usunąć sugerowany „konsensus”, na wypadek gdyby można go było uznać za dyskusyjny.

ofc am / wiedziałem, że

— cytujesz Lenstrę,

sądzę, że maszyn Turinga nie da się wyprowadzić , wręcz przeciwnie, tworzą one aksjomat systemu obliczeniowego (m.in. teza Churcha-Turinga ). cała analiza Lenstrasa i CS w ogólności wywodzą się z aksjomatu istnienia TM.

— vzn

@ Rafael, jeśli mama mówi, że prawidłowe sprzątanie mojego pokoju byłoby „godnym pochwały przedsięwzięciem”, jej mowę brzmi „nie zawracaj sobie głowy sprzątaniem pokoju”. Czy źle cię rozumiem, czy też mnie nie rozumiesz?

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ą.

— Babou
źródło

Obawiałem się, że ta odpowiedź może się pojawić. Spojrzałem na to i to mi nie pasowało. „Nie powinieneś być zbyt rozczarowany matematyką”. - może, ale Knuth też nie wydaje się definiować rzeczy, ale raczej wprowadza je nieformalnie, wyjaśniając. Wspaniale jest przejść przez ten pomysł, a nie tego, czego oczekuję od matematyki.

— k.stm

Może mógłbyś pomóc w tej dziedzinie, publikując matematycznie zaciemnioną wersję jego pracy. Ale jeśli interesuje Cię „płynne przejście od matematyki do algorytmów”, lepszym tematem może być teoria typów. Związek między matematyką a algorytmami jest nadal tematem badawczym.

— babou

PS Jeśli „obawiałeś się, że ta odpowiedź może się pojawić”, powinieneś to powiedzieć w swoim pytaniu, ponieważ jest to jedna z głównych książek źródłowych. Pełne i udokumentowane pytania dają lepsze odpowiedzi.

— babou

Przyszło do mnie dopiero po zadaniu pytania, kiedy nie było mnie przy komputerze. Moje uwagi na temat książki Knutha nie powinny być podejmowane w sposób pejoratywny (tak myślę, że wzięliście to za komentarz do „publikowania matematycznie zaciemnionej wersji”) - prawdopodobnie byłoby to podobne do bluźnierstwa. Jego sposób po prostu nie jest tym, czego szukam. Może po prostu nie ma czegoś takiego, co sobie wyobrażam…

— k.stm

@ k.stm Cóż, zapomnij o zaciemnieniu, które samo w sobie jest całym tematem. Chodzi o to, że uważam, że algorytmika nie jest (jeszcze?) Matematyką. Możliwe, że można uzyskać formalizacje, ale prawdopodobnie są to proste kodowania, które tracą treść, z niewielką korzyścią. To zależy od tematu. Prawdopodobnie jest to o wiele mniej prawdziwe w przypadku teorii automatów, która ma znaczną algorytmię. Chodzi o to, że odpowiednie rozpoznanie abstrakcyjnej matematycznej natury struktur nie jest oczywiste. Jest to kwestia zrozumienia, a nie formalizacji, i zajmuje to lata. Pomyśl o tym jak o fizyce

— babou