SPIS TREŚCI

Strona główna Wprowadzenie do informatyki System komputerowy Dane tekstowe Podstawowe operacje logiczne wykonywane przez procesor Budowa komputera Zasada działania komputera Urządzenia zewnętrzne komputera Pojęcie i zadania systemu operacyjnego System operacyjny UNIX System V Organizacja danych w systemie MS-DOS Organizacja danych w systemie Windows Technika okienek w Windows Graficzny interfejs użytkownika Startowanie i zamykanie systemu Windows Słownik angielskich terminów komputerowych Pytania kontrolne Wstęp do algorytmów Podstawowy edytor tekstów w systemie Windows 95 Dokumenty tekstowe Arkusze kalkulacyjne Relacyjne bazy danych Wstęp do telekomunikacji Postawy sieci komputerowych Podstawowe usługi realizowane w sieciach rozległych Wirusy komputerowe Angielskie słownictwo komputerowe w Windows 95 Sprawdzian z angielskiego słownictwa komputerowego

Wstęp do algorytmów

Definicja algorytmu

Sposoby przedstawiania algorytmów

Program jako algorytm

Zadanie domowe

Sprawdzian kontrolny nr 1

Sposób rysowania schematów blokowych

Reguły rysowania schematów blokowych

Definicja algorytmu liniowego

Algorytm obliczania wartości wielomianu II stopnia

Algorytm Hornera III stopnia

Sprawdzian kontrolny nr 2

Jezyki programowania a algorytmy

Sprawdzian kontrolny nr 3

Definicja algorytmu

Algorytm jest przepisem opisującym krok po kroku rozwiązanie problemu lub osiągnięcie jakiegoś celu.

Przykład:

Algorytm gotowania jajka na miękko.

Krok 1. Włóż jajko do gotującej się wody.

Krok 2. Zanotuj czas początkowy t₀.

Krok 3. Oczytaj czas aktualny t.

Krok 4. Oblicz D t = t - t₀.

Krok 5. Jeśli D t < 3 min., to przejdź do kroku 3.

Krok 6. Wyjmij jajko z gotującej się wody. Zakończ algorytm.

Człowiek zawsze starał się ułatwiać sobie życie oraz ulepszać metody realizacji swoich zamierzeń: wzniecanie ognia, budowanie piramid, wysyłanie wiadomości, sterowanie maszynami, wychodzenie z labiryntu, pakowanie plecaka. Najstarsze algorytmy mają około 2000 lat, a więc opracowano je jeszcze przed pojawieniem się pierwszych komputerów.

Choć szybkość działania obecnych komputerów jest zawrotna, to jednak istnieją zadania, których rozwiązywanie przy pomocy komputera może trwać dłużej niż życie pojedynczego człowieka.

Przykład:

Zaplanowano zorganizowanie spotkań premiera z wojewodami. Premier ma wyruszyć ze stolicy, odwiedzić wszystkie województwa, każde dokładnie jeden raz, i wrócić do stolicy. Nasze zadanie polega na wskazaniu premierowi najkrótszej drogi.

W przypadku państwa z czteroma województwami najkrótsza trasa przejazdu będzie wyglądała jak na poniższym rysunku.

W takim przypadku liczba możliwych tras wynosi 4!=24. Natomiast dla państwa z 25 województwami liczba tras do sprawdzenia będzie wynosiła 25!=1,551121004333 x10⁺²⁵.

Sposoby przedstawiania algorytmów

Występują następujące sposoby przedstawiania algorytmów:

1. Słowny – na ogół mało dokładny.
2. Lista kroków.
3. Schemat blokowy.
4. Drzewo algorytmu.

Zadanie {obliczanie wartości funkcji f(x)}:

Napisz algorytm obliczający wartość funkcji

przy założeniu, że dla x=0 f(x)=0 .

1. Słowny opis algorytmu

a. dla liczb ujemnych |x| = -x, a więc

b. dla liczb dodatnich |x| = x, a więc

c. jeśli x = 0, to z podanej wyżej definicji wynika, że f(x) = 0.

W matematyce opis słowny przedstawiamy następująco:

2. Algorytm w postaci listy kroków

   Dane: Dowolna liczba rzeczywista x.

   Wynik: Wartość funkcji f(x)

   Krok 1. Wczytaj wartość danej x.

   Krok 2. Jeśli x > 0, to f(x)=1. Zakończ algorytm.

   Krok 3. Jeśli x = 0, to f(x)=0. Zakończ algorytm.

   Krok 4. Jeśli x < 0, to f(x)=-1. Zakończ algorytm.

3. Schemat blokowy

4. Drzewo algorytmu

