Informatyka zajmuje się rozwiązywaniem problemów za pomocą komputerów. Zapis problemu w języku zrozumiałym dla komputera to algorytm. Informatyka zatem to także nauka o algorytmach.

Informatyka zajmuje się

rozwiązywaniem problemów za

pomocą komputerów. Zapis

problemu w ścisłej postaci

pokazującej jak postępować krok

po kroku, by rozwiązać problem to

algorytm. Informatyka zatem to

inaczej nauka o algorytmach.

Zapis algorytmu w języku

zrozumiałym dla komputera to z

kolei program.

Sformalizujmy definicję

algorytmu

Algorytm

to uporządkowany zbiór, jednoznacznych,

wykonywalnych kroków, określający skończony proces,

który dla właściwych danych wejściowych „produkuje”

żądany wynik

    Uwagi:
     - uporządkowanie kroków ( w sensie
       przyczynowo-skutkowym) nie wyklucza
       algorytmów równoległych
       (wielowątkowych)
     - wykonywalność kroków bywa określana jako

obliczalność

- żądanie skończoności eliminuje nieskończone

procesy nie dające rozsądnych wyników

A zatem:



Problem



Algorytm czyli ścisły zapis problemu w

jednej z możliwych notacji (zapis, który

krok po kroku opowiada jak osiągnąć cel)



Program-komputerowa realizacja

algorytmu



Proces – wykonanie programu

Algorytmy mogą wykorzystywać zarówno

znane metody jak i nowo opracowane.

Trudno podać algorytm rozwiązywania problemu
choć były próby (fazy rozwiązywania problemu
wg Polya).

Reprezentacja algorytmów

Algorytm jest tworem abstrakcyjnym,

tworem fizycznym jest sposób jego
przedstawienia czyli

reprezentacja

algorytmu

Dokładne określenie problemu poprzez

wyszczególnienie danych ( i warunków jakie
mają spełniać) oraz wyników ( i też
warunków jakie mają spełniać) nazywamy

specyfikacją problemu (algorytmu).

Przykłady reprezentacji

algorytmów



słowna



w postaci listy kroków



schematy blokowe



drzewo obliczeń



pseudokod



diagramy Nassi-Schneidermana



w języku programowania (co prowadzi
już do konstrukcji programu)

Przykładowy problem

Dane:

trzy dowolne liczby a,b i c

Wynik:

wartość największej z tych

liczb

Algorytm – opis słowny

Należy przyjąć, że największą

liczbą jest

, a następnie porównać

z nią najpierw liczbę

zapamiętać

większą liczbę z tej pary, a
następnie porównać ją z liczbą

Większa liczba z tego drugiego
porównania daje poszukiwaną
wartość.

Algorytm - lista kroków



Krok 1.

Określ wartości a,b i c



Krok 2.

Przyjmij, że max = a



Krok 3.

Jeżeli b jest większe niż

max, to przyjmij, że max=b



Krok 4.

Jeżeli c jest większe niż

max, to przyjmij, że max=c



Krok 5.

Wypisz max jako wynik

a,b,c

Max:=a

Max<b

b<b

Max:=b

Max<c

Max:=c

Wynik: max

KONIEC

Start

Algorytm- schemat

blokowy

b >=a

c>=b

Wynik :c

Wynik :b

c>=a

Wynik :c

Wynik :a

Algorytm w postaci drzewa obliczeń

Algorytm - pseudokod



Krok 1.

Dane a,b i c



Krok 2.

max = a



Krok 3.

Jeżeli b >max, to max=b



Krok 4.

Jeżeli c >max, to max=c



Krok 5.

Wynik: max

Inne notacje algorytmów-

diagramy Nassi-

Schneidermanna

a,b

a,b,c <<

max:=a

max<b

TAK

NIE

max:=b

max<c

NIE

TAK

max:=c

Wypisz max

Typy algorytmów



liniowe



rozgałęzione



iteracyjne



rekurencyjne

Języki programowania w

ewolucji historycznym



początki procesu programowania- algorytmy

wyrażane w języku maszynowym



języki asemblerowe (drugiego poziomu)



języki trzeciej generacji



języki wysokiego poziomu -

pełna

niezależność od środowiska komputera i

komunikowanie się z komputerem za

pomocą pojęć i struktur abstrakcyjnych (to

komputer winien dostosowywać się do

charakterystyki człowieka) –duże spektrum

tych języków

Język naturalny, a język

programowania



jeden i drugi ma swój zbiór słów, zbiór reguł mówiących jak

tworzyć poprawne zdania (instrukcje języka programowania) czyli

składnię i reguł mówiących jak je rozumieć czyli semantykę,

więcej jest jednak różnic



język naturalny pozostawia wiele interpretacji, wyczuciu, zawiera

zwroty wieloznaczne, idiomy; język programowania nie pozostawia

