Algorytm - ściśle określona procedura obliczeniowa, która dla

poprawnych danych wejściowych „produkuje” właściwe

wyniki.

Algorytm - skończona sekwencja reguł, która aplikuje się na

skończonej liczbie danych, pozwalająca rozwiązywać

określony problem (klasę problemów).

Algorytm - zespół reguł w procesie obliczeniowym (przetwarzania

danych)

Cechy algorytmu

-Określoność (Definiteness),

-Jednoznaczność (Uniqually determined),

-Skończoność (Finiteness),

-Ogólność (Generality),

-Efektywność (Effectiveness).

Algorytmiczne rozwiązywanie problemu

Układ kategorii: koncepcja - środki - realizacja

1. Postawienie problemu:

Definicja problemu,

Sprecyzowanie wymagań dotyczących rozwiązania,

Opis danych wejściowych (Input) i wyników(Output).

2. Budowanie algorytmu:

Koncepcja rozwiązania,

Zapis algorytmu i stopniowe precyzowanie,

Analiza algorytmu.

3. Tworzenie programu:

Wybór języka i struktur danych,

Kompilacja, testowanie.

Specyfikacja algorytmów

Formy specyfikacji algorytmów

Werbalna, opisowa (descriptive),

Schemat blokowy, sieć działań, (flow diagram, flow chart),

Pseudokodowa (pseudocode),

Języki programowania (programming languages).

Konstrukcje algorytmiczne

Elementarne konstrukcje algorytmiczne:

Bezpośrednie następstwo,

Wybór warunkowy,

Iteracja warunkowa,

Iteracja ograniczona.

Elementy analizy algorytmu

Cele analizy algorytmu:

Porównanie różnych algorytmów rozwiązujących te same problemy,

Przewidywanie wydajności w nowym środowisku,

Określenie wartości parametrów.

Aspekty analizy algorytmu:

Złożoność obliczeniowa (czasowa, pamięciowa),

Poprawność (semantyczna, syntaktyczna).

Operacje podstawowe (Basic operations)

Cechy operacji:

1. Proporcjonalność do czasu wykonania programu implementującego algorytm,

2. Proporcjonalność do liczby wszystkich operacji algorytmu,

3. Tego samego rzędu, co całkowita liczba wszystkich operacji algorytmu,

Problem:

Złożoność obliczeniowa algorytmu

Złożoność pesymistyczna (worst-case complexity),

Złożoność optymistyczna (best-case complexity),

Złożoność oczekiwana (average-case complexity).

Poprawność algorytmów

Sposoby dowodzenia:

Metoda empiryczna (testy funkcjonalne),

Formalne dowodzenie poprawności.

Specyfikacja danych wejściowych i wyników - warunki wstępne:

Asercja początkowa (precondition) - dotycząca danych wejściowych,

Asercja końcowa (postcondition) - dotycząca wyników.

Poprawność algorytmów

Wymagana:

1. Własność stopu (halting property) - algorytm zatrzymuje się i wyprowadza wynik (obliczenia nie są przerywane).

2. Poprawność wyniku (data correctness).

Poprawność częściowa (partial corectness) - spełnienie p. 2,

Poprawność całkowita (full corectness) - spełnienie p. 1, 2.

Poprawność algorytmów

Algorytm jest poprawny jeśli:

1. Posiada własność określoności obliczeń względem asercji początkowej.

2. Posiada własność stopu względem asercji początkowej.

3. Dla każdego zestawu danych wejściowych spełniających asercję

początkową obliczenie zakończy się i wyniki spełniają asercję

końcową.

Niezmienniki pętli (Loop invariants).

Niezmiennik pętli: warunki i relacje spełniane przez zmienne i

struktury danych na początku lub końcu każdego przebiegu pętli.

Etapy dowodzenia poprawności:

-Wybór niezmiennika pętli,

-Dowód prawdziwości niezmiennika względem liczby

przebiegów pętli.

Złożoność pamięciowa

 Złożoność pamięciowa oczekiwana (expected space complexity)

 Złożoność pamięciowa najgorszego przypadku (worst case space complexity)

Metody obniżania złożoności pamięciowej:

 Wielokrotne obliczanie wartości,

 Stosowanie struktur rozproszonych,

 Kompresja danych,

 Strategie przydziału pamięci.

Metody projektowania algorytmów

 Strategia „dziel i rządź” (Divide-and-conquer strategy)

 Rekurencja (Recursive approach)

 Programowanie dynamiczne ( Dynamic Programming)

 Metoda przyrostowa (Constructive method)

 Metoda zachłanna (Greedy approach).

---