SPIS TREŚCI
Rozmiar: 978 bajtów Strona główna Rozmiar: 978 bajtów Wprowadzenie do informatykiRozmiar: 978 bajtów System komputerowy
Rozmiar: 978 bajtów Dane tekstoweRozmiar: 978 bajtów Podstawowe operacje logiczne wykonywane przez procesor
Rozmiar: 978 bajtów Budowa komputeraRozmiar: 978 bajtów Zasada działania komputeraRozmiar: 978 bajtów
Rozmiar: 978 bajtów Urządzenia zewnętrzne komputeraRozmiar: 978 bajtów Pojęcie i zadania systemu operacyjnego
Rozmiar: 978 bajtów System operacyjny UNIX System VRozmiar: 978 bajtów Organizacja danych w systemie MS-DOS
Rozmiar: 978 bajtów Organizacja danych w systemie WindowsRozmiar: 978 bajtów Technika okienek w Windows
Rozmiar: 978 bajtów Graficzny interfejs użytkownikaRozmiar: 978 bajtów Startowanie i zamykanie systemu Windows
Rozmiar: 978 bajtów Słownik angielskich terminów komputerowych Rozmiar: 978 bajtów Pytania kontrolne
Rozmiar: 978 bajtów Wstęp do algorytmów Rozmiar: 978 bajtów Podstawowy edytor tekstów w systemie Windows 95
Rozmiar: 978 bajtów Dokumenty tekstowe Rozmiar: 978 bajtów Arkusze kalkulacyjne Rozmiar: 978 bajtów Relacyjne bazy danych
Rozmiar: 978 bajtów Wstęp do telekomunikacji Rozmiar: 978 bajtów Postawy sieci komputerowych
Rozmiar: 978 bajtów Podstawowe usługi realizowane w sieciach rozległych Rozmiar: 978 bajtów Wirusy komputerowe
Rozmiar: 978 bajtów Angielskie słownictwo komputerowe w Windows 95 Rozmiar: 978 bajtów 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 t0.

Krok 3. Oczytaj czas aktualny t.

Krok 4. Oblicz D t = t - t0.

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+25.

liczba miast wojewódzkich liczba tras czas znalezienia najkrótszej trasy
4 24 0,25 x 10-9 sekundy
25 1,551121004333 x10+25 2 x 105 lat

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:

  1. 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.

  2. Schemat blokowy

  1. 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
Liczba poprawnych odp. Ocena

0-1

1

2

2

3

3

4

4

5

5

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.

:=

Instrukcja przypisania

*

Operacja mnożenia

/

Operacja dzielenia

div

Operacja dzielenia całkowitego

mod

Reszta z dzielenia całkowitego

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:

Stopień wielomianu Liczba mnożeń metodą zwykłą Liczba mnożeń metodą Hornera
2 3 2
3 6 3
5 15 5
10 55 10
20 210 20

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
  1. Podaj definicję algorytmu liniowego (2 pkt.)
  2. Czy w algorytmach liniowych występują instrukcje warunkowe (bloki decyzyjne)? (1 pkt.)
  3. Narysuj schemat blokowy algorytmu Hornera dla obliczania wartości wielomianu II stopnia: (4 pkt.)

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

0-9

Ndst (1)

10-12

Dopuszczający (2)

13-15

Dst (3)

16-18

Db (4)

19-20

Bdb (5)

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

Element schematu blokowego

Instrukcja w języku PASCAL

  Begin
  End.
  Read(x);

(Objaśnienie: czytaj daną z klawiatury)

  Write(y);

(Objaśnienie: wypisz wynik na ekranie)

  zmienna := wyrażenie;
  Procedure(parametry);


if warunek then Instrukcja1 else Instrukcja2;

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.)
  1. Jakim znakiem musi kończyć się każdy wiersz oraz instrukcja w jezyku PASCAL? (1 pkt.)
  2. Napisz krótki program, który będzie realizował następujące operacje: ( 5 pkt.)
Liczba punktów Ocena

0-9

Ndst (1)

10-12

Dopuszczający (2)

13-15

Dst (3)

16-17

Db (4)

18-20

Bdb (5)