miejsca na interpretacje i domysły- żądania wobec komputera

muszą być wyartykułowane w sposób ścisły i jednoznaczny



programy w części dotyczącej algorytmiki muszą być uniwersalne,

drobne różnice realizacyjne między komputerami wynikają z

architektury komputera, a nie istoty algorytmu- narzuca to wymóg

odpowiedniej uniwersalności na języki programowania



język naturalny jest zastany, jego bogactwo tworzone jest

wielopokoleniowo, język programowania jest tworem sztucznym,

który konstruuje się praktycznie od zera

Konstrukcja języka metodą

gramatyk formalnych



gramatyki te stworzyły N.Chomsky
bezskutecznie próbując opisać nimi
bogactwo języka naturalnego
(angielskiego)- okazały się one
znakomitym narzędziem do opisu
języków programowania, zwłaszcza
część teorii Chomsky’ego dotycząca
tzw. gramatyk bezkontekstowych

Podstawy teorii gramatyk

bezkontekstowych



alfabet to dowolny zbiór znaków - A



słowo to dowolny ciąg znaków utworzonych z

dopuszczonych przez alfabet znaków (dopuszczamy

także tzw. słowo puste o zerowej długości –ε)



długość słowa to liczba jego znaków



zbiór wszystkich możliwych słów jaki można

utworzyć przy pomocy alfabetu A oznaczmy przez A*



językiem zdefiniowanym nad alfabetem A nazywamy

dowolny podzbiór A*

Język użyty tu definicyjnie dla rozróżnienia od

rzeczywistych języków programowania

definiowanych później przez te gramatyki nazywamy

językiem formalnym

Podstawy teorii gramatyk

bezkontekstowych



Przykład

Jeśli A= {a,b}
to A*=

{ε,a,b,aa,bb,ab,ba,aab,aba…}

Definicja gramatyki

bezkontekstowej



Jest to uporządkowana czwórka:

{N,T,P,S}
N- zbiór tzw. symboli pomocniczych
T- zbiór symboli końcowych
P- zbiór produkcji czyli konstrukcji postaci

Pojedyncza produkcja to innymi słowy możliwość zastąpienia symbolu

pomocniczego przez słowo, w skład którego mogą wchodzić

zarówno symbole pomocnicze jak i końcowe.

S- wyróżniony symbol pomocniczy gramatyki (tzw. aksjomat)

Idea tworzenia języka generowanego przez taką

gramatykę polega na tym, aby wychodząc z symbolu

pomocniczego tak długo stosować, którąś z produkcji aż

znikną symbole pomocnicze i zostaną wyłącznie końcowe

)

(







Gramatyki bezkontekstowe-

przykłady

Przykład 1
G1={ {S}, {a}, {S:= ε,S:=aaS},S}
Gramatyka generuje słowa o parzystej

długości (przyjmując, że słowo puste tez ma

parzystą długość) złożone wyłącznie z liter a

Przykład 2
G2={ {S}, {a,b}, {S:= ε,S:=aSa,S=bSb},S}
Gramatyka generuje palindromy o parzystej

długości złożone tylko z liter a oraz b

Gramatyki bezkontekstowe-

uzupełnienia



Gramatyka G jest jednoznaczna jeżeli każde słowo

języka, które można z niej wyprowadzić ma tylko

jeden sposób wyprowadzenia



Gramatyka G jest zgodna z językiem L ze zbioru T*

jeżeli każe słowo wyprowadzalne z G należy do L



Gramatyka G jest pełna względem języka L jeżli każde

słowo tego języka jest wyprowadzalne z gramatyki G

Definiując określony język programowania przy

pomocy gramatyki dążyć się będzie do tego, aby

każdy program (jako zbiór słów tego języka) był

jednoznaczny. Bazą alfabetu są w przypadku

większości języków programowania słowa języka

angielskiego

Przykład gramatyki

definiujacej liczby całkowite



Przyjmujmy, że w dowolnym języku
programowania liczba całkowita to
ciąg cyfr poprzedzonych znakiem + lub
–

Mamy wówczas:
G={ {S,Z,C,L}, {-,+,0,1,2,3,4,5,6,7,8,9},

{C::=0|1|2|3|4|5|6|7|8|9,S::=L|
ZL,Z::=+|-, L::=C|LC},S}

Konstrukcja języka

programowania



na podobnej zasadzie buduje się definicje

innych typów danych, wyrażeń, a także

konstrukcji programistycznych instrukcji



cały taki zbiór z dbałością o jednoznaczność

gramatyk definiuje nam język programowania



poprawność tej definicji gwarantuje nam

uzupełnienie gramatyki o zbiór odpowiednich

reguł semantycznych jednoznacznie

określających interpretację (przyjmowane

wartości) dla poszczególnych symboli i

wyrażeń

Szczegółowe notacje

używane do opisu gramatyk

bezkontekstowych



notacja użyta przykładowo do opisu

produkcji w definicji wyrażenia

całkowitoliczbowego nosi nazwę notacji

BNF (Backusa-Naura) i stanowi właśnie

zestaw reguł produkcji



używana powszechnie do definicji składni

języków programowania, a także protokołów

komunikacyjnych



przy jej pomocy opisano składnię takich

języków programowania jak Fortran

(Backus), czy Algol (Naur)

BNF-przykład



<zero>::=0



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





<ciąg cyfr>::=<cyfra>|<cyfra><ciąg cyfr>



<liczba naturalna>::=<cyfra>|<cyfra

niezerowa><ciąg cyfr>

Oprócz notacji BNF do prezentacji składni

języka można stosować postać graficzną tzw.

diagramy syntaktyczne

Diagramy syntaktyczne-

graficzna postać reguł

produkcji, liczba

naturalna(pierwsza część)

zero

cyfra niezerowa

.....

)

Typy instrukcji



Instrukcja pusta



Instrukcja złożona –jako zamknięty blok innych instrukcji



Instrukcja przypisania
a:=b (różne konwencje znaku przypisania)



Instrukcja warunkowa np.

       if (warunek, test logiczny) then
       (instrukcje 1) else (instrukcje 2) –
       niekiedy brak słów then lub else
       Stosowane operatory porównań oraz logiczne
       typu AND, OR lub NOT



Instrukcje iteracyjne (powtórzeń, pętli) – różne składni zależnie od

typu iteracji (znana liczba powtórzeń, liczbę powtórzeń określa

warunek)



Instrukcje wejścia-wyjścia



Instrukcje wywołania procedur lub funkcji

Procedury i funkcje



wydzielone fragmenty programu o składni zbliżonej

identycznej jak cały program co ma posłużyć tzw.

modularyzacji programu (idea programowania strukturalnego-

wyodrębnienie fragmentów kodu, które następnie mogą być

użyte jako swoiste „czarne skrzynki”)



poza zwiększeniem czytelności kodu programu sprawiają, że

instrukcje raz zapisane mogą być wielokrotnie realizowane

(instrukcja wywołania procedury)



dają praktycznie możliwość wykorzystania rekurencji

(rekursji)

Rekurencja-

polega na odwoływaniu się do obiektu, definicji,

funkcji do samej siebie, w programowaniu najczęściej wiąże

się z tworzeniem tzw. procedur (funkcji) rekurencyjnych, które

w wywołują same siebie

Wybrane pojęcia związane z

tradycyjnym programowaniem-

proste typy danych



liczby całkowite



liczby rzeczywiste



dane znakowe



wartości logiczne

Wybrane pojęcia związane z

tradycyjnym programowaniem-

złożone struktury danych

Związane z implementacją (konkretnym

językiem)



tablice



struktury niejednorodne (np. rekordy)



zbiory

Abstrakcyjne i dynamiczne



stos



listy



kolejki

Zmienne ze względu na

używanie pamięci



zmienne statyczne- zmiennym
przydziela się z góry pewien
obszar pamięci na podstawie ich
typu (wstępnej deklaracji)



zmienne dynamiczne – pamięć
przydzielona na te zmienne może
być rezerwowana i zwalniana w
trakcie działania programu

Szczególny rodzaj danych

-pliki



pliki binarne – dane w pliku to ciąg bajtów bez
względu na zawartość



pliki ogólne- podzielone na tzw. rekordy
logiczne (niekoniecznie równe fizycznym na
dysku) , obecne w licznych językach
programowania



pliki tekstowe –najbardziej rozpowszechniony
standard, plik o strukturze wierszowej,
jednostka podstawową znak ( w ASCII – 1bajt),
różne standardy kodowania znaków sterujących

Paradygmat

programowania

Ogół oczekiwań programisty wobec

języka programowania i komputera,
na którym działa program- innymi
słowy idzie o zbiór mechanizmów
jakich używa programista tworząc
program oraz mechanizmów
związanych z tym jak ten program
jest wykonywany przez komputer

Najważniejsze

paradygmaty

programowania



programowanie imperatywne czyli – sekwencja poleceń

zmieniająca stan maszyny krok po kroku(mimo pewnych

abstrakcji ALGOL,FORTRAN, C,ADA)



programowanie strukturalne (modularne) – program jako

zbiór zamkniętych „kawałków” (procedur, funkcji,

modułów)-także PASCAL, C (rozwijając się)



programowanie obiektowe – program to zbiór

porozumiewających się ze sobą obiektów zawierających

nie tylko instrukcje jak w programowaniu strukturalnym,

ale także dane; obiekty podlegają mechanizmowi

dziedziczenia- C++,JAVA



inne – np. programowanie w logice

Wiele dzisiejszych języków programowania odzwierciedla

kilka paradygmatów programowania jednocześnie

Document Outline