Złożoność obliczeniowa -algorytmiczna

Czynniki które mają wpływ na funkcjonowanie procedur gospodarczych

Rozróżniamy dwa rodzaje systemów systemy sztuczne i naturalne. Systemy naturalne to takie systemy które zostały stworzone naturalnie przez naturę natomiast systemy sztuczne są to systemy stworzone przez człowieka.

Czynniki mające wpływ na funkcjonowanie procesów gospodarczych (systemu sztucznego)

• cel, zakres oraz środki realizacji procesu

• decydenci

• wejścia procesów

• procedury przetwórcze

• uwarunkowania wewnętrzne

• uwarunkowania, wpływ otoczenia

Na każdy proces gospodarczy oddziaływają różnego rodzaju oddziaływania które zazwyczaj są losowe o charakterze.........

Algorytmizacja od słowa algorytm jest podstawą do automatyzacji oraz informatyzacji wszelkiego rodzajów procesów w obiekcie gospodarczym. Podstawowym algorytmizacji jest:

Algorytm- jest to zbiór określonych reguł postępowania które realizowane zgodnie z ustalonym porządkiem umożliwiają rozwiązanie określonego zadania.

Cechy algorytmu:

• liczba operacji w algorytmie powinna być skończona

• każda operacji musi być zrozumiała i wykonana dla realizatora algorytmu (człowiek - maszyna - komputer)

• istotna kolejność operacji

Podstawowe typy algorytmów za pomocą których systemy informatyczne realizują swoje zadania

• sterowanie dialogiem użytkownika z systemem

• wprowadzanie danych

• aktualizacja danych

• sortowanie danych

• archiwizacja danych

• wyszukiwanie i wyprowadzanie informacji

Sterowanie dialogiem użytkownika z systemem informatycznym - każdy system informatyczny posiada tzw. menu które jest wykorzystywane do tworzenia hierarchii poszczególnych funkcji przy korzystaniu z dialogu użytkownika systemu.

Wprowadzanie danych - zadaniem tych procedur jest umożliwienie użytkownikowi wprowadzenia danych, oraz częściowa ich weryfikacja

Aktualizacja danych - polega na dopisaniu określonych danych zmienianiu lub usunięciu

Sortowanie danych - w procedurach sortowania stosujemy tzw. klucz sortowania, w zależności od tego czy sortujemy dane na podstawie jednej cechy, czy też na podstawie wielu cech inaczej atrybutów mówimy o kluczu złożonym oraz o kluczu prostym (mówimy o prostym gdy jest jedna cecha).

Archiwizacja danych - związane jest to z tym że duże ilości danych są zapisywane na nośnikach zewnętrznych czy też różnego rodzaju stacji dysków. Drugą cechą jest przechowywanie informacji w celu zabezpieczenia w systemie informatycznym.

Wyszukiwanie i wyprowadzanie informacji -każdy użytkownik w zależności od formatu w jakim on chce otrzymać dane może wyprowadzić je na jaki tylko chce terminal.

Algorytm przedstawiamy w postaci

• Graficznej (wykorzystujemy schematy blokowe)

• Opisowej (np. idź, przynieś, podaj, itp.)

• Dźwiękowej (np. nie słyszę co mówisz)

• Elektronicznej (program komputerowy)

Zadaniem informatyków jest opracowanie różnego rodzaju algorytmów, pokazanie że stosowanie jakiegoś algorytmu nie ma sensu gdy on nam będzie liczył 200 mln lat. Zamiast dokładnego algorytmu który liczyłby nam wszystkie możliwe warianty stosuje się w praktyce

podejście heurystyczne.

Algorytmy dzielimy na :

• Proste

• Rozgałęzione

• Cykliczne ( rekurencyjne)

• Mieszane

Algorytmy proste - są to algorytmy w których następuje sekwencja realizacji poszczególnych instrukcji, a każda z nich wykonywana jest jednokrotnie

Algorytmy rozgałęzione - dopuszczają one alternatywność dróg rozwiązania zadania.

Algorytmy cykliczny - są to algorytmy w których może następować wielokrotna realizacja tych samych sekwencji realizacji

Algorytmy mieszane - posiadają one cech algorytmów rozgałęzionych oraz algorytmów cyklicznych. Charakteryzują się tym że są alternatywne drogi rozwiązania, a cykl pewnych operacji jest powtarzalny cyklicznie.

Każdy algorytm składa się z pewnej określonej liczby operacji, sama operacja składa się z dwóch części, jest to część operacyjna oraz część argumentowa, (np. w operacji „czytaj a”, „czytaj” jest częścią operacyjną a „a” jest częścią argumentową)

W informatyce wykonujemy trzy rodzaje operacji są to operacje arytmetyczne, logiczne oraz operacje sterowania, przykładem takiej operacji arytmetycznej jest instrukcja (a+b), przykładem operacji logicznej może być (czy a =b), operacja sterowania jest to operacja umożliwiająca się poruszanie po różnych częściach algorytmu z godnie z jego działaniem.

Głównymi operacjami tego sterowania są tzw. skoki.

Przy opracowywaniu algorytmu stosuje się znormalizowane podejścia, każdy autor może opracować algorytm w inny sposób, ale na ogół przyjmuje się że szkielet opracowania algorytmu składa się z następujących operacji:

1. Określenie pożądanego stanu wyjściowego

2. Określenie ram budowy algorytmów

3. Ustalenie dziedziny dopuszczalnych operacji (wybór oprogramowania)

4. Określenie celów pośrednich (cząstkowych)

5. Budowa procedur realizujące cele pośrednie

6. Powiązanie procedur cząstkowych w jedną całość

7. Opisanie algorytmu za pomocą określonego narzędzia prezentacji algorytmu

8. Weryfikacja algorytmu

Elementy stosowane przy budowie schematów blokowych

Strzałka - pokazuje nam powiązania między dwoma elementami schematu

Operand zapisujemy w nim wszystkie operacie za wyjątkiem instrukcji wyboru

Predykat zapisujemy w nim instrukcje wyboru

Etykieta zawiera polecenie START STOP

Gdy algorytm jest bardzo duży przy przejściu na następną stronę stosujemy n gdzie „n” jest numerem strony

Narzędziem prezentacji algorytmów są tzw. tablice decyzyjne które składają się z 4 podstawowych pól

Wykaz Zapisu

warunku warunku

Wykazu Zapisu

działań działań

W polu wykazu warunku zapisujemy wszystkie warunki jakie muszą być brane pod uwagę podczas podejmowania decyzji.

W polu zapisu warunku zapisujemy wszystkie kombinacje wartości jakie mogą przyjąć poszczególne warunki.

W polu wykazu działań zapisujemy zestaw wszystkich możliwych wariantów decyzji .

W polu zapisu działań zapisujemy warianty decyzji jakie należy podjąć przy określonej polu zapisu warunku w kombinacji wartości warunku.

Innym przykładem zapisu prezentacji są tablice krzyżowe dwuwymiarowe w nagłówkach kolumn i wierszy są zapisywane elementy bądź funkcje, ustalenie związku między elementami i funkcjami odbywa się przez podstawienie krzyżyka lub iksa.

Przykład

	St F	1	2	3	4
	St1		X
	St2	X
	St3				X
	St4			X

Następną formą prezentacji algorytmu jest schemat przebiegu

1. Dokumentacja źródłowa

2. Monitor z klawiaturą

3. Zbiór na dysku

4. Sortowanie danych

5. Emisję tabulogramów

Schemat blokowy równania kwadratowego

Przykład 1

ax²+bx+c=0

a=

b=

c=

TAK NIE

a=0

To nie jest =b²-4ac

rów. kwadrat.

TAK   

KONIEC

Nie ma 

pierwiastka

KONIEC

KONIEC

KONIEC

Przykład 2

START

Czytaj x

TAK x>0 NIE

Wypisz 1 TAK x=0 NIE

STOP wypisz 0 wypisz 1

STOP STOP

Przy stosowaniu danych wykorzystujemy różne algorytmy, np. rozpatrzmy trzy algorytmy proste wstawianie, proste wybieranie, algorytm bąbelkowy

Dane mogą być różnie w systemie uporządkowane i w zależności od tego jak one są uporządkowane tak przedstawia się minimalny i średni czas liczenia algorytmu

Dla oceny efektywności algorytmów stosowani używamy dwóch kryteriów

1. Ustalanie liczby niezbędnych porównań między poszczególnymi elementami Po

2. Liczba przesunięć elementów Pr

Proste wstawianie	Po=n-1 Pr=2(n-1)
Proste wybieranie	Po=(n^2-n)/2 Pr=3(n-1)
Algorytm bąbelkowy	Po=(n^2-n)/2 Pr=0

Algorytm kubełkowy

A1 B1 R1 A2 A3 K1 D1 A4 B2 R2








A1 B1 D1 K1 R1

A2 B2 R2

A3

A4

A B D K R

Algorytm bąbelkowy jest metodą porządkowania ciągów która polega na przestawianiu sąsiednich par elementów stojących w nieodpowiedniej kolejności, przy czym ciąg jest przeglądany w tym samym kierunku tak długo jak długo może w nim wystąpić jeszcze para elementów w niewłaściwym porządku. W suma algorytmów wykorzystuje się pojęcie kresu, przy czym kres określa miejsce w ciągu oznaczone na rysunku poziomą linią stanowiące granicę poszukiwania pary elementów po przestawieniu.


9 10 10 10 10


7 9 9 9 9


1 7 7 7 7


10 1 4 4 4


4 4 1 3 3



2 3 3 1 2

3 2 2 2 1

wykład 2 Informatyka

1







---