|
Question |
Answer |
Liczba rozwiązań dopuszczalnych w problemie komiwojażera: start learning
|
|
|
|
|
|
start learning
|
|
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. start learning
|
|
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 start learning
|
|
Jest on prawdziwy przed pierwszą iteracją pętli.
|
|
|
Rzeczy dotyczące niezmiennika pętli, które należy udowodnić: Utrzymanie start learning
|
|
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 start learning
|
|
Kiedy pętla się kończy, z niezmiennika wynika uŜyteczna własność, która pomaga udowodnić poprawność algorytmu.
|
|
|
|
start learning
|
|
Polega na określeniu zasobów, jakie są potrzebne do wykonania algorytmu
|
|
|
Analiza algorytmów: zasób zasadniczy start learning
|
|
|
|
|
Analiza algorytmów: inne zasoby start learning
|
|
pamięć, przepustowość kanału komunikacyjnego, sprzęt komputerowy
|
|
|
Analiza kilku algorytmów dla tego samego problemu start learning
|
|
poszukiwanie najefektywniejszego
|
|
|
Analiza algorytmów – założenia: Model obliczeń start learning
|
|
maszyna o dostępie swobodnym do pamięci (RAM – Random Access Machine)
|
|
|
Analiza algorytmów – założenia: Rozkazy start learning
|
|
wykonywane jeden po drugim (sekwencyjnie)
|
|
|
Analiza algorytmów – założenia: czas start learning
|
|
Zakładamy, Ŝe wykonanie kaŜdego rozkazu (arytmetycznego, manipulowania danymi, sterującego) zajmuje stały czas
|
|
|
|
start learning
|
|
najdłuŜszy czas działania algorytmu dla dowolnych danych wejściowych określonego rozmiaru n
|
|
|
|
start learning
|
|
aby wyznaczyć najczęściej przyjmujemy, Ŝe wszystkie dane wejściowe są równie prawdopodobne.
|
|
|
