Wprowadzenie. Języki algorytmiczne. Tworzenie i eksploatacja programu.

Podstawowe pojęcia: algorytm, program, język programowania, struktura programu, instrukcje, zmienne i typy zmiennych, deklaracja zmiennych, operatory, wyrażenia.

„Informatyka zajmuje się całokształtem przechowywania, przesyłania, przetwarzania i interpretowania informacji. Wyróżnia się w niej dwa działy, dotyczące sprzętu i programowania”.

Definicja, opracowana w 1989 roku przez ACM, mówi:

„Informatyka to systematyczne badanie procesów algorytmicznych, które charakteryzują i przetwarzają informację, teoria, analiza, projektowanie, badanie efektywności, implementacja i zastosowania procesów algorytmicznych. Podstawowe pytanie informatyki to: co można (efektywnie) zalgorytmizować”.

Ważniejsze fakty z historii algorytmiki i rozwoju maszyn liczących

Abak(us) - liczydło w Mezopotamii X w. pne

Euklides IV w. pne - algorytm znajdowania największego wspólnego podzielnika

Muhammed ibn Musa al Chorezmi VIII / IX w., matematyk, astronom (algorytm, algebra, zero, system dziesiętny)

John Neper (XVII w.) - logarytmy, pałeczki Nepera

Blaise Pascal (1623-1662) - Pascalina, maszyna mechaniczna (50 szt.) wykorzystywana przy poborze podatków i pomiarach geodezyjnych. Wykonywała dodawanie i odejmowanie

Leibnic Gotfried (1646-1716) system binarny, maszyna mnożąca

Joseph Jacquard (1801) krosno tkackie sterowane otworami w kartach perforowanych

Charles Babbage (1791-1871) twórca maszyny różnicowej (np. kwadrat kolejnej liczby naturalnej jest sumą kwadratu poprzedniej liczby naturalnej i kolejnej nieparzystej liczby naturalnej) oraz projekt maszyny analitycznej sterowanej programem

Ada Augusta hrabina Lovelance, córka Byrona - algorytmy dla maszyny Babbage'a

Herman Hollerith (1860-1929) - karty perforowane i czytniki elektryczne (1890), IBM (1924)

Alan Turing (1912-1954) - maszyna Turinga (1936)

ENIAC (1946) - pierwszy komputer elektroniczny

John von Neuman (1903-1957) komputer z zapamiętanym programem

W celu rozwiązania dowolnego zadania przy wykorzystaniu komputera należy określić skończoną liczbę czynności, które należy wykonać na określonych danych, tj. skonstruować odpowiedni algorytm. (Algorismus IXw.- pisarz, matematyk perski). Algorytmizacja jest to działanie pozwalające otrzymać algorytm. Algorytm zapisany w języku programowania nazywa się programem, w którym czynności opisane są za pomocą odpowiednich instrukcji języka.

Każdy algorytm:

• posiada dane wejściowe i produkuje pewien wynik,

• jest precyzyjnie zdefiniowany (za pomocą określonych instrukcji),

• jest skończony,

• powinien być efektywny.

Algorytmy powinny spełniać określone wymagania. Są nimi:

• poprawność - posiadanie tej cechy przez algorytm oznacza, że algorytm rzeczywiście wytwarza żądane wyniki,

• określoność - cecha ta oznacza możliwość działania algorytmu niezależnie od wartości danych wejściowych,

• wykonalność - algorytmu składa z kroków wykonalnych dla wykonawcy algorytmu,

• testowalność - właściwość ta oznacza możliwość dokonania testów pozwalających rozstrzygnąć czy algorytm posiada wyżej wymienione cechy.

Algorytmy charakteryzują się pewnymi mierzalnymi cechami. Są nimi np.:

• dokładność obliczeń,

• złożoność obliczeniowa,

• złożoność pamięciowa.

Szybkość zmian w informatyce

Mimo oszałamiającej szybkości z jaką niektóre z innowacji technicznych stają się bezużyteczne i są zastępowane następnymi „podstawy informatyki” zmieniają się powoli.

Postęp technologiczny ma wpływ na rozwój zasad wytwarzania algorytmów poprzez:

• skrócenie czasu realizacji algorytmów,

• umożliwienie realizowania algorytmów dla dużej liczby przetwarzanych danych,

• umożliwienie prezentacji wyników działania algorytmów o złożonej postaci wyników (obraz, dźwięk) oraz

• umożliwienie udostępniania wyników szerokiemu gronu ich odbiorców w dowolnym miejscu i czasie.

Rozwój technologii wpływa na rozwój algorytmów, których stosowanie było uwarunkowane ograniczeniami technologicznymi.

Konstruując algorytm trzeba posiadać metodę jego zapisania.

Przykłady algorytmów

• w postaci listy kroków

Rozwiązywanie równania kwadratowego

ax² + bx + c =0

Dane: Współczynniki a, b, c równania.

Wyniki: Pierwiastki równania, jeśli dane współczynniki rzeczywiście określają równanie kwadratowe i równanie ma pierwiastki. Jeśli równanie nie ma pierwiastków, to wypisz odpowiedni komunikat.

Krok 1: Jeśli a = 0, to wypisz komunikat, że nie jest to równanie kwadratowe i zakończ algorytm.

Krok 2: Oblicz wartość wyróżnika Δ = b² - 4ac

Krok 3: Jeśli Δ<0 , to wypisz komunikat, że równanie kwadratowe nie ma pierwiastków i zakończ algorytm.

Krok 4: Jeśli Δ=0 , to oblicz oba pierwiastki z tego samego wzoru: x₁ = x₂ = -b / (2a), wypisz ich wartości i zakończ algorytm.

Krok 5: {W tym przypadku Δ>0} Oblicz pierwiastki według wzorów:

wypisz ich wartości i zakończ algorytm.

• w postaci schematu blokowego

Elementy schematów blokowych:

początek i koniec algorytmu

kierunek przetwarzania i łącznik

operacje wejścia i wyjścia

blok decyzyjny (warunek)

operacje przetwarzania danych i modułu (podprogramu)

- w postaci programu w języku Turbo Pascal

program kwadratowe;

var a, b, c, delta, x1, x2: real;

begin

writeln(`Podaj współczynniki równania kwadratowego');

readln(a, b, c);

if a=0 then writeln(`To nie jest równanie kwadratowe')

else begin

delta:=b*b-4*a*c;

if delta<0 then writeln(`Brak pierwiastków rzeczywistych')

else if delta=0 then

begin

x1:=-b/(2*a);

writeln(`Podwójny pierwiastek X=', x1:10:4);

end

else

begin

x1:=(-b-sqrt(delta))/(2*a);

x2:=(-b+sqrt(delta))/(2*a);

writeln(`Dwa pierwiastki X1=', x1:10:4,' X2=', x2:10:4);

end;

end;

end.

Proces tworzenia programu:

• specyfikacja założeń

• tworzenie algorytmów

• kodowanie

• edycja programów źródłowych

• kompilacja

• łączenie modułów bibliotecznych

• testowanie i usuwanie błędów

• tworzenie dokumentacji

• instalacja i szkolenie użytkowników

• modyfikacje programu

Programy w języku maszynowym, symbolicznym i wysokopoziomowym.

Wady programowania w języku niskopoziomowym:

• kod ściśle związany z danym komputerem,

• stosowanie sztuczek optymalizujących program,

• łatwość popełnienia błędu i trudność wykrycia,

• brak czytelnej struktury programu.

Języki wysokopoziomowe - zbliżone do języka zastosowań.

1957 Fortran (Formula Translator) IBM

1958-1960 Algol (Algorithmic Language) Peter Naur

1962 Cobol (Common bussines oriented language) Departament Obrony USA

1964-1967 PL/I - język uniwersalny, bardzo rozbudowany

1971 Pascal - N. Wirth (1983 Turbo Pascal Borlanda)

1972 język C - Dennis Ritchie (język programowania systemowego)

1979-1983 język C++ - Bjarne Stroustrup (programowanie obiektowe)

1994 - Object Pascal, Delphi (Borland) (narzędzie do szybkiego tworzenia aplikacji)Język programowania, wykorzystywany do zapisu dowolnego programu, korzysta ze skończonego zestawu symboli, których znaczenie i sposób użycia jest ściśle określone.

Alfabet języka - zbiór znaków za pomocą których zapisuje się programy.

Słowa kluczowe - zastrzeżone, o specjalnym znaczeniu, nie mogą być przedefiniowywane.

Są to słowa które maja specjalne znaczenie rozumiane przez kompilator języka Pascal:

(standard)

and array begin case const div do else end file for forward function goto if in label mod nil not of or packed procedure program record repeat set shl shr string then to type until var while with xor

(Turbo Pascal)

asm absolute downto external implementation inline interface interrupt unit uses

Zasady konstruowania z tych symboli bardziej złożonych konstrukcji językowych definiujemy najczęściej za pomocą diagramów syntaktycznych lub notacji BNF.

Diagramy syntaktyczne:

Notacja Backusa-Naura (BNF):

<cyfra>::=0|1|2|3|4|5|6|7|8|9

<ciąg cyfr>::=<cyfra>{<cyfra>}

<instrukcja złożona>::=begin<instrukcje>{;<instrukcje>}end

symbole metajęzykowe <> ::= {} |

Składnia języka Pascal nie wymusza podziału programu na wiersze (oprócz deklaracji zmiennych łańcuchowych) i cały program może być dowolnie podzielony na linie. Istotne jest tylko, aby poszczególne słowa kluczowe i identyfikatory (nazwy zmiennych, stałych, funkcji itp.) były oddzielone separatorem (dowolna ilość spacji lub znaku końca wiersza, znak tabulacji, średnik, nawias, +, -, :, =, >, <).

Struktura programu w języku Pascal.

program nazwa_programu; nagłówek nieobowiązkowy

uses Printer, CRT, Graph;

label lista_etykiet;

const sekwencja_definicji_stałych;

type sekwencja_definicji_typów;

var sekwencja_deklaracji_zmiennych;

procedure identyfikator_procedury;

begin

... ciąg instrukcji

end.

Komentarz { } lub (* *)

Dowolny tekst ujęty w znaki {} lub (* *) traktowana jest jako komentarz - czyli jest ignorowany przez kompilator.

Komentarze nie są wymagane, jednak poprawiają czytelność programu i należy je stosować.

Procedurą lub funkcją nazywamy wyodrębnioną część programu, stanowiącą pewną całość, posiadającą nazwę i ustalony sposób wymiany informacji z pozostałymi częściami programu.

Stosowanie procedur i funkcji umożliwia:

• programowanie modularne,

• wielokrotne używanie raz zdefiniowanych procedur i funkcji,

• zaoszczędzenie pamięci.

Moduły służą do grupowania funkcji i procedur w biblioteki oraz niezależnego pisania długich programów. Moduły mogą być standardowe (dostarczane z kompilatorem) oraz niestandardowe (własne).

Moduł standardowy System jest dostępny automatycznie, pozostałe trzeba deklarować poleceniem uses lista_nazw_modułów;

Etykieta umożliwia przekazanie sterowania do określonego miejsca za pomocą instrukcji goto

label alfa, beta1,10, 9999; {do 4 cyfr lub identyfikator}

Użycie etykiety

alfa: instrukcja;

...

goto alfa;

Identyfikator (nazwa) zmiennej (a także typu, stałej, funkcji, procedury i programu) musi zaczynać się od litery i nie może zawierać operatorów arytmetycznych i innych znaków specjalnych. Może zawierać litery, cyfry i znak "_". Małe i duże litery zarówno w nazwach jak i słowach kluczowych są nie rozróżniane. Pierwsze 63 znaki są znaczące. Identyfikatory predefiniowane można przedefiniowywać.

Liczby

liczby szesnastkowe poprzedzone są przez $

Literały znakowe #127 (dziesiętnie) #$7F (szesnastkowo) ^H (sterujące) (Ctrl+H)

Łańcuchy `Turbo Pascal'

Literały logiczne True False

Stałe
Każdemu literałowi możemy przyporządkować nazwę. Poprawia to czytelność programu i ułatwia zmiany.

W odróżnieniu od zmiennej, której wartość możemy zmodyfikować, możemy zadeklarować stałą. Powszechnie znane nam stałe to stałe matematyczne takie jak "Pi"" czy "e", lub prędkość światła "c".

Aby w naszym programie nie posługiwać się tajemnicza liczbą możemy zadeklarować stałą - od tej pory kompilator będzie wiedział, że jeżeli zostanie użyte słowo zadeklarowane jako nazwa stałej należy w tym miejscu umieścić odpowiednia wartość.

Deklaracja stałej wygląda podobnie do deklaracji zmiennej:

CONST identyfikator = wartość;

W przypadku stałej nie można deklarować kilku stałych w jednym wyrażeniu.

Przykłady:

CONST

Pi =3.14;

g = 9.81;

Wyrażenie - określa sposób obliczania wartości. Składa się ze stałych, zmiennych, operatorów i wywołań funkcji.

2 * PI + sin(x)

Operatory - symbole operacji

• Operatory arytmetyczne

* - mnożenie

/ - dzielenie

- - odejmowanie

+ - dodawanie

div - dzielenie całkowite

mod - reszta z dzielenia całkowitego

• Operatory logiczne Not And Or Xor Shl Shr (przesunięcia, wprowadzane są 0)

Operacje logiczne wykonywane są na zmiennych logicznych lub całkowitych (wówczas na parach bitów).

• Operatory relacyjne = <> < > <= >= in (jest elementem)

• Operatory teoriomnogościowe + suma zbiorów - różnica zbiorów * iloczyn zbiorów

• Operator konkatenacji (połączenie łańcuchów) +

• Operator @ - pobranie adresu podanego argumentu i ^ - wskazania przez wskaźnik

Priorytet operatorów:

1. jednoargumentowe + - @ not

2. multiplikatywne * / div mod and shl shr

3. addytywne + - or xor

4. relacyjne = <> > < <= >= in

Można używać nawiasów okrągłych aby zapewnić odpowiednią kolejność działań.
Działanie operatorów jest różne w zależności od typów zmiennych na których wykonywane są operacje.

Typy i zmienne proste: charakterystyka typów liczbowych rzeczywistych i całkowitych, typ znakowy i logiczny.

Zmienna to obszar w pamięci, który przechowuje jakąś wartość, posiada swoją nazwę (adres w pamięci) i jest określonego typu.

Typy danych - określają zbiór wartości zmiennej, wielkość zajmowanej przez nią pamięci oraz rodzaj operacji jakie można na niej wykonać.

klasyfikacja typów zmiennych w Pascalu

• prosty

• porządkowy

• całkowity

• logiczny

• znakowy

• okrojony

• wyliczeniowy

• rzeczywisty

• łańcuchowy

• strukturalny

• tablicowy

• rekordowy

• zbiorowy

• plikowy

• obiektowy

• wskaźnikowy

Zmienne powinny być zadeklarowane przed ich użyciem. Deklaracja obejmuje nazwę zmiennej i jej typ tj.

var z : T;

Kilka zmiennych jednakowego typu możemy zadeklarować tak:

var z1, z2,... , zn : T;

Typ zmiennej może być określony w deklaracji zmiennej lub w definicji typu (typ posiada wówczas swój identyfikator).

Typy proste są podstawowymi typami języka Turbo Pascal i mogą być wykorzystane do budowy bardziej złożonych struktur. Typy proste dzielimy na porządkowe i rzeczywiste. Typy porządkowe składają się ze skończonego i uporządkowanego zbioru wartości.

Typy całkowite
Typ	Zakres	Rozmiar w bajtach
integer	-32768...32767	2
shortint	-128..127	1
longint	-2147483648...2147483647	4
byte	0...255	1
word	0...65535	2

Typy rzeczywiste
Typ	Zakres	Liczba cyfr znaczących	Rozmiar w bajtach
real	2.9e-39...1.7e+38	11-12	6
single	1.5e-45...3.4e+38	7-8	4
double	5.0e-324...1.7e+308	15-16	8
extended	1.9e-4951...1.1e+4932	19-20	10
comp	1...9...2e+18	19-20	8

CHAR

Typ CHAR może przechowywać jeden znak ASCII. Jest to typ porządkowy - kolejnym znakom z zestawu ASCII można przypisać kolejne numery (porządek) co umożliwia konwersję pomiędzy typem porządkowym i całkowitym.

Do konwersji służą funkcje:

• ORD(x) : longint - zamiana zmiennej x dowolnego typu porządkowego na odpowiadającą jej wartość całkowitą

• CHR(x:byte) : char - operacja odwrotna do ORD

• UPCASE(x:char) : char - zamiana małej litery na dużą (tylko alfabet angielski)

Stałe typu CHAR w Turbo Pascalu można zapisywać w postaci 'a', 'x', #13, #$FA.

Wartości typu CHAR można porównywać, stosować w pętli FOR.

Do operacji arytmetycznych należy typ CHAR zamienić na typ całkowity.

Szczególnym typem tablicy jest STRING (typ łańcuchowy). Pozwala on przechowywać napisy. String jest tablicą o elementach typu CHAR. Pierwszy znak ma indeks 0 i mówi ile jest aktualnie liter w napisie. Maksymalna długość napisu w Turbo Pascalu to 255 znaki.

Deklaracja typu string może zawierać określenie maksymalnej długości napisu.

x: string; { napis o długości do 255 znaków }

y: string[10]; { napis o długości do 10 znaków }

Typ STRING dopuszcza wykonywanie następujących operacji:

• Porównania: "<", "=", ">", "<=", ">=", "<>"

Łączenie: "+"

Deklaracja własnego typu oraz typy okrojone

W Pascalu istnieje możliwość deklaracji własnego typu danych. Deklaracje takie są konieczne w pewnych konstrukcjach (wskaźniki, parametry funkcji i procedur), można je także stosować dla własnej wygody i polepszenia czytelności programu. Oto przykład:

W programie, który operuje na liczbach rzeczywistych (zadeklarowanych jako SINGLE) jeśli chcemy zwiększyć dokładność obliczeń musimy zmienić wszystkie deklaracje zmiennych (na DOUBLE). Operacja taka może być pracochłonna jeśli nasz program ma kilkadziesiąt tysięcy wierszy. Jeśli wprowadzimy własny typ nazwany jako FLOAT, który pierwotnie równoważny jest typowi REAL, i konsekwentnie stosujemy go w naszym programie, to aby zmienić precyzję obliczeń w całym programie wystarczy dokonać modyfikacji tylko w jednym miejscu: definicji typu FLOAT.

Składnia (w części deklaracyjnej programu):

TYPE

nazwa1 = typ_bazowy1;

nazwa2 = typ_bazowy2;

Przykład:

TYPE

float = real;

calkowity = integer;

inny_calkowity = calkowity;

Można także stworzyć typy okrojone, które przyjmują tylko pewien podzbiór wartości typu bazowego. Konstrukcja taka jest możliwa dla typów bazowych porządkowych (np. całkowitych, CHAR itp.);

Przykład:

TYPE

Indeksy =1..3; { zmienna indeksy może przyjmować wartości 0,1,2,3 }

Setka = 1..100;

MaleLitery = a..z;

zakres = -10..10;

Typy okrojone można także definiować bezpośrednio przy deklaracji zmiennej:

VAR

dziesiatki :1..10;

litery : a .. z;

Typ wyliczeniowy

program alfa;

type karta = (kier, karo, pik, trefl); {definicja typu wyliczeniowego}

var ala : karta; {deklaracja zmiennej ala typu karta}

begin

ala := kier;

if ala = karo then write(`OK.') else write(`NIE');

end.

type litera = `A'..'Z'; {podzbiór typu char}

type tydzień = (poniedziałek,wtorek,środa,czwartek,piątek,sobota,niedziela); {typ wyliczeniowy}

dni_robocze = poniedziałek..piątek; {typ okrojony typu tydzień,

nie może to być typ wyliczeniowy}

Typy porządkowe

Do typu porządkowego należą wszystkie typy całkowite (SHORTINT, INTEGER, LONGINT, BYTE, WORD), typ znakowy (CHAR), typ logiczny (BOOLEAN).

Do typów porządkowych zalicza się również typ okrojony oraz typ wyliczeniowy.
Do typów porządkowych można stosować trzy specyficzne funkcje:

• ORD - (omówiona przy typie znakowym) funkcja zamieniająca wartość typu porządkowego na odpowiadającą jej wartość liczbową,

• PRED(x) zwracająca wartość poprzedniego elementu danego typu

• SUCC(x) zwracająca wartość następnego elementu danego typu

Zwiększanie i zmniejszanie wartości zmiennej

Często w programach istnieje konieczność zwiększania lub zmniejszania zmiennych typu porządkowego o stałą wartość (np. i := i+1). Funkcje standardowe INC i DEC pozwalają zapisać tą operacje w elegancki sposób.

Składnia obydwu funkcji jest taka sama:

INC (zmienna, krok);

DEC (zmienna, krok);

Zmienna musi być typu porządkowego

Krok może być dowolnym wyrażeniem dającym wartość typu całkowitego (LONGINT).

Element Krok może zostać pominięty - domyślnie przyjmowany jest wtedy krok=1.

10

;

begind

end

cyfra

instrukcja złożona

cyfra

ciąg cyfr

cyfra

9

8

7

6

5

4

3

2

1

0

N

T

T

N

N

T

KONIEC

pisz

„x₁ oraz x₂”

pisz

„x₁=x₂”

pisz

„Brak pierw.”

oblicz x₁=x₂

Δ=0

Δ=b² - 4ac

Δ<0

START

a=0

oblicz x₁ x₂

pisz

„To nie RK”

czytaj a, b, c

A>0

sortuj dane

pisz NWD

czytaj A, B

P := A*B

A1

KONIEC

START

---