|
问题 |
答案 |
Liczba rozwiązań dopuszczalnych w problemie komiwojażera: 开始学习
|
|
|
|
|
|
开始学习
|
|
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.
|
|
|
|
开始学习
|
|
Polega na określeniu zasobów, jakie są potrzebne do wykonania algorytmu
|
|
|
Analiza algorytmów: zasób zasadniczy 开始学习
|
|
|
|
|
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
|
|
|
|
开始学习
|
|
najdłuŜszy czas działania algorytmu dla dowolnych danych wejściowych określonego rozmiaru n
|
|
|
|
开始学习
|
|
aby wyznaczyć najczęściej przyjmujemy, Ŝe wszystkie dane wejściowe są równie prawdopodobne.
|
|
|
