24.02.2008
WYKLAD 1
Temat: Algorytmizacja zadań
Algorytmika – dziedzina wiedzy zajmująca się badaniem algorytmów
Algorytm – przepis, wykonanie jakiegoś zestawu czynności prowadzących do osiągnięcia oczekiwań; z góry określonego celu.
Przykłady algorytmów:
· Przepis
· Procedury postępowania w organizacjach
· Procedury rozwiązywania poszczególnych rodzajów zadań obliczeniowych
· Procedury prowadzenia badań naukowych
Algorytm – zbiór reguł postępowania które umożliwiają rozwiązywanie określonego zadania w skończonej liczbie w skończonym czasie
Np.:
o przepisy kulinarne
o procedury prowadzenia badań naukowych
o procedury postępowania w organizacjach
o procedury rozwiązywania poszczególnych rodzajów zadań obliczeniowych
Wykonawcą algorytmu może być komputer lub człowiek. Każdy problem który musi być rozwiązany musi być poddany specyfikacji ( dokładny opis zadania)
W ramach specyfikacji podaje się
· Dane
· Warunki
· Wyniki
· Związki wyników z danymi
Specyfikacja problemu
Przykład1
Sformułowanie zadania:
Dany jest ciąg liczb
znaleźć największą
z nich
Algorytm:
Niech max ma wartość równą jednemu elementowi ciągu. Porównaj max z kolejnym elementem ciągu i jeśli spotkasz wartość większą przyjmij ją jako nową wartość max
Etapy rozwiązywania problemu:
· Sformułowanie zadania
· Określenie danych wejściowych
· Określenie celu (wyniku)
· Poszukanie metody rozwiązania czyli algorytmu
· Przedstawienie algorytmu w postaci
* Opis słowny
* Listy kroków
* Schematu blokowego
* Jednego z jerzyków programowania
· Analiza poprawności rozwiązania
· Testowanie rozwiązania dla różnych metod
Sposoby zapisu algorytmu
1. Zapis słowny – pozwala określić kierunek działań i odpowiedzieć na pytania czy zagadnienie jest możliwe do rozwiązania
2. Lista kroków – które należy wykonać w celu rozwiązania problemu
· Sformułowanie zagadnień
· Określenie zbioru danych potrzebnych do rozwiązania zagadnienia
· Określenie przewidywanego wyniku
· Zapis ponumerowanych kroków które należy wykonać aby przejść od punktu początkowego do punktu końcowego
3. Zapis graficzny – schemat blokowy
Rodzaje algorytmów:
· Liniowy:
· Ma postać ciągu kroków, które muszą zostać bezwarunkowo wykonane jeden po drugim
· Nie zawiera żadnych warunków ani rozgałęzień. Zaczyna się od podania zestawu danych a także wykonania kroków do otrzymania wyniku.
Przykład
1. Sformowanie zadania: Oblicz sumę dwóch liczb naturalnych a i b. Wynik oznacz przez s.
2. Dane wejściowe: Dwie liczby a i b
3. Cel obliczeń: Obliczenie sumy S=a+b
4. Dodatkowe ograniczenia: Sprawdzenie warunku dla danych wejściowych np. czy a i b są liczbami naturalnymi.
· Z rozgałęzieniem:
Większość algorytmów zawiera rozgałęzienie będące efektem sprawdzenia warunków. Wyrażanie warunków umożliwiają wykonanie zadania dla wielu wariantów danych i rozważenie różnych przypadków.
1. Sformowanie zadania: Znajdź rozwiązanie równania liniowego w postaci ax+b=0. Wynikiem jest wartość liczbowa lub stwierdzenie dlaczego nie ma jednoznacznego rozwiązania
2. Dane wejściowe: Dwie liczby rzeczywiste a i b należące do R
3. Cel obliczeń: Obliczenie wartości x lub stwierdzenie, że równanie nie ma jednoznacznego rozwiązania.
a= 0 to sprawdź czy b=0 jeśli tak to równanie sprzeczne lub tożsamościowe
a¹ 0 to oblicz x = -b/a
· Z powtórzeniami:
Powtórzenia mają dwojaką postać:
Ø Liczba powtórzeń jest z góry określona ( przed rozpoczęciem cyklu) – najczęściej związana z działaniem na macierzach
Ø Liczba powtórzeń jest niezmienna ( zależy od spełnionego pewnego warunku) – związana z obliczeniami typu iteracyjnego.
Schemat blokowy
Pojęciowy model algorytmu
- jest rozumiany jako odwzorowanie f, którego dla określonego zestawu danych wejściowych We generującego pewien zestaw danych wyjściowych Wy, gdzie liczność zbirów We i Wy mogą być różne
Dane wejściowe We Dane wyjściowe Wy
Graficzny model algorytmu
Pojęcie dziedziny algorytmu
Każdy algorytm działa na zbiorze obiektów wraz z operacjami które można wykonac na nim.
Układ obiektów wraz z operacjami będących podstawą określenia algorytmu który nazywamy dziedziną algorytmu
Przykład dziedzin algorytmicznych
· Dziedzina liczb całkowitych { C, +, -, div( dzielenie bez reszty), mod (dzielenie z resztą) abs ( wartość absolutna) }
· Dziedzina liczb rzeczywistych { R, +, -, *, /, sort( pierwiastek), log, sin, cos, abs}
· Dziedzina algorytmiczna rachunku logicznego { B, not, and, or, =>, <, > , <>, =<, =>}
· Dziedzina algorytmiczna dla języka programowania - zbiór symboli alfanumerycznych oraz reguł syntaktycznych i semantycznych języka programowania.
- algorytm powinien precyzyjnie przedstawiać kolejne kroki postępowania. Do opisu kroków mogą być stosowane następujące : ( dokończyć)
Język programowania – jest to środek umożliwiający zapis algorytmu w postaci zrozumiałej dla człowieka, a także równocześnie przetwarzalnej do postaci zrozumiałej dla komputera
Klasyfikacja algorytmów
Rozważać będziemy następujące algorytmy:
· Algorytmy sekwencyjne – równoległe – kroki algorytmu wykonywane kolejno w sekwencjach
· Numeryczne – wykonywanie obliczeń lub przetwarzanie danych
· Rekurencyjne – itercyjne – algorytm w kolejnych krokach wywołuje sam siebie dla nowych wartości argumentów wykonania lub wykonania obliczeń pętli dla zmieniających się wartości jej zmiennej sterującej
Algorytm sekwencyjny Algorytm równoległy
Własności algorytmów
· Adekwatność – czy algorytm realizuje obliczenia zgodnie z przyjętym celem realizacji zadania
· Własność STOP – zostały zdefiniowane kryteria zatrzymania wykonywania algorytmu w warunkach poprawnego i niepoprawnego … obliczenia
· Jednoznaczność – algorytm zapisany jest w sposób na tyle precyzyjny, że jego wykonanie jest automatyczne realizowanie kolejnych kroków
· Powtarzalność – każde wykonanie algorytmu przebiega według określonych reguł tego samego schematu działań i prowadzi do tej samej …
Metody weryfikacji algorytmu
1. Metoda czarnej skrzynki
- polega na weryfikacji poprawności algorytmu poprzez analizę uzyskanych wyników jego wykonania po zadaniu określonego zestawu danych wejściowych . W tej metodzie nie analizuje się wewnętrznej budowy algorytmu tylko analizuje się go jako zamkniętą całość
Wejście Algorytm Wyjście
Metoda analityczna
2. Metoda białej skrzynki
- polega na śledzeniu poprawności algorytmu od jego wnętrza. Uwzględnia się wtedy wewnętrzną logikę algorytmu. Przykładami zastosowania metody białej skrzynki mogą być
Ø Mapy śledzenia algorytmu – umożliwiają analizę poprawności wykonywania się algorytmu przez analizę wartości zmiennych w poszczególnych krokach jego wykonywania się
Ø Formalna specyfikacja problemów – jest to zapis algorytmu w oparciu o pewną notację formalną
Ø Logika algorytmiczna – badanie poprawności wykonywania się algorytmu przez stwierdzenie poprawności pewnych kroków logicznych.
Rodzaje złożoności obliczeniowej algorytmu
Ø Złożoność zasobowa – pamięciowa – wyrażona w sakli zajętości niezbędnych do realizacji algorytmu
Ø Złożoność czasowa – wyrażana w skali czasu wykonywania algorytmu ( liczba kroków) – złożoność czasowa jest ważniejsza.
Czynniki wpływające na czas wykonywania programu:
Ø Rozmiar danych wejściowych algorytmu
Ø Jakość kodu wynikowego generowanego przez komplikator
Ø Architektura i szybkość komputera na którym program jest wykonywany
Ø Złożoność czasowa wykorzystanego algorytmu
24.02.2009
WYKŁAD 2
Temat: Konstruowanie algorytmów
Tworzenie szczegółowego planu rozwiązywania zadań obliczeniowych z podaniem zbioru elementarnych operacji i kolejności ich realizacji nazywamy procesem konstruowania algorytmu
Metody konstruowania algorytmu
ü Top down – zadany problem dzielimy na logicznie domknięte moduly posługujące się ogólnym opisem ich funkcjonowania. Potem każdą część dzielimy na coraz mniejsze moduły.
...
phyrox100