Algorytmy, języki programowania, programy

Wykład 6

Technologia Informacyjna

mgr Anna Bombińska-Sołtys

e-mail:a.bombinska@uwmsc.edu.pl

http://annasoltys.vot.pl/wyklady/

Historia algorytmu

 Pierwsze  opisy,  które  później  nazwano  algorytmami,  dotyczyły 

rozwiązań zadań matematycznych.

 Pomiędzy  400  a  300  rokiem  p.n.e.  grecki  matematyk  i  filozof 

Euklides,  wymyślił  pierwszy  znany  nam nietrywialny algorytm, 
czyli przepis na realizację zadania. Był to algorytm znajdowania 
największego  wspólnego  dzielnika  dwóch  dodatnich  liczb 
całkowitych.

Algorytm Euklidesa

 Algorytm  Euklidesa    - algorytm znajdowania  największego 

wspólnego dzielnika (NWD) dwóch liczb naturalnych. Nie wymaga 
rozkładania  liczb  na  czynniki  pierwsze.  Algorytm  wymyślił
Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go 
w swoim dziele Elementy.

 W algorytmie wykorzystywana jest zależność

 Największy wspólny dzielnik

 Stąd

Cechy algorytmu

1. Musi posiadać określony stan początkowy,  czyli operację od

której zaczyna się jego realizacja.

2. Ilość operacji potrzebnych do zakończenia pracy musi być

skończona - warunek skończoności.

3. Musi dać się zastosować do rozwiązywania całej klasy zagadnień,

a nie jednego konkretnego zadania – warunek uniwersalności.

4. Interpretacja poszczególnych etapów wykonania musi być

jednoznaczna - warunek jednoznaczności.

5. Cel musi być osiągnięty w akceptowalnym czasie – warunek

efektywności.

6. Musi posiadać wyróżniony koniec.

Sposoby zapisu i typy algorytmów

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

- ciąg kroków (opis słowny),

- drzewo decyzyjne

- schemat blokowy (sieć działań)

- zapis w strukturalnym języku programowania

Wyróżniamy następujące typy algorytmów:

- liniowy

- rozgałęziony

- z powtórzeniami (iteracyjny)

Ciąg kroków (opis słowny)

 Jest  to  na  ogół  mało  precyzyjny sposób  zapisu.  Polega  na 

logicznym  i  zrozumiałym  dla  odbiorcy  przedstawieniu  kolejnych 
czynności (akcji), jakie należy wykonać aby osiągnąć zamierzony 
efekt. Przykładami takiego opisu algorytmu mogą być: przepis
kulinarny,  recepta wykonania  leku,  metoda  rozwiązania 
zadania.

 Przykład - Algorytm gotowania jajka na miękko.

Krok 1.

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

Krok 2.

Zanotuj czas początkowy t

0

.

Krok 3.

Oczytaj czas aktualny t.

Krok 4.

Oblicz D

t

= t - t

0

.

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.

Drzewo decyzyjne

 Drzewo  decyzyjne – graficzna  metoda  wspomagania  procesu 

decyzyjnego, stosowana w teorii decyzji. 

Schemat blokowy

 Schemat  blokowy

algorytmu  jest  najbardziej  popularnym 

graficznym sposobem przedstawiania algorytmu. Składa się on ze 
skrzynek oraz  połączeń między  nimi.  Są tu  zapisane  operacje, 
które  mają być wykonane,  a  połączenia  wyznaczają kolejność
wykonania.

Schematy blokowe

 NAJWIĘKSZY WSPÓLNY DZIELNIK

Algorytm liniowy

 Algorytmem 

liniowym  (sekwencyjny)

nazywamy  taki 

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

Algorytm rozgałęziony

 Algorytm  rozgałęziony zawiera  rozgałęzienia  będące  efektem  

sprawdzania  warunków.  Wyrażenia  warunkowe  umożliwiają 
wykonanie  zadania  dla  wielu  wariantów  danych  i  rozważenie 
różnych przypadków.

Algorytm z powtórzeniami (iteracyjny)

 W 

algorytmach  z  powtórzeniami

powtarzanie  różnych  działań  ma  dwojaką 
postać:

- liczba 

powtórzeń

jest  z  góry 

określona (przed rozpoczęciem cyklu)

- liczba  powtórzeń

jest  nieznana

(zależy 

od 

spełnienia 

pewnego 

warunku).

Z  tego  wynika,  że  możemy  spotkać  się  z 
dwoma 

sytuacjami: 

gdy 

musimy 

wykonać  czynność  bądź  zadaną  ilość  razy, 
bądź do momentu spełnienia warunku.

Język algorytmiczny (programowania) 

 Język  algorytmiczny jest  najbardziej  ścisłym  i  zrozumiałym  dla 

komputera opisem algorytmu. 

 Algorytm

zapisany  w  języku programowania nazywamy 

programem.  Tekst  programu  może  również  służyć  do 
komunikowania rozwiązania człowiekowi. 

 Języki programowania są językami formalnymi (sztucznymi), a 

ich  wyrażenia,  czyli  programy muszą  mieć  formę    możliwą  do 
zaakceptowania przez maszynę. 

Języki programowania

1. Języki kompilowane (samodzielne programy): 

-

Pascal

-

Delphi 

-

C, C++.

2. Języki  częściowo  kompilowane (powstaje  kod  bajtowy  -

postać pośrednia wymagający platformy uruchomieniowej):

-

Java -JVM (Java VirtualMachine),

-

JRE (Java Runtime Environment),

-

C# -.NET Framework.

Wymienione platformy są bezpłatne.

Języki programowania

3. Języki interpretowane (wymagany jest interpreter):

-

JavaScript (interpreterem jest przeglądarka),

-

Perl  (Practical  Extraction  and  Report  Language,  praktyczny 
język ekstrakcji i raportowania),

-

PHP (obecnie PHP  Hypertext  Preprocessor,  pierwotnie
Personal  Home  Page)  stosowany  głównie  do  dynamicznego 
tworzenia stron internetowych,

-

VBA (Visual  Basic  for Aplications),  interpretatorem  jest 
pakiet  Microsoft  Office,  najbardziej  przydatny  w  arkuszu 
kalkulacyjnym.

Przegląd języków programowania

Program dla komputera IBM 650

 Kolumna  LOC zawiera  numer  adresu  pod  którym  znajduje  się 

instrukcja, OP zawiera  kod  operacji,  DATA dane, INST adres 
instrukcji, która ma być wykonana jako następna.

Program w języku FORTRAN I

 W  listopadzie  1954  roku  została  ogłoszona  pierwsza  specyfikacja 

języka  FORTRAN,  nazwa  jest  akronimem  słów the IBM
Mathematical FORmula TRANslating system.

 Można  zauważyć,  że  program  ten  jest  dużo  czytelniejszy  od 

poprzedniego.

Program w języku Algol-60

 W  latach  60-tych  antidotum  na  brak  czytelności  stał  się  język 

Algol-60. Wprowadzono w nim pętlę for oraz możliwość dzielenia 
programu na podprocedury.

Źródło

Literatura

 Wstęp  do  informatyki.

Piotr Fulmański, Ścibór  Sobieski. 

Podręcznik, Wydawnictwo Uniwersytetu Łódzkiego 2005. 

 Algorytmy. Maciej M. Sysło. WSiP Warszawa 2002.

Strony www:

 http://pl.wikipedia.org