test dla informatyków ;-)

0

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

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?

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0