Materiały opracowano na podstawie autorskiego wykładu dra Mieczysława Lecha Owoca

1. Istota podejścia do algorytmizacji procesów przetwarzania danych - pojęcia i konteksty

Formy danych i informacji

•typowe (tekstowe, numeryczne, logiczne itp.)

•multimedialne (dźwięk, grafika, animacje itp.)

Struktury danych i informacji

•proste

•złożone (zbiory, bazy danych)

•zaawansowane (bazy wiedzy)

Przykłady procedur przetwarzania danych:

•sterowanie komunikacją użytkownika z

systemem

•wprowadzanie danych

•aktualizacja danych

•wyszukiwanie i wyprowadzanie informacji

•sortowanie danych

•archiwizacja danych

1. Istota i podejścia do algorytmizacji procesów przetwarzania danych - zawartość procedur

Procedura sterowania komunikacją użytkownika z systemem

•zdefiniowanie hierarchii ważności funkcji,

•ustalenie sposobu wywoływania i kończenia zadań,

•obsługa sytuacji wyjątkowych i generowanie komunikatów.

Procedura wprowadzania danych

•określenie zakresu wprowadzanych danych,

•zdefiniowanie formatu rejestrowanych danych,

•wyznaczenie sekwencji czynności umożliwiających wprowadza-nie danych,

•obsługa sytuacji wyjątkowych.

Procedura wyszukiwania i wyprowadzania informacji

•określenie parametrów wyszukiwania,

•wskazanie źródła danych i formatu wyprowadzanych informacji,

•wybór metod wyszukiwania i prezentacji informacji.

Procedura sortowania danych

•wyznaczenie zakresu danych sortowanych,

•ustalenie kryterium sortowania,

•dobór metody sortującej.

Istota i podejścia do algorytmizacji procesów przetwarzania danych - pojęcie i własności algorytmu

Algorytm -zbiór określonych reguł doprowadzających do rozwiązania zadania

Cechy algorytmu:

•jednoznaczność

•skończoność

•uniwersalność

Zadania analizy algorytmów:

•Czy problem jest rozwiązywalny na komputerze przy ustalonych

warunkach?

•Który ze znanych algorytmów można zastosować w danej sytuacji?

•Czy istnieje algorytm lepszy od podanego?

Podejścia do algorytmizacji procesów PD:

•Klasyczne (formy wyrażania)

•opisy słowne

•graficzne:

.schematy blokowe

.tablice decyzyjne

•inne

•Wykorzystujące techniki sztucznej inteligencji

•drzewa decyzyjne

•algorytmy ewolucyjne

•inne

•kiedy stosujemy podejścia klasyczne?

W procesie rozwiązywania każdego zadania możemy wyróżnić pewne etapy, które nas do niego prowadzą:

1. Sformułowanie zadania,

2. Określenie danych wejściowych,

3. Określenie celu, czyli wyniku,

4. Poszukiwanie metody rozwiązania, czyli algorytmu,

5. Przedstawienie algorytmu w odpowiedniej postaci,

6. Analiza poprawności rozwiązania ,

7. Testowanie rozwiązania dla różnych danych (ocena efektywności przyjętej metody).

Algorytmy powininny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i zastosowanie. Niektóre algorytmy można opisać w języku potocznym, zwłaszcza wtedy, gdy jego wykonawcą ma być człowiek.

Z czego składa się opis algorytmu?

Zawiera on opis danych, opis wyników oraz plan przetworzenia danych (np. ciąg czynności, które muszą być wykonane w określonej kolejności). Opis czynności występujących w algorytmie nazywamy instrukcjami.

Istnieją zadania, których realizacji nie można ująć w ramy jakiegoś planu działania. Taki charakter ma np. każda twórczość artystyczna. Konieczna jest do tego wyobraźnia i twórcze działanie, a na to nie ma przepisu (patrz nowela S. Lema).

Rodzaje algorytmów:

• sekwencyjne - instrukcje wykonywane są w porządku, w jakim zostały wprowadzone.

• iteracyjne - rodzaj algorytmu, w którym wielokrotnie wykonuje się pewne instrukcje, dopóki nie zostanie spełniony określony warunek,

• rekurencyjne - takie procedury, które w swojej definicji posiadają wywołanie samej siebie,

Ab ovo - od [bardzo prostego] początku - algorytm sekwencyjny

Algorytm gotowania jaja na miękko.

Na początku opracowywania algorytmu przyjmijmy założenia:

• używamy kuchenki gazowej, posiadamy garnek i wodę,

• niezbędne jest też samo jajko,

• nic nie utrudni samej czynności, to znaczy np. w trakcie gotowania nie zostaniemy pozbawieni dopływu gazu, czy też osoba nie wie co to jest garnek.

Algorytm ten ma postać:

1. Wlać do garnka zimną wodę.

2. Zapalić gaz.

3. Gotować wodę do wrzenia.

4. Włożyć jajko.

5. Odczekać trzy minuty.

6. Zgasić gaz.

7. Wyjąć jajko.

Algorytm dzwonienia do koleżanki / kolegi - wersja 1

1. Podnieś słuchawkę.

2. Wybierz cyfrę 1.

3. Wybierz cyfrę 2.

4. Wybierz cyfrę 3.

5. Wybierz cyfrę 4.

6. Wybierz cyfrę 5.

7. Wybierz cyfrę 6.

8. Wybierz cyfrę 7.

9. Przekaż informacje.

10. Odłóż słuchawkę.

A jeśli międzymiastowa,

A jeśli sygnał zajętości wcześniej,

A jeśli nie odbierze koleżanka,

Instrukcja warunkowa działa według jednego z dwóch przedstawionych schematów:

• Jeśli spełniony jest warunek W,

wykonaj instrukcję A.

• Jeśli spełniony jest warunek W,

to wykonaj instrukcję A;

w przeciwnym razie wykonaj instrukcję B.

Algorytm dzwonienia do koleżanki / kolegi - wersja 2

1. Podnieś słuchawkę.

2. Jeśli międzymiastowa

Wykręć 1 cyfrę numeru międzymiastowego

Wykręć 2 cyfrę numeru międzymiastowego

Wykręć 3 cyfrę numeru międzymiastowego

3. Wybierz cyfrę 1.

4. Jeśli sygnał zajętości,

4.1. Zakończ połączenie

5. Wybierz cyfrę 2.

6. Jeśli sygnał zajętości,

6.1. Zakończ połączenie

7. Wybierz cyfrę 3.

8. Jeśli sygnał zajętości,

8.1. Zakończ połączenie

9. Wybierz cyfrę 4.

10. Jeśli sygnał zajętości,

10.1. Zakończ połączenie

11. Wybierz cyfrę 5.

12. Jeśli sygnał zajętości,

12.1. Zakończ połączenie

13. Wybierz cyfrę 6.

14. Jeśli sygnał zajętości,

14.1. Zakończ połączenie

15. Wybierz cyfrę 7.

16. Jeśli sygnał zajętości,

16.1. Zakończ połączenie

17. Jeśli to nie koleżanka

1. Poproś o przekazanie słuchawki

18. Przekaż informacje.

19. Odłóż słuchawkę.

Algorytm dzwonienia do koleżanki / kolegi - wersja 2

1. Podnieś słuchawkę.

2. Jeśli międzymiastowa

• Wykonaj 3 razy

Wykręć kolejną cyfrę numeru międzymiastowego

3. Wykonaj 7 razy

• Wybierz kolejną cyfrę numeru lokalnego.

• Jeśli sygnał zajętości,

Odłóż słuchawkę

4. Jeśli słuchawka nie odłożona

5. Jeśli to nie koleżanka

Poproś o przekazanie słuchawki

6. Przekaż informacje.

7. Odłóż słuchawkę.

Podstawowe paradygmaty tworzenia algorytmów komputerowych:

dziel i zdobywaj - dzielimy problem na kilka mniejszych i je znowu dzielimy, aż ich rozwiązaniach nie staną się oczywiste (rekurencja),

programowanie dynamiczne - problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu,

metoda zachłanna - nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w tym momencie drogę rozwiązania,

programowanie liniowe - oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,

poszukiwanie i wyliczanie - kiedy przeszukujemy zbiór danych aż do odnalezienie rozwiązania,

probabilistyczne rozwiązanie - algorytm działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny,

heurystyka - człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach, rozwiązanie zawsze jest przybliżone.

2. Przegląd klasycznych rozwiązań -opis słowny

WE:

•Kartoteka pracowników

•Kwestionariusz osobowy

WY:

•Zaktualizowana kartoteka pracowników

Przetwarzanie:

•Otworzyć plik zawierający dane pracowników

•Wczytać dane nowego pracownika

•Zapisać zaktualizowane dane w kartotece pracowników

Problemy:

•jak sprawdzać poprawność wprowadzanych danych?

•jak opisywać operacje powtarzalne lub wymagające rozgałęzień?

2. Przegląd klasycznych rozwiązań - idea tablicy decyzyjnej (TD)

Tablica decyzyjna schematycznie wypełniona

Ponad 5 osób	T	T	T	T	N	N	N	N
Wysokie dochody	T	T	N	N	T	T	N	N
Duże oszczędności	T	N	T	N	T	N	T	N
W banku		X	X			X	X
Podzielić	X					X
Akcje					X
Brak porady				X				X
	1	2	3	4	5	6	7	8

Tablica decyzyjna zredukowana

Ponad 5 osób	T	T	N	--	N	--
Wysokie dochody	T	T	T	N	T	N
Duże oszczędności	T	N	N	T	T	N
W banku		X	X	X
Podzielić	X		X
Akcje					X
Brak porady						X
	1	2	6	3 + 7	5	4 + 8

2. Przegląd klasycznych rozwiązań - inne: pseudokod

Pseudokod („strukturalizowany język naturalny”) - zmodyfikowana forma języka polskiego używana do przedstawienia logiki przetwarzania danych; sprowadza się do „obsługi” podstawowych akcji wykonywanych podczas przetwarzania.

Akcje - odpowiadają czasownikom: czytaj, zapisz, drukuj, sortuj, przesuń, połącz, dodaj, odejmij, pomnóż, podziel, oblicz

Obiekty - odpowiadają rzeczownikom opisującym struktury danych: rekord, zbiór, zmienna, tablica, nazwa

Inne - dotyczą operatorów: równy, mniejszy niż, lub, i...

1. Proces - przyjęcie dostawy:

- wykonaj

•czytaj [następny] Dostawa-rekord

•znajdź odpowiedni Towar-rekord

•dodaj dokument-dostawy-rekord.Ilosc-przyjeta do Towar-rekord.Ilosc-towaru

-dopóki nie EOF (End-of-file)

2. Proces -generowanie zamówienia:

-wykonaj

•czytaj [następny] Towar-rekord

•Jeżeli Ilosc-towaru mniejsza niż Ilosc-minimalna-towaru

-To generuj Zamowienie

•koniec jeżeli

-dopóki nie EOF (End-of-file)

---