Program jako algorytm

Program komputerowy to algorytm napisany w języku programowania.

Język programowania musi być zrozumiały dla komputera. Tekst programu może też służyć ludziom do przekazywania sobie algorytmów. W dalszych lekcjach o algorytmach będziemy używali języka Pascal.

Poprzedni algorytm zapisany w języku Pascal wygląda następująco:

program Zadanie1;

var x:real;

begin

read(x);

if x > 0 then write(1)

else if x = 0 then write(0)

else write(-1)

end.

Uwaga: Blok decyzyjny ze schematu blokowego jest tutaj zastąpiony przez instrukcję if ... then .... else....

Zadanie domowe

1). Narysuj schemat blokowy algorytmu obliczającego wartość funkcji Przyjmij, że komputer potrafi tylko dodawać i mnożyć.

2). Napisz algorytm w języku Pascal, który oblicza wartość bezwzględną liczby x. Definicja funkcji matematycznej wygląda następująco:

Sprawdzian kontrolny nr 1 za 5 pkt.

1. Podaj definicję algorytmu
2. Ile lat temu opracowano pierwsze algorytmy
3. Wymień sposoby przedstawiania algorytmów
4. Jakie słowo w języku Pascal zastępuje blok decyzyjny?
5. Podaj definicję programu

Sposób rysowania schematów blokowych

Żeby przekazać posiadany algorytm drugiemu człowiekowi lub maszynie, musimy ten algorytm zapisać. I tu powstaje problem języka do zapisywania algorytmów. Języki naturalne, takie jak język polski, język angielski itp., nie bardzo się nadają do tego celu. Mimo to od wieków algorytmy zapisywano w językach naturalnych. Problem nie był palący, dopóki nie pojawiły się komputery. Ponieważ maszyna nie potrafi się niczego domyślić, to musi mieć jednoznacznie opisane czynności. Najlepszym obecnie “językiem” opisu algorytmów jest tzw. schemat blokowy.

Podstawową zasadą obowiązującą przy budowę schematów blokowych, jest łączenie strzałek “wychodzących” ze strzałkami “wchodzącymi”.

Schematy blokowe są zbudowane ze strzałek oraz niżej przedstawionych elementów.

Reguły rysowania schematów blokowych

I. Po zbudowaniu schematu blokowego nie powinno być takich strzałek, które z nikąd nie wychodzą, lub do nikąd nie dochodzą.

II. Każdy schemat blokowy musi mieć tylko jeden element startowy oraz co najmniej jeden element końca algorytmu.

Definicja algorytmu liniowego

Algorytmem liniowym nazywamy taki algorytm, który ma postać listy kroków wykonywanych zgodnie z ich kolejnością.

Algorytmy liniowe są zapisem obliczeń, które mają postać ciągu operacji rachunkowych wykonywanych bez sprawdzania jakichkolwiek warunków.

Wielomiany występują w wielu szkolnych zadaniach z matematyki oraz fizyki. Wartości wielomianów obliczmy dla konkretnych argumentów. Na ogół zajmujemy się wielomianami drugiego lub trzeciego stopnia, są to więc funkcje tak proste, że bez zastanowienia wykonujemy zapisane w nich działania.

Algorytm obliczania wartości wielomianu II stopnia

Rozważmy wielomian II stopnia: . Aby obliczyć jego wartość, zwykle podnosimy najpierw x do kwadratu (czyli mnożymy x przez siebie). Otrzymaną wartość mnożymy przez współczynnik a. Następnie mnożymy współczynnik b przez x. Sumując otrzymane wyniki oraz wyraz wolny c. otrzymujemy wartość wielomianu w(x).

Algorytm zwykły obliczający wielomian II stopnia (2 dodawania i 3 mnożenia)

W tak skonstruowanym algorytmie wykonujemy 3 mnożenia i 2 dodawania. Aby zmniejszyć liczbę mnożeń, należy zastosować algorytm wykorzystujący następującą postać wielomianu:

Algorytm Hornera obliczający wielomian II stopnia (2 dodawania i 2 mnożenia)

Algorytm Hornera 3 stopnia

Rozważmy wielomian III stopnia:

Aby obliczyć jego wartość, zwykle korzystamy z następującego algorytmu (w którym wykonujemy 6 mnożeń i 3 dodawania).

Algorytm zwykły obliczający wielomian III stopnia (3 dodawania i 6 mnożeń)

Aby zmniejszyć liczbę mnożeń, wykorzystamy przekształcenie wielomianu w(x) do następującej postaci:

Algorytm Hornera obliczający wielomian III stopnia (3 dodawania i 3 mnożenia)

Nie jest ważne, czy do obliczeń wykorzystamy liczydło, kalkulator lub superkomputer. Istotna jest metoda, którą zastosujemy do obliczeń, szczególnie gdy stopień wielomianu jest duży. Pokazuje to tabelka:

Wzór na liczbę mnożeń dla metody zwykłej

Wzór na liczbę mnożeń dla metody Hornera

Sprawdzian kontrolny nr 2 za 20 pkt.(40 minut)

1. Dlaczego do opisu algorytmów stosujemy schemat blokowy, a nie język naturalny? (2 pkt.)
2. Narysuj i opisz elementy z których buduje się schematy blokowe (6 pkt.)
3. Wymień zasady obowiązujące przy budowaniu schematów blokowych (2 pkt.)
4. Jakimi znakami oznacza się operacje: (3 pkt.)

1. przypisania,
2. mnożenia,
3. dzielenia

5. Podaj definicję algorytmu liniowego (2 pkt.)
6. Czy w algorytmach liniowych występują instrukcje warunkowe (bloki decyzyjne)? (1 pkt.)
7. Narysuj schemat blokowy algorytmu Hornera dla obliczania wartości wielomianu II stopnia: (4 pkt.)

8. Wielomian jest stopnia 6. Ile operacji mnożenia oraz operacji dodawania wykona algorytm Hornera obliczający wartość tego wielomianu? (4 pkt.)

Języki programowania, a algorytmy

Schematów blokowych używamy do zapisywania algorytmów głównie w komunikacji człowiek – człowiek. Natomiast w komunikacji człowiek – komputer, algorytmy zapisujemy przy pomocy tzw. języków programowania. Schematy blokowe są na razie “nieczytelne” dla komputerów, z powodu braku odpowiednich programów tłumaczących (translatorów) z postaci schematu blokowego na języki wewnętrzne komputerów.

Języki programowania dzielimy na:

1. języki wewnętrzne (binarne lub asemblery),
2. języki zewnętrzne (FORTRAN, COBOL, PASCAL, C, BASIC,CLIPPER).

Aby zamienić schemat blokowy na zapis w postaci programu komputerowego będziemy musieli poznać budowę programu, w naszym przypadku napisanego w języku PASCAL. Każdy program w języku PASCAL, w pierwszym wierszu musi rozpoczynać się od napisu program, spacji, dowolnej nazwy programu oraz znaku średnika ;. W następnym wierszu należy zadeklarować jakich zmiennych będzie używał program. Deklaracja ta składa się z: napisu var, spacji, nazw zmiennych (np. x,y,z), znaku dwukropka :, typu zmiennej np. real (liczby rzeczywiste) oraz znaku średnika ;. (patrz poniższy przykład)

Przykład:

Teraz możemy przystąpić do konstruowania programu, która będzie wykonywać nasz algorytm. Aby nie komplikować zbytnio naszego przykładu, zajmiemy się programowaniem algorytmu obliczającego wartość bezwzględną dla liczby x.

Wiadomo z matematyki, że:

Schemat blokowy algorytmu będzie więc wyglądał jak na powyższym rysunku.

Naszego program będzie wyglądał następująco:

program WARTBEZ;

var x: real;

Begin

Read(x);

If x < 0 then x := – x;

Write(x);

End.

Pamiętaj: Każdy algorytm (a więc część główna programu w PASCALu) rozpoczyna się słowem begin i kończy się słowem end oraz kropką. Każdy wiersz oraz instrukcja w języku PASCAL musi kończyć się znakiem średnika ;.

W pisaniu programów będzie pomocna następująca tabelka

Sprawdzian kontrolny nr 3 za 20 pkt.(25 minut)

1. Jak dzielimy języki komputerowe? (2 pkt.)
2. Wymień 3 języki zewnętrzne (3 pkt.)
3. Wyjaśnij dlaczego schematów blokowych nie stosuje się w komunikacji człowiek-komputer? (2 pkt.)
4. Podaj definicję programu (3 pkt.)
5. Od jakiego napisu rozpoczyna się deklaracja zmiennych w programie napisanym w języku PASCAL? (1 pkt.)
6. Wymień instrukcje języka PASCAL służące do:

a. Czytania danych z klawiatury,

b. Wypisywania wyników na ekranie,

c. Badania warunku (3 pkt.)

7. Jakim znakiem musi kończyć się każdy wiersz oraz instrukcja w jezyku PASCAL? (1 pkt.)
8. Napisz krótki program, który będzie realizował następujące operacje: ( 5 pkt.)

• czytanie liczby z klawiatury,
• wyświetlanie tej liczby na ekranie.