Aby odpowiedzieć „jakie problemy można rozwiązać za pomocą komputera”, opracowaliśmy teorię obliczalności. Czy w przypadku problemów, które można obliczać, istnieje teoria, która pozwala odpowiedzieć na pytanie „czy program otrzymuję najprostszy”?
Nie sądzę, aby złożoność obliczeniowa odpowiadała na pytanie. Myślę, że bierze pod uwagę, jak długo potrzebujemy (choć mierzone abstrakcyjnie).
Nie jestem pewien, czy algorytmiczna teoria informacji odpowiada na pytanie. Wydaje się, że teoria mówi o rozmiarze, w którym równoważność minimalnego i najprostszego nie jest dla mnie oczywista (cóż, przynajmniej mnie różnią się).
Myślę, że teoria powinna przynajmniej definiować relację „prosta” lub „prostsza niż”.
Jestem teraz przekonany, że powinienem przyjrzeć się złożoności Kołmogorowa. Chciałbym jednak wyjaśnić, co miałem na myśli, kiedy zadawałem to pytanie.
Kiedy ulepszam program, staram się redukować niepotrzebne połączenia między różnymi częściami programu (być może ponowne dzielenie części, aby było mniej lub słabiej). Ponieważ połączenia są zmniejszone, program wydaje się „prostszy”. Stąd wybór słowa „prosty”, kiedy formułuję pytanie. Jest bardzo prawdopodobne, że rozmiar programu również się zmniejsza, ale jest to dobry efekt uboczny, a nie główny cel. Oczywiście proces poprawy nie może trwać wiecznie. Jest kwestia, którą powinienem zatrzymać. Jeśli tylko rozważając „strukturę” (przepraszam za inną niezdefiniowaną koncepcję) lub „relację”, czy mogę się przekonać, że nic więcej nie można zrobić?
Oto lepszy opis mojego pojęcia złożoności.
Olaf Sporns (2007) Złożoność . Scholarpedia , 2 (10): 1623
Odpowiedzi:
Problem ten jest badany w teorii informacji algorytmicznej. To, co definiujesz, nazywa się złożonością Kołmogorowa-Chaitina.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
I wydaje się, że pojęcie prostoty, którego potrzebujesz, może zostać sformalizowane poprzez pojęcie miary złożoności, które jest sformalizowane przez aksjomaty Bluma.
http://en.wikipedia.org/wiki/Blum_axioms
Wydaje się również, że można uogólnić złożoność Kołmogorowa, biorąc pod uwagę inne miary złożoności. Zobacz odnośnik poniżej. (Artykuł Wikipedii na temat złożoności Kołmogorowa dotyczy tego problemu).
Burgin 1990 - Uogólniona złożoność Kołmogorowa i inne miary podwójnej złożoności Cybernetyka i analiza systemów Tom 26, Numer 4, 481–490
źródło
Odpowiedź na pierwsze pytanie brzmi: tak, istnieje teoria, jest to algorytmiczna teoria informacji i nazywane są programami eleganckimi (autor: Gregory Chaitin).
Na drugie pytanie dotyczące „czy program otrzymuję najprostszy”?
Nie ma odpowiedzi , ponieważ jest to pytanie niemożliwe do obliczenia, nie można udowodnić, że program jest programem eleganckim.
Odpowiedziałem, aby dodać wzmiankę o eleganckich programach .
źródło
Istnieją różne metody decydowania o tym, co jest prostym kodem, a co nie.
Niestety, nie ma automatycznego sposobu, aby to ustalić, na przykład Złożoność Kołmogorowa zawodzi w przypadku funkcji rekurencyjnych, niektóre funkcje rekurencyjne (logiczne głębokie) są proste, ale zrozumienie tego nie jest takie proste.
Z mojego doświadczenia wynika, że nasz zespół pracował w systemie i znaleźliśmy „prostą” procedurę w Oracle (nie więcej niż 50 linii) ... i staraliśmy się to zrozumieć, zajęło 2 miesiące (i kilka spotkań), aby w pełni zrozumieć nie ze względu na złożoność kodu, ale logikę kryjącą się za każdą zmienną.
Myślę, że sposobem na określenie, jak prosty jest kod, jest: „przeczytaj kod i rozważ czas poświęcony na jego zrozumienie”.
Więc „Najprostszy program do rozwiązania problemu?” można podzielić na:
a) prostota kodu (jasny kod), ale jest zbyt subiektywna.
b) nadmierna złożoność funkcji, jeśli mam problem z X, to muszę rozwiązać zadanie DX (Delta X), aby je rozwiązać, gdzie DX musi mieć tendencję do X.
Na przykład, jeśli moim problemem jest (jeden) „obrać jabłko” i muszę to zrobić w PHP (i języku), to
jeśli mam ogromne szczęście i PHP ma funkcję function_peel_apple (), to jest to najprostszy kod w historii X = 1 DX = 1, wystarczy wywołać funkcję i to wszystko!
Przeciwnie, jeśli nie mam tyle szczęścia, ale istnieje funkcja function_peel () i function_get_apple (), to X = 1 (jeden problem) i DX = 2 (dwa zadanie).
Jeśli, w najgorszym przypadku, nie istnieje żadna funkcja, to muszę utworzyć jedną (lub więcej) samodzielnie i dodać kilka zadań przed rozwiązaniem problemu, teraz jest to złożony program.
źródło