Jak rygorystycznie sformułować problem obliczeniowy?

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.

algorithms reference-request books

— Kaveh
źródło

Myślę, że to dobre pytanie, ale nie wiem, czy jest dobra odpowiedź. Czuję, jakby to było pytanie: „Czy istnieje sposób, aby nauczyć kogoś, kto nie jest informatykiem, myśleć jak informatyk?” Odpowiedź brzmi: „tak, uczyń ich informatykami”. To powiedziawszy, niektórzy badacze inżynierii oprogramowania mogli przeprowadzić badania nad takimi rzeczami.

— jmite

Myślę też, że do tego właśnie służą przypadki użycia. Jeśli ktoś nie rozumie, jak właściwie sformułować swój problem, wymień kilka scenariuszy tego, co chciałby, aby dany program zrobił, oraz oczekiwane zachowanie w każdym przypadku. Następnie programista opracowuje specyfikację. To powiedziawszy, jestem osobą teorii, a nie inżynierem, więc jeśli się mylę, możesz mnie poprawić.

— jmite

@jmite, dziękuję za komentarze. Masz rację, że częścią inżynierii oprogramowania jest próba zrozumienia, czego chce klient (myślę, że nazywa to analizą wymagań ). Ale zwykle dotyczy to dużych projektów. Nie mówię o takich projektach, ale o proste pytania, takie jak te, które otrzymujemy na tej stronie, które nie są ściśle określone. Widziałem książki uczące ludzi, jak logicznie wypowiadać wypowiedzi z wieloma przykładami. Mam nadzieję, że istnieje coś podobnego do algorytmów i problemów obliczeniowych.

— Kaveh

To powiedziawszy, jestem zdania, że wymaga pewnego sposobu myślenia, który nie jest łatwo przyswajalny, szczególnie przez dorosłych. Próbowałem nakłonić ludzi do upuszczenia rzeczy technicznych i wyjaśnienia problemu tak prosto, jak to możliwe, w kategoriach przedmiotów codziennego użytku. Problem polega na tym, że zwykle zapominają o jakimś ograniczeniu lub sprawiają, że brzmi to jak operacja, która jest O (N) w ich rzeczywistym systemie to O (1) i tak dalej. Tak więc skończę z czymś bardzo zbliżonym do ścisłej definicji niewłaściwego problemu.

— svinja

w pewnym sensie to, o co się prosi, jest sprzeczne, ponieważ rygorystyczne formułowanie problemów jest dokładnie jedną z kluczowych wyuczonych umiejętności, która oddziela laików od specjalistów / profesjonalistów ...

— vzn

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.

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.

— vzn
źródło

Dzięki vzn, są to dobre zasoby na temat pisania matematyki, ale nie szukam czegoś innego. Problemem nie jest dobre pisanie w matematyce, ale zasoby dla ludzi, aby nauczyć się formułować problemy obliczeniowe na tyle jasno, aby ekspert mógł zrozumieć, czego szuka osoba zadająca pytanie, i pomóc im.

— Kaveh

yw; mówicie, że są to dwie różne rzeczy, a są to słowa / wyrażenia, ale mówię, że są one [pożyczyć zdanie dotyczące inżynierii oprogramowania] „ściśle powiązane”

— wer.

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 .

„Jak myśleć jak profesjonaliści” Emmanuele Violi

— vzn
ź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.

— użytkownik5193682
źródło