1.DEFINICJE

Algorytm - jest to ciąg kroków obliczeniowych prowadzących do przekształcenia danych wejściowych w wyjściowe.

Etapy Algorytmizacji

1. Sformułowanie zadania.

2. Określenie danych wejściowych.

3. Określenie celu, czyli wyniku.

4. Sformułowanie (jeżeli jest to konieczne) warunków, jakie muszą spełniać dane wejściowe i wynik.

muszą spełniać dane wejściowe i wynik.

5. Poszukiwanie metody rozwiązania, czyli algorytmu.

6. Przedstawienie algorytmu w wybranej postaci.

7. Analiza poprawności rozwiązania.

8. Testowanie rozwiązania dla różnych danych - ocena efektywności przyjętej metody

1.Zadanie

2.Dane wejściowe

3.Określenie celu

4.Warunki danych wejściowych

5.Poszukiwanie metody rozwiązania

6.Przedstawienie algorytmu w wybranej postaci

7.Analiza poprawności rozwiązania

8.Testowanie

Metody Reprezentowania Algorytmów

1.Opis słowny - Tekstowa

2.Schemat blokowy - Graficzna

3.Diagramy N-S - Graficzna

4.Lista kroków - Tekstowa

5.Drzewo algorytmu - Graficzna

6.Pseudokod - Tekstowa

7.Kod źródłowy w wybranym języku programowania - Tekstowa

8.Prezentacja - Graficzna

9.Wzór matematyczny - Tekstowa

Algorytmy - Podstawowe Pojęcia

Algorytm z rozgałęzieniami - algorytm, w którym zawarto przynajmniej

jeden warunek

Algorytm iteracyjny - algorytm, w którym występuje iteracja, czyli

wielokrotne powtarzanie pewnych operacji lub całych fragmentów algorytmu

(kilku kroków)

Algorytm rekurencyjny - algorytm, który na jednym z kroków wykorzystuje

sam siebie jako całość. Innymi słowy - algorytm, który odwołuje się do samego

siebie.

Strategia „dziel i zwyciężaj” - problem, który należy rozwiązać jest tu

rekurencyjnie dzielony na mniejsze podproblemy tego samego lub podobnego

typu dotąd, aż stanie się on wystarczająco łatwy do bezpośredniego

rozwiązania. Następnie rozwiązanie otrzymane dla mniejszych podproblemów

jest scalane, co prowadzi do uzyskania rozwiązania problemu głównego

Analiza Algorytmów

Analiza algorytmu polega na określeniu zasobów, jakie są potrzebne do

jego wykonania. Jako zasoby rozumiemy:

- czas obliczeń

- pamięć

- szerokość kanału komunikacyjnego

- dostępne układy logiczne

Przed przeprowadzeniem analizy musimy wybrać odpowiedni model realizowania obliczeń, uwzględniając zasoby dostępne w wybranej technologii oraz ich koszty.

Przykład: jednoprocesorowa maszyna o dostępie swobodnym do pamięci (Random Access Machine), przy tym algorytmy są realizowane jako programy komputerowe. W modelu tym instrukcje są wykonywane sekwencyjnie. Podczas analizy algorytmu często musimy korzystać z różnych dziedzin matematyki, takich jak kombinatoryka, rachunek prawdopodobieństwa, algebra.

Podczas analizy dowolnego algorytmu najważniejsze są dwa czynniki:

- Rozmiar danych wejściowych - zazwyczaj obejmuje ilość elementów wejściowych lub (rzadziej) ilość pamięci zajmowanej przez te dane.

- Czas działania - dla konkretnych danych wejściowych jest wyrażony liczbą

wykonanych prostych (elementarnych) operacji lub „kroków”. Zakładamy, że

wykonanie każdego i-tego wiersza programu wymaga czasu ci, gdzie ci - pewna stał

Notacje Asymptotyczne

Efektywność algorytmu - można scharketryzować na podstawie rzędu wielkości funkcji, która opisuje czas działania algorytmu. Dzięki temu możemy porównać złożność kilku różnych algorytmów.

- Pomimo tego że możemy niejednokrotnie określić dokładny czas działania algorytmu, to taka dokładnośc jest często niepotrzebna, a przy tym pracochłonna.

- Dla dostatecznie dużych danych wejściowych liczymy jednie rząd wielkości czasu działania algorytmu, czyli asymptotyczną złożoność obliczeniową.

Rodzaje Notacji:

- theta

- omikron - Notacja O szacuje pesymistyczny czas działania algorytm

- omega - Notacja szacuje optymistyczny czas działania algorytmu

Zależność:

W praktyce, szukamy zazwyczaj asymptotycznej granicy dolnej (Omega) i asymptotycznej granicy górnej (O - omikron), aby na ich podstawie wykazać istnienie asymptotycznie dokładnych granic (Theta).

-----------------------------

Struktura Danych

Struktura Danych - Struktura danych - jest to pewien z góry określony sposób uporządkowania danych w pamięci (operacyjnej, zewnętrznej, itd.).Każdy algorytm pracuje z użyciem określonych struktur danych.

Stała - Z góry znana wartość (np: liczbowa, znakowa), zajmująca pewien obszar w pamięci, nie podlegająca (przynajmniej z założenia) zmianom w trakcie realizowania programu.

Zmienna - Pewien obszar pamięci, w którym przechowywane są dane; w tym przypadku wartość przypisana do określonej zmiennej może sie zmieniać podczas działania programu.

Każda stała i każda zmienna musi należeć do określonego typu,dzięki czemu wiadomo, jaki obszar pamięci będzie zajmować.

Typy Danych: Typ danych określa zbiór wartości, do których należy stała, jakie może przyjmować zmienna lub wyrażenie lub które mogą być rezultatem działania operatora bądź funkcji

Tablica - kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy(indeks-ów).

Rekord - Rekord lub struktura to struktura danych składająca się z danych różnych typów powiązanych w całość.

Zbiór - Zbiór jest określany przez wszystkie możliwe podzbiory elementów swego typu podstawowego. (Brak operatora wyboru zamiast tego można wykorzystać operator elementarny - in)

Plik - abstrakcyjny typ danych, brak oraniczenia pod względem wielkości. Dostęp jest sekwencyjny czyli pobranie kolejnej składowej musi być poprzedzone wyborem jej poprzednika (przejście tylko do następnego)

Stos - Do stosu można dodawać nowe elementy albo je z niego usuwać, ale obowiązuje przy tym zasada, że pierwszy elementem odczytywany (usuwanm) jest ten który został zapisany jako ostatni. (Struktura - LIFO - Ostatni dodany, jest pierwszym do wyciagniecia)

Kolejka - Kolejka ma strukture, FIFO - pierwszy dodany, jest pierwszym do wyciągniacia

Lista - Elementy ułożone są w liniowym porządku, lista jedukierunkowa umożliwia przejście tylko do następnego elementu.

Lista (dwukierunkowa) - Lista dwukierunkowa umożliwia przejśćie do następnego i poprzedniego elementu.

Lista cykliczna - następnikiem ostatniego elementu jest pierwszy element, a poprzednikiem pierwszego ostatni. Lista która działa na zasadzie koła.

Drzewo - Drzewo jest powiązane za pomocą gałęzi, korzeń - tylko jeden - wejściowy, liście węzły końcowe bez powiązań. Ma poziomy (korzeń - 1 poziom, Węzły dowiązane do korzenianależą do poziomu drugiego, itd.). Liczbę gałęzi, przez które trzeba przejść w drodze od korzenia dodanego węzła nazywamy długością drogi. Jeżeli stopień drzewa wynosi 2, to mówimy, że jest to drzewo binarne. Jeżeli drzewo ma większy stopień, to nazywamy je drzewem wielokierunkowym. Każdy węzeł (poza korzeniem i liśćmi) posiada dokładnie jednegorodzica (przodka) i przynajmniej jedno dziecko (potomka).

---