ALGORYTMY,

SCHEMATY BLOKOWE

Definicja algorytmu



W matematyce oraz informatyce to skończony

uporządkowany zupełnie zbiór jasno

zdefiniowanych czynności koniecznych do

wykonania pewnego zadania w skończonej

liczbie kroków.



Ma on przeprowadzić system z pewnego stanu

początkowego do pożądanego stanu

końcowego.

HISTORIA ALGORYTMU



Słowo

algorytm

pochodzi od nazwiska

arabskiego matematyka z

IX

wieku

Muhammeda ibn Musa Alchwarizmiego

.



Początkowo słowem

algorism

nazywano

czynności konieczne do wykonywania obliczeń

z użyciem dziesiętnego systemu liczbowego.



Obecne znaczenie słowa algorytm jako

zestawu ścisłych reguł powstało wraz z

rozwojem matematyki i techniki.

HISTORIA ALGORYTMU



W

1842

roku

Charles Babbage

, który na

podstawie swoich doświadczeń
sformułował ideę maszyny analitycznej
zdolnej do realizacji złożonych
algorytmów matematycznych.

ROZWÓJ MASZYN LICZĄCYCH



Wraz z wynalezieniem pod koniec

XIX wieku

kart perforowanych

elektro-mechaniczne

maszyny osiągnęły zdolność realizacji
algorytmów przetwarzających ogromne
zbiory danych.



Karty perforowane stały się wejściem, z
którego dane przetwarzały proste algorytmy
sumujące. Jako wyjście służyły odpowiednie
zegary.

ROZWÓJ MASZYN LICZĄCYCH



W

XX wieku

postęp elektroniki pozwolił

na budowę

maszyn analogowych

potrafiących w swoim wnętrzu odtwarzać
pewne algorytmy matematyczne.



Mogły one dokonywać operacji
arytmetycznych oraz różniczkować i
całkować.

KOMPUTERY



Badacze zdali sobie sprawę, że maszyny

najlepiej radzą sobie z szybkim

powtarzaniem bardzo prostych operacji.



Alan Turing

- Badacz ten podczas prac nad

algorytmami szyfrującymi, zdał sobie

sprawę, że każdy z nich da się sprowadzić

do zestawu instrukcji realizowanych przez

pewną teoretyczną maszynę. Miała ona

zdolność do czytania i pisania poleceń z

nieskończonej taśmy. Jej rozkazy mogły

zawierać polecenia przesunięcia się o ileś

kroków głowicy, zapisu/odczytu w jakimś

miejscu taśmy nowej instrukcji.

KOMPUTERY



Według tej idei zbudowano pierwsze

komputery. Posługiwały się algebrą

Boole'a

oraz binarnym systemem liczbowym.



Tak proste maszyny były w stanie realizować

bardzo złożone algorytmy matematyczne,

jak np. obliczanie trajektorii pocisków czy

rakiet.



Dzisiaj komputery są powszechne oraz tanie

i przez to implementacja w nich właściwych

algorytmów stała się bardzo ważną gałęzią

gospodarki.

ALGORYTMY KOMPUTEROWE

–

Komputery przetwarzają przekazywane im

informacje z wykorzystaniem pewnych

algorytmów. Program jest algorytmem zapisanym

w języku zrozumiałym dla maszyny.

–

Zwykle algorytmy pracują na pewnych danych

wejściowych i uzyskują z nich dane wyjściowe.

–

Każdy algorytm komputerowy musi być wyrażony

w bardzo rygorystycznie zdefiniowanym języku.

ALGORYTMY KOMPUTEROWE

–

Komputery mogą reagować tylko na całkowicie
jednoznaczne instrukcje.

–

Jeżeli dany algorytm da się wykonać na
maszynie o dostępnej mocy obliczeniowej i
pamięci oraz akceptowalnym czasie, to mówi
się, że jest

obliczalny

.

–

Poprawne działanie większości algorytmów
implementowanych w komputerach opiera się
na kolejnej realizacji pewnego zestawu
warunków. Jeżeli, któryś z nich nie zostanie
spełniony, to program kończy się komunikatem
błędu.

Podstawowe paradygmaty

tworzenia algorytmów

komputerowych:



dziel i zdobywaj

– dzielimy problem na

kilka mniejszych i je znowu dzielimy, aż
ich rozwiązania 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,

Podstawowe paradygmaty

tworzenia algorytmów

komputerowych:



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,

Podstawowe paradygmaty

tworzenia algorytmów

komputerowych:



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.

Najważniejsze techniki

implementacji algorytmów

komputerowych:



proceduralność

– algorytm dzielimy na

szereg podstawowych procedur, wiele
algorytmów dzieli wspólne biblioteki
standardowych procedur, z których są one
wywoływane w razie potrzeby,



praca po kolei

– wykonywanie kolejnych

procedur algorytmu, według kolejności ich
wywołań, na raz pracuje tylko jedna
procedura,

Najważniejsze techniki

implementacji algorytmów

komputerowych:



praca

równoległa

– wiele procedur

wykonywanych jest w tym samym czasie,

wymieniają się one danymi,



rekurencja

– procedura wywołuje sama siebie,

aż do uzyskania wyniku lub błędu,



obiektowość

– procedury i dane łączymy w

pewne obiekty reprezentujące najważniejsze

elementy algorytmu oraz stan wewnętrzny

wykonującego je urządzenia.

SCHEMAT BLOKOWY



To sieć działań, czyli graficzna
reprezentacja procedury lub programu
sporządzana w celach poglądowych lub
jako przedstawienie algorytmu do
zapisania w języku programowania.

KLOCKI SCHEMATU

BLOKOWEGO



KLOCKI GRANICZNE



KLOCKI WEJŚCIA I WYJŚCIA



KLOCEK WYKONAWCZY



KLOCEK WARUNKOWY

KLOCKI GRANICZNE

Używany do zakończenia
algorytmu (zwykle jeden, można
używać kilku - algorytm ma
wtedy mniej ścieżek i jest
bardziej przejrzysty).

Używany do rozpoczęcia
algorytmu(tylko jeden).

KLOCKI WEJŚCIA I WYJŚCIA

Służy do wprowadzania
danych(wartości) z zewnątrz.

Służy do wyprowadzania
danych.

KLOCEK WYKONAWCZY

W tym klocku można umieszczać
jedną lub kilka instrukcji. Korzysta
się z instrukcji przypisania(:=) i
operatorów arytmetycznych(+; -;
*; /; ^).

KLOCEK WARUNKOWY

Klocek ten ma jedno wejście i dwa wyjścia. Pytamy
np. czy lewa strona jest równa prawej(a=b).
Otrzymujemy odpowiedź TAK lub NIE i wychodzimy
jednym z wyjść. W klocku warunkowym umieszcza
się tylko jedno wyrażenie logiczne. Wyrażenie
logiczne budujemy za pomocą operatora logicznego,
inaczej znaku relacji(=; <; >; <=; >=; <>).

Przykład prostego algorytmu w

postaci schematu blokowego na sumę

trzech liczb:

Zasady rysowania schematów

blokowych:



Podstawową zasadą obowiązującą przy

budowę schematów blokowych, jest łączenie

strzałek wychodzących ze strzałkami

wchodzącymi.



Po zbudowaniu schematu blokowego nie

powinno być takich strzałek, które z nikąd nie

wychodzą, lub do nikąd nie dochodzą.



Każdy schemat blokowy musi mieć tylko jeden

element startowy oraz co najmniej jeden

element końca algorytmu.

SORTOWANIE BĄBELKOWE



Sortowanie bąbelkowe opiera się na bardzo
prostej metodzie, a mianowicie po kolei
porównywane są dwa sąsiednie elementy
tablicy. Gdy element o mniejszym indeksie
jest mniejszy od elementu o większym
indeksie, (gdy sortujemy tablicę rosnąco)
to zamieniane są one miejscami.
Porównywane są w ten sposób wszystkie
elementy tablicy. Algorytm kończy się, gdy
cała tablica jest uporządkowana.

SORTOWANIE BĄBELKOWE

2

4

-3

5

0

2

4

2

-3

5

0

2

2

-3

4

5

0

2

ALGORYTM EUKLIDESA

START

Dane: a, b

a>b

a:= b
b:= (a mod b)

(a
mod
b)=0

TAK

NI
E

Pisz: NWD(a, b)=

b

STOP

PODSUMOWANIE

WIADOMOŚCI

1. Algorytm to...

2. W którym wieku wynaleziono karty

perforowane:

a) W XVIII

b)W XIX

c) W XX

PODSUMOWANIE

WIADOMOŚCI

3. Na czym polega zasada tworzenia

algorytmów komputerowych „Dziel

i zdobywaj”?

3. Podaj cechy schematu blokowego.

4. Czy klocki graniczne są elementami

schematu blokowego?

TAK/NIE

PODSUMOWANIE

WIADOMOŚCI

6. Podaj nazwę poniższego klocka

schematu blokowego:

7. Co umieszczamy w klocku

wykonawczym?

8. Przedstaw w postaci schematu

blokowego algorytm włączenia
telewizora.

PODSUMOWANIE

WIADOMOŚCI

9. Jaki problem porusza algorytm

Euklidesa?

10. Przy pomocy sortowania

bąbelkowego ustaw w kolejności od
najmniejszej do największej
następujące liczby:

16

-8

4

10

0

2