Często wchodzę w interakcje z ludźmi, którzy chcą poprosić o algorytm dla problemu obliczeniowego (lub jego złożoności), ale nie wyrażają go w sposób rygorystyczny dla nas (informatyków) do zrozumienia.
Odsyłanie ich do książek takich jak CLRS nie jest pomocne, ponieważ tamtejsze przykłady zwykle mają dość prosty sposób rygorystycznego określania, np. Biorąc pod uwagę listę sąsiadów wykresu i dwa wierzchołki obliczają najkrótszą ścieżkę między tymi wierzchołkami.
Czy jest jakaś dobra książka (lub jakiś inny zasób), w której osoba z minimalną znajomością CS może nauczyć się, jak formułować i określać problemy obliczeniowe w sposób rygorystyczny, zrozumiały dla informatyków?
Najlepiej, aby książka zawierała wiele przykładów rygorystycznego formułowania problemów obliczeniowych z różnych dziedzin i przykładów ze świata rzeczywistego.
Wyjaśnienie
Aby sprecyzować pytanie, załóżmy, że znają podstawową terminologię matematyczną / CS, taką jak zbiory, funkcje, wykresy, listy itp. Na poziomie pierwszego i drugiego roku studiów licencjackich CS (co ma miejsce w przypadku osób, które mam w umysł). Na przykład przeczytali jakiś wprowadzający podręcznik, taki jak Aho i Ullman (chociaż mogli nie do końca go zrozumieć).
- Al Aho i Jeff Ullman, Foundations of Computer Science , 1992.
Odpowiedzi:
dobrym zasobem na ten temat, dość dobrze znanym przez naukowców, ale nie tak powszechnie znanym specjalistom, jest Pisanie matematyczne Donalda E. Knutha, Tracy L. Larrabee i Paula M. Robertsa. jest opublikowana książka, wykłady wideo i zestaw notatek. jest bardziej napisany z perspektywy ludzi próbujących opanować pisanie matematyczne, np. do tworzenia prac, ale wszystkie porady mają duże zastosowanie w przypadku osób świeckich próbujących precyzyjnie formułować problemy. pisanie matematyczne, choć trudne do nauczenia, jest naukowym podejściem do rygorystycznego definiowania / formułowania - a jako szczegóły książki rozwiązuje , np. za pomocą algorytmów lub dowodów, problemy obliczeniowe / algorytmiczne.
Informacje o piśmie matematycznym
Indeks matematyczny pism wykładowych
Pisanie matematyczne Uwagi do klasy CS1193
klasyczny tekst Garey & Johnson, Komputery i nienaruszalność nie opisuje dokładnie, jak precyzyjnie formułować problemy, ale podaje wiele przykładów oraz różnorodne „wzorce” teoretyczne / koncepcyjne / techniczne, podzielone na sekcje podobnych problemów, które mogą być używane jako „elementy składowe” do opisu problemów obliczeniowych / algorytmicznych.
źródło
właśnie natknąłem się na ten miły / schludny, nietypowy, stosunkowo nowy / nieznany ref na swojej stronie głównej autorstwa Emmanuele Violi , prof (T) CS z Northeastern University) najwyraźniej niepublikowany gdzie indziej. 41pp. zaczyna się od bardzo podstawowych pojęć matematycznych, np. implikacji, a następnie przechodzi do zaawansowanych tematów, takich jak twierdzenie Erdősa – Szekeresa i teoria Ramseya .
źródło
Kup książkę Algorytmy i struktury danych od Roberta Lafore.
W tej książce każdy algorytm jest wyjaśniony jako historia, bardzo podobnie jak poezja. Następnie daj tej osobie wersję algorytmu Lafore, a później wersję CLRS.
Być może w ten sposób osoba poczuje, jak przełożyć z opisu intuicyjnego na rygorystyczny.
źródło