- udowodnic poprawnosc algorytmu przy pomocy metody niezmiennikow
Kod:
wynik=1+2+3+4....+n
begin
s=0, i=0
while\ i<n do
{i=i+1;s=s+i}
end
prosze o wytlumaczenie i pomoc!
0
1
Powiem Ci jaki jest ogólny schemat, sesja trwa ;) i nie mam czasu Ci tego rozpisać - ale Twoj przyklad jest latwy:
Niezmiennikiem tutaj będzie coś takiego:
s = (1 + 2 + ... + i) and i < n + 1
Dzięki temu, na końcu będziesz mógł napisać:
s = (1 + 2 + ... + i) and i >= n and i < n + 1
Stąd wniosek, że i = n, a tym samym s = 1 + ... + n
To co zostawiam Tobie to przepchanie przez obie instrukcje pętli tego niezmiennika. Zauważ, że przed pętlą ten niezmiennik jest spełniony - to jest element tej idei:
niezmiennik przed pętlą zachodzi, po pętli niezmiennik wraz z negacją warunku pętli daje to czego chcemy. Zostało Ci pokazać, że niezmiennik pod koniec pętli także jest prawdziwy = przepchaj niezmiennik przez obie instrukcję i zobacz, że jest nadal prawdziwy. Hint: przepychaj od końca, pamiętaj że tam siedzą implikacje.
0
naprawde dzieki za dobre checi i zaczynam juz to powoli rozumiec ale nie rozumiem o co chodzi z tym ,,przepchaniem" :D baaaardzo bym prosil jakbys podal mi po prostu taka odpowiedz jaka ty dalbys na to zadanie a ja juz sobie powolutku dojde jak do tego doszlo :)
0
Ale w zasadzie o co pytasz? O gotowca do twojej pracy domowej? Zapomnij.
Sama idea metody niezmienników jest dość intuicyjna i prosta:
- ustalasz pewną własność która nie ulega zmianie w kolejnych obrotach pętli algorytmu
- pokazujesz ze w związku z tym po n obrotach pętli algorytm da odpowiedź
Założmy że masz na tablicy n kółek i n+1 krzyżyków. Jeśli usuwasz jednocześnie jedno kółko i jeden krzyżyk to co zostanie na tablicy?
Bardziej formalnie: niezmiennikiem jest różnica w liczbie kółek i krzyżyków na tablicy. Jeśli w trakcie algorytmu usuwamy zawsze po jednym z każdego rodzaju to widać że różnica pomiędzy liczbą jednych i drugich pozostaje niezmieniona. Nie trudno zauważyć że po n rundach na tablicy nie zostanie już żadne kółko ale zostanie jeden krzyżyk, więc algorytm faktycznie poprawnie znajdzie symbol którego jest więcej.
Załóżmy że sortujemy tablicę n-elementów metodą wybierania (selection sort).
Niezmiennikiem jest własność, że po i-tej rundzie algorytmu wszystkie elementy na indeksach <0..i) są posortowane.
Widać jasno, ze po pierwszej rundzie najmniejszy element trafi na pierwsze miejsce w tablicy, czyli liczby na indeksach <0,1) są posortowane.
Widać, ze w każdej kolejnej rundzie dochodzi jedna liczba do zbioru posortowanych elementów, więc własność niezmiennika jest zachowana.
Z tego możemy wyciągnąć wniosek że po n rundach liczby na indeksach <0,n) będą posortowane, czyli cała tablica będzie posortowana, więc udowodniliśmy że algorytm działa poprawnie.
W twoim przypadku mozesz przyjąć niezmiennik taki, że po i-tej rundzie licznik suma zawiera sumę liczb <1,i>.
Widać że po pierwszej rundzie licznik zawiera 1, widać też że w każdej kolejnej rundzie do sumy dodawane jest i, więc niezmiennik jest zachowany.
Z tego mozemy wyciągnąć wniosek że po n rundach algorymu licznik suma będzie zawierał sumę liczb <1,n>, więc algorytm działa poprawnie.
0
bardzo dziekuje za pomoc, rozumiem juz o co chodzi w metodzie niezmiennikow ale chodzi mi o to jak sie daje odpowiedz na takie zadanie, Nie, to nie jest moja praca domowa tylko bede miec podobne rzeczy na sesji ;/ odpowiedzia mogloby byc to co napisal pan na koncu czyli ,,W twoim przypadku mozesz przyjąć niezmiennik taki, że po i-tej rundzie licznik suma zawiera sumę liczb <1,i>.
Widać że po pierwszej rundzie licznik zawiera 1, widać też że w każdej kolejnej rundzie do sumy dodawane jest i, więc niezmiennik jest zachowany.
Z tego mozemy wyciągnąć wniosek że po n rundach algorymu licznik suma będzie zawierał sumę liczb <1,n>, więc algorytm działa poprawnie.
"?
0
To zależy od wymagań prowadzącego. Moze wymagać bardziej ścisłego opisu matematycznego a nie takiego słowno-muzycznego ;] Pomyśl sobie o tym dowodzie jak o dowodzie na bazie indukcji matematycznej, bo to jest dość podobna konstrukcja.
0
kolego naprawde nie moglbys zrobic mi tego zadania?? przepraszam za moja ignorancje ale to naprawde bardzo by mi to pomoglo poniewaz widzialbym jak ma wygladac odpowiedz na to zadanie i mysle ze wtedy poradzilbym sobie z innymi
0
Tu masz przykłady z rozwiązaniami :)
https://www.cs.cmu.edu/~aldrich/courses/654-sp07/slides/7-hoare.pdf
Ja się z tego uczyłem kiedys.
0
miejcie mnie za glupiego i w ogole ale nie rozumiem tego z tych przykladow co tam sa poniewaz po prostu sa bardziej skomplikowane, nie moglibyscie naprawde zrobic mi tego zadania ;/? przysiegam to nie jest moja praca domowa
0
500zl i zrobie
0
zajebiscie...
0
Wiesz zaczyna się sesja i nikomu się nie chce tworzyć precedensu odwalania prac domowych bo forum zostanie pogrzebane :/
0
to nie jest moja praca domowa, chce to po prostu umiec, jesli ktos bylby tak mily i zyczliwy niech zrobi mi to nawet na kompletnie innych liczbach lub na innym prostym algorytmie bym tylko zobaczyl jaki jest schemat dawania odpowiedzi na takie zadanie
0
no ale jakies powiazania maja i na pewno bym cos z tego wyciagnal...
0
Paradoksalnie, schemat jest. Schemat to są regułki dla konkretnych instrukcji (mam na myśli tą "poziomą kreskę"). Jednak bez zobaczeni kilku przykładów te regułki wydają się oddarte od tego wszystkiego, w rzeczywistości z czasem zobaczysz, że one są schematem :D
W tych materiałach, które Ci podałem jest chyba dokładnie Twój przykład - a jeśli tam nie ma, to jest wszędzie w googlach. Jeśli nie rozumiesz tego z googli - to nie jest nic dziwnego. Ale w tej sytuacji musiałbym bym Ci krok po kroku wszystko rozpisać, sam mam sesję.
Oczywiście, że powiązania mają, a właściwie to potrzeby studenckie = wszystko robi się tak samo. Jedyny moment, w którym musisz odejść od schematu to wymyślenie niezmiennika, dalej przepychanie jest już schematyczne (rób to od tyłu najlepiej).
Przepychanie oznacza zobaczenie ( a tak na prawdę przekonanie się) co się dzieje z niezmiennikiem w pętli. Przepychasz przez każą instrukcję, w momencie przepychania patrz na regułki, żeby było Ci łatwiej. Efektem przepchnięcia niezmiennika przez pętle będzie dowód, że formuła którą śmiało nazwałeś niezmiennikiem pętli na prawdę nim jest.
Dla łatwości: spróbuj udowodnić jakiś prostszy niezmiennik: np że suma nigdy nie spada poniżej zera.
Tutaj masz na stronie 2 regułki:
https://www.mimuw.edu.pl/~urzy/Semantyka/hoare.pdf