On Dec 22, 12:31 pm, Roman W <b...@g...pl> wrote:
> On Thursday, December 22, 2011 10:58:29 AM UTC, Andrzej Jarzabek wrote:
> > > Problem polega na tym, ze dowolny test robisz dla danych, ktore znasz.
> > > Natomiast jezeli masz logiczny dowod, ze implementacja jest poprawna i
> > > algorytm jest poprawny, to wiesz ze zadziala dla dowolnych danych
> > > akceptowanych przez algorytm.
>
> > O ile dowód jest również poprawny.
>
> Dlatego uwazam, ze trzeba robic i to, i to.

W praktyce dowód poprawności implementacji jest jednak strasznie
kosztowny i łatwo się w nim pomylić. W wielu przypadkach owo "trzeba"
jest na wyrost - jeśli się zrobi porządną implementację i intensywne
testy, to koszta z dodatkowego przeprowadzenia dowodu poprawności tej
implementacji są niewspółmierne do korzyści. Oczywiście być może są
dziedziny, gdzie jest inaczej - ja się tylko odnoszę, do
niekwalifikowanego "trzeba".

do góry

On Thu, 22 Dec 2011 09:24:16 +0100, Pawe? Kierski <n...@p...net>
wrote:

>W dniu 2011-12-21 15:39, Roman W pisze:
>> On Wednesday, December 21, 2011 2:27:31 PM UTC, A. L. wrote:
>>> Echem... Akurat... Metoda Simplex jak wiadomo ma zlozonosc
>>> wykladnicza, a wszystkie testy pokazuja ze wielomianowa. Zeby dostac
>>> naprawde zlozonosc wykladnicza tzreba skonstruowac specjalny prtzyklad
>>> co nastapilo cos w 30 lat po sformulowaniu metody.
>>
>> Dla skonczonej liczby punktow funkcje wykladnicza zawsze da sie dofitowac
wielomianem, wiec takie testy moga byc tylko i wylacznie heurystyczne.
>
>Czyli to, co zaproponowałem wykryje tylko "grube" błędy dla względnie
>prosto testowalnych algorytmów. Jeśli to wystarczy - OK.

Oczywiscie ze nie, bo zlozonosc obliczeniowa jest zaledwie
asymptotyczna. Moze sie wiec okazac ze czas wykonania jakiegos
algorutmu dla rozmiarow danych on 0 do, powiedzmy 1000, rosnei
wykladniczo, a potem rosnie liniowo.

A.L.

do góry