no więc weźmy sobie dowolne dwie funkcje napisane np. w C++,..., często zdarza się że chcemy sprawdzić czy dwie takie funkcje są sobie równe - zwracają te same wartości dla tych samych argumentów... a może ważniejsze jest rozszerzenie tego na wyrażenia. Stąd pytanie ;)
kiedy ważne? trywialnie-chociażby przy sprawdzaniu czy program jest poprawny, przy porównywaniu wzorców itd.
0
0
Masz 2 funkcje "kompiluj". Argumentami są źródła programów w postaci tekstu. Wynikiem są pliki exe.
Wejście - zbiór nieskończony
Wyjście - zbiór nieskończony
W sposób banalny - dla każdego elementu z wejścia sprawdź czy jest takie samo wyjście, nie masz możliwości sprawdzić.
W sposób zaawansowany - porównaj kody źródłowe funkcji - byłoby problemem typu automatyczne dowodzenie twierdzeń. Wymagałoby inteligencji od programu testowego. Rozumienia znaczenia poszczególnych instrukcji. Gdybyśmy mieli coś takiego, to byłoby tylko o krok od automatycznej idealnej optymalizacji kodu, dowodzenia poprawności itp.
Przykro mi, nie da się.
0
poszczególne instrukcje to rozumie sam kompilator... nie? poza tym czy to nie dziwne że skoro mamy taki konkretny algorytmiczny problem to nie istnieje algorytm który go będzie rozwiązywał? choćby miał rozwiązywać n-lat ?
//troche podpuszczam :P
0
gaborek napisał(a)
poszczególne instrukcje to rozumie sam kompilator... nie?
Nie. Kompilator nie rozumie instrukcji. On tylko wie co przekształcić na co.
poza tym czy to nie dziwne że skoro mamy taki konkretny algorytmiczny problem to nie istnieje algorytm który go będzie rozwiązywał? choćby miał rozwiązywać n-lat ?
//troche podpuszczam :P
Istnieje wiele konkretnych problemów i niektóre z nich są nierozwiązywalne (co zostało dowiedzione).
0
tak z czystej ciekawości:
np?
Nie pytam o te które nie są jeszcze udowodnione/rozwiązane ale o te które już wiemy, że po prostu nie da ich się rozwiązać.
0
Grzybu napisał(a)
tak z czystej ciekawości:
np?
Nie pytam o te które nie są jeszcze udowodnione/rozwiązane ale o te które już wiemy, że po prostu nie da ich się rozwiązać.
O ile wiem to problem stopu jest na pewno nierozwiazywalny.
0
Grzybu napisał(a)
tak z czystej ciekawości:
np?
Nie pytam o te które nie są jeszcze udowodnione/rozwiązane ale o te które już wiemy, że po prostu nie da ich się rozwiązać.
Np. kochany problem Kapustki (nad którym spędziłem sporo czasu kombinując by rozwiązać): problem odpowiedniości Posta.
0
Grzybu napisał(a)
tak z czystej ciekawości:
np?
wlasciwie sobie sam odpowiedziales ;). Problemy np-zupelne, przykladowo wyznaczanie najkrotszych sciezek miedzy n miastami dla sporych n (powiedzmy 10^6, czy tam do 10). Jezeli rozwiazanie problemu z wykorzystaniem najnowszych zdobyczy techniki i algorytmiki trwalo by czas porownywalny z czasem trwania wszechswiata, to mozna taki problem uznac za nierozwiazywalny :)
a miedzy 5 latami, a 5000 lat jest tylko 1000x roznicy - przy zlozonosciach rzedu n!, to naprawde niewiele ;)
ALE podobno procesory kwantowe z rownoleglym rozwiazywaniem jednego problemu maja klasc na lopadki problemy np-zupelne i tez podobno cale szyfrowanie oparte na algorytmach matematycznych tez ma pasc... podobno... na razie, to maja problem z dodaniem czwartego bitu do takiego proca, a gdzie patrzec za 64 :D
a co do sprawy porownywania - zostaja jeszcze heurezy, ktore czesto wystarczaja (w przypadku funkcji matematycznych)
0
NP to pikuś... brakuje wielomianowych algorytmów, a nie algorytmów <ort>w ogóle</ort> i większość z nas wykładniczy algorytm do czegoś takiego napisze :P ... jednak są problemy których nie da się rozwiązać i warto o tym wiedzieć i nie marnować na nie czasu(jak ten którego dotyczy ankieta). Przynajmniej ja sobie nie wyobrażam zastosowań w których moglibyśmy się zadowolić tym że to co zwróci algorytm(o ile się zakończy) jest albo poprawne albo nie :D
0
dzielenie przez zero?
0
Kooba napisał(a)
dzielenie przez zero?
Dzielenie przez zero to nie algorytm, tylko blad logiczny ;) Jest niemozliwe z definicji dzielenia.
0
Wiem, to przekłamanie, ale do dziś pamiętam tekst przy liczeniu granic:
zwróć uwagę na znak przy zerze, bo dzielenie przez ujemne zero odwróci ci znak przy nieskończoności
;)
żeby OT nie było: problem nierozwiązywalne to np:
- problem odpowiedniości Posta
- albo z fizyki: nawet klasyczny układ trzech cząstek jest nierozwiązywalny analitycznie. Można robić tylko jakieś tam przybliżenia.
0
Zawsze można napisać algorytm na kwadraturę koła :>
0
hmmm... no właśnie czasem fajnie że algorytm istnieje nawet w czasie wykładniczym... bo jest co aproksymować-choćby słynny problem pokrycia zbioru. ale algorytmy dla niektórych problemów po prostu nie istinieją, a także twierdzenia pewne są,których nie można udowodnić. 40 lat temu ludzi to bulwersowało, a jak jest z wami? :P
0
Jak pierwszy raz przeczytałem o tym, że
twierdzenia pewne są,których nie można udowodnić
a i obalić się nie da (w związku z twierdzeniem Godla o tym czytałem), to byłem w ciężkim szoku. Trochę mi się światopogląd przetasował. Bo gdzie jak gdzie, ale żeby w matematyce (w dodatku w logice formalnej) coś takiego było, to mi się w głowie nie mogło pomieścić.
Z algorytmami tak nie było. Pierwsze spotkania z algorytmami budziły raczej we mnie zdziwienie z serii: "to do tego DA SIĘ napisać algorytm?!". Więc jak natrafiłem na jakiś problem, dla którego NIE dało się, to nie byłem zaskoczony, wręcz przeciwnie ;)
0
Problem, dla którego nie istnieje maszyna Turinga pozwalająca go rozwiązać istnieje i mozna to udowodnić:
-
Każdy algorytm jest równoważny funkcji akceptującej jakiś język. Język składa się z listy słów (może być nieskonczona). Algorytm akceptuje język, jeśli akceptuje wszystkie słowa dozwolone w tym języku. Słowo może być np. zapisaną definicją problemu + rozwiązanie problemu. Słowa, w których rozwiązanie jest nieprawidłowe, algorytm ma odrzucać, pozostałe ma akceptować.
-
Konstruujemy macierz:
MT1 MT2 MT3 .....
W1 1 0 1
W2 0 0 1
W3 ...
W4 ...
MT1, MT2, ... - lista wszystkich mozliwych maszyn Turinga
W1, W2, ... - lista wszystkich możliwych słów
0 - MT nie akceptuje słowa
1 - MT akceptuje słowo
- Weźmy język, do którego należą wszystkie słowa, które na przekątnej macierzy z punktu 2. posiadają wartość 0. Odpowiednia MT dla takiego języka nie istnieje. Gdyby istniała, to dla tych słów w odpowiedniej kolumnie musiałyby być jedynki. W tym również jedynka na przekątnej, co jest sprzeczne z założeniem, co kończy dowód.
Kurcze, edycja postów nie działa :(
Wyskakuje "Błąd programu - przekazano nieprawidłowe parametry"
Chciałem dodać, że mnie kiedyś bardzo zaskoczyło, że istnieje algorytm liczenia mediany o złożoności pesymistycznej O(n).
//ale szybka działa. Ktoś coś skopał znowu - n
// scaliłem posty - Q
0
Zwykle bardzo ładnie dzieli się przez zero, mówię to na podstawie zbiorów zadań z pewnej gałęzi matematyki (ort! de L'Hospitala).
Twierdzenie Gödla, o tak, zaskakujące, zadziwiające nawet.
Nie dotyczy tylko matematyki. Chociaż dla mnie to zbyt odległe
Bardziej poruszyły mnie badania chaosu.
A teraz mamy jeszcze rewolucję kwantową.
Aż strach się bać co nas jeszcze czeka.
0
prawde mówiąc nie wiele wiem o maszynie turinga... i troche się boje czy na pewno jest tych maszyn tylko przeliczalnie wiele. Koncepcja będzie na pewno słuszna jeśli rozpatrzymy zamiast tego wszystkie algorytmy, które można zapisać na kartce :D
//edit... po prostu miałem nieprecyzyjną definicje, jednak MT jest pod każdym względem skończona więc wszystko gra.
0
Każdą maszynę Turinga można zapisać (zakodowac) na kartce papieru, tak jak każdy agorytm. Obecne komputery są równoważne maszynom Turinga. MT są przeliczalne.
0
W tej ankiecie brakuje wariantu: "Na chwilę obecną nie mamy możliwości". Do niedawna atom był niepodzielny a teoria kwarków była teorią.