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