Algorytm002

Liczba rozwiązań dopuszczalnych w problemie komiwojażera:

(n-1)!/2

Niezmiennik pętli

Mówimy, że zdanie P jest niezmiennikiem pętli, jeżeli po każdym jej przebiegu jest ono prawdziwe. W praktyce niezmiennik pętli traktowany jest jako założenie indukcyjne, na podstawie którego wykazuje się prawdziwość kroku indukcyjnego.

Zdanie a jest równe 5 jest trywialnym niezmiennikiem pętli.

int a=5, b=0; for (int i=0; i<9; ++i) {b++;}

Rzeczy dotyczące niezmiennika pętli, które należy udowodnić: inicjowanie

Jest on prawdziwy przed pierwszą iteracją pętli.

Rzeczy dotyczące niezmiennika pętli, które należy udowodnić: Utrzymanie

Jeśli jest on prawdziwy przed iteracją pętli, to pozostaje prawdziwy przed następną iteracją.

Rzeczy dotyczące niezmiennika pętli, które należy udowodnić: Zakończenie

Kiedy pętla się kończy, z niezmiennika wynika uŜyteczna własność, która pomaga udowodnić poprawność algorytmu.

Analiza algorytmów

Polega na określeniu zasobów, jakie są potrzebne do wykonania algorytmu

Analiza algorytmów: zasób zasadniczy

czas obliczeń

Analiza algorytmów: inne zasoby

pamięć, przepustowość kanału komunikacyjnego, sprzęt komputerowy

Analiza kilku algorytmów dla tego samego problemu

poszukiwanie najefektywniejszego

Analiza algorytmów – założenia: Model obliczeń

maszyna o dostępie swobodnym do pamięci (RAM – Random Access Machine)

Analiza algorytmów – założenia: Rozkazy

wykonywane jeden po drugim (sekwencyjnie)

Analiza algorytmów – założenia: czas

Zakładamy, Ŝe wykonanie kaŜdego rozkazu (arytmetycznego, manipulowania danymi, sterującego) zajmuje stały czas

Przypadek pesymistyczny

najdłuŜszy czas działania algorytmu dla dowolnych danych wejściowych określonego rozmiaru n

Przypadek średni

aby wyznaczyć najczęściej przyjmujemy, Ŝe wszystkie dane wejściowe są równie prawdopodobne.