Data 2001-10-06

Wykładowca Dr Piotr Buczyński

Podstawy informatyki

Literatura

1. Skrypt „wstęp do informatyki” wyd. Informa 1999

2. L.Bułchah i inni „DOS 5.0 od Środka” oficyna Wydawnicza W-wa 1992

3. K.Sache, P.Misimowicz, T Kręglewski „Przewodnik po tematyce mikrokomputerowej”, WNT W-wa 1998

4. T Walczak „Komputery - zasady działania, metody zastosowań”, PWE, W-wa 1997

5. A Szablewski, A Boroniec „Wstęp do informatyki” Informa Szczecin 2000.

ELEMENTY ARGORYTMIZACJI

ALGORYTMIZACJA- opracowywanie algorytmów rozwiązywanie zadań (stawianych przed komputerem)

MYŚLENIE ALGORYTMICZNE- logiczne myślenie

Pojęcia pierwotne algorytmizacji

Operacje elementarne - operacje (czynności) stanowiąca niepodzielną całość

Algorytm

Pojęcie metodologiczne: metoda rozwiązania danego problemu ( zadanie o skończonej liczbie operacji elementarnych

Pojęcie pragmatyczne: skończony ciąg operacji elementarnych służący do przekształcenia danych wejściowych w dane wyjściowe→ wyniki działania algorytmu

CECHY ALGORYTMU

1. Jednoznaczność definicji metody rozwiązania

2. Możliwość wielokrotnego wykorzystania (klasa zadań}

3. Skończona liczba operacji

4. Ustalona kolejność niektórych operacji

5. Dowolna kolejność niektórych operacji

6. Dany algorytm nie musi być jedynym rozwiązującym dany problem

STRUKTURA I FUNKCJONOWANIE ALGORYTMU

Postawione zadanie

↓

DANE WEJŚCIOWE

↓

OPERACJE

↓

DANE WYJŚCIOWE

↓

ZADANIE WYKONANE

Dane wejściowe

1. Parametry określają warunki i szczególne sposoby wykonania algorytmu

2. Argumenty na nich są wykonywane operację

+ OR - AND

Dane wyjściowe

1. Wyniki wykonywanego algorytmu

2. Zróżnicowana postać

Operacje

1. Arytmetyczne (działania arytmetyczne)

2. Logiczne (porównywanie, alternatywa, legacja)

3. Sterujące (poruszanie po algorytmie)

FORMY OPISU ALGORYTMU

• Język naturalny

• W języku formalnym (matematyka, logika)

• Graficzne (sieci działań schematy, tablice decyzyjne, schematy przepływu)

Schemat blokowy

Def. Graficzne odwzorowanie czynności, jakie należy wykonać dla zrealizowania określonego zadania.

SYMBOLE GRAFICZNE SCHEMATÓW BLOKOWYCH (SB)

1.Blok początku lub końca algorytmu

,

000--

2.Operator blok bezwarunkowy ( zmiana wartości, postaci lub miejsca zapisu)

3.Predykator wybór jednej z możliwych dróg działania

4.Wektor droga przepływu danych (sterowanie)

5.łącznik stronicowy

ZASADY KONSTRUKCJI SCHEMATÓW BLOKOWYCH (SB)

1. Schematy blokowe składają się z bloków powiązanych wektorami, które wyznaczają logiczną kolejność operacji

2. SB rozpoczynają się dokładnie jednym blokiem początku, (więc nie ma wejścia i jedno wyjście)

3. SB kończą przynajmniej jednym blokiem końca (minimum jedno wejście, nie ma wyjścia)

4. SB musi tworzyć graf spójny (sieć spójną)- bez wektorów „trafiających w próżnię”

5. Operator (blok bezwarunkowy)- minimum jedno wejście jedno wyjście

6. Operator opisuje realizację czynności jednorodnej

7. Predykat (blok warunkowy minimum jedno wejście dwa wyjścia

8. Poziom szczegółowości opisu działań (w operatorach i predykatach) zależy od rodzaju przewidywanego do zastosowania języka programowania.

9. Liczby łączników stronicowych muszą być parzyste

RODZAJE SCHEMATÓW BLOKOWYCH

1. Sieci liniowe

• Najprostsza struktura logiczne (z góry na dół)

• Brak predykatów tylko operatory

• Każdy operator ma dokładnie jedno wejście i 1 wyjście

• Każdy operator jest wykorzystywany tylko 1 raz

2)sieci z rozwidleniem

• Opis algorytmu rozwiązanie pewnego zadania w sposób alternatywny (z góry na dół)

• Wybór wariantu zależy od spełnienia określonych warunków wstępnych

• Schemat blokowy zawiera minimum jeden predykat

• SB zawiera warunkowe subschematy

• Subschematy schodzą się tworząc końcową sekwencję operatorem

2. Sieć z cyklem

• Opis algorytmu, w którym sekwencje operatorów muszą być powtarzane wielokrotnie

• SB zawiera minimum jeden predykat

• O pozostawaniu w cyklu decyduje parametr

• Czynności powtarzane *<0,∞) While po

<1,∞) Repest czytaj

Albo ustalona for do

SIEĆ MACIERZ

Opis algorytmu z cechami dwóch lub trzech........

Algorytm

y=ax²+bx+c





START





CZYTAJ a







A<>0 NIE




TAK





CZYTAJ b





CZYTAJ c





Delta= b*b*4ac









TAK ∇< 0 1.

NIE




PISZ „ NIE MA PIERWIASTKÓW”







STOP





1.






∇=0


TAK X₁=(-b-∇)/(2*a)


NIE




SQRT(delta)


X₁= ^-b/_(2*a)


X₂=(-b+∇)/(2*a)








PISZ X₁




PISZ X₁X₂





STOP




STOP

ALGORYTM EUPLIDESA

Algorytm Euklidesa, postępowanie, którego celem jest znalezienie największej wspólnej miary dwóch odcinków o długości m i n (lub największego wspólnego dzielnika dwóch liczb m i n). Krótszy z odcinków (np. n) odkłada się na dłuższym m tyle razy (czyli dzieli się m przez n), aż resztę stanowi odcinek r₁ mniejszy od odcinka n (jeśli reszta jest równa zero, to problem jest już rozwiązany). Następnie odcinek r₁ odkłada się na n tyle razy, by otrzymać resztę r₂ mniejszą od r₁. Jeśli r₂ = 0, to r₁ jest poszukiwaną wspólną miarą. Jeśli r₂ nie równa się 0, to z kolei odkłada się r₂ na r₁ itd., aż otrzymana reszta r_n = 0. Wówczas reszta r_n-1 jest poszukiwaną wspólną miarą (lub dzielnikiem).

Największy wspólny dzielnik, NWD, dla dwóch liczb naturalnych n, m taka największa liczba naturalna k, że n oraz m dzieli się bez reszty przez k. Pojęcie przydatne przy znajdowaniu wspólnego mianownika dwóch ułamków.

NWD wyznacza się rozkładając liczby m i n na czynniki pierwsze (przedstawiając je jako iloczyny liczb pierwszych), wtedy NWD równe jest iloczynowi powtarzających się w obu rozkładach liczb pierwszych.

Najmniejsza wspólna wielokrotność, NWW, dla dwóch liczb naturalnych n, m taka najmniejsza liczba naturalna k, że k dzieli się bez reszty przez n i przez m. Pojęcie przydatne przy znajdowaniu wspólnego mianownika dwóch ułamków.

Znajdowanie NWD (a, b) a, b ∈ N

1/a+1/b= x/NWW(a, b)

NWW = a* b/ NWD(a, b)

ALGORYTM EUPLIDESA

1. Czy a<> b jeżeli nie to NWD= a STOP

2. Czy a >b jeżeli tak to a =a -b/ idź do 1.

3. b= b -a idź do 1





START








A<>B



NIE

NWD= a TAK










a> b NIE





STOP TAK b =b - a




a=a -b

Przykładowy program

WHILE a<>b do

IF a>b THEN

A: =a-b;

ELSE

b:=b-a;

---