Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
7
1.ZADANIE,ALGORYTM,REPREZENTACJAALGORYTMU
1.1.ZADANIE.DANE.ALGORYTM
1.1.1.Zadanie,informacjaodanych
Jednymzgłównychdziałańrealizowanychmetodamiinarzędziamiinformatykijest
rozwiązywanieróżnychrodzajówzadańobliczeniowychbędącychformą
przetwarzania
informacji.Każdeztychzadańpoleganawytworzeniu,poprzezobliczenia,pożądanych
wynikówdlaokreślonegozbiorudanych.Rozważymykilkaaspektówtakiegopostępowania.
RozpatrzmynastępującyoperatorS:
S
:
X
0ą
Y
(1.1)
gdzie
X-zbiórzawartywpewnejliniowejprzestrzeniXzwanyzbioremwartościdanych
0
zadania,
Y-unormowanaprzestrzeńwartościrozwiązań.
OperatorSnazywamyzadaniem(którenależyrozwiązać).OperatorSmożemyrównież
traktowaćjakoformalnesformułowanieproblemu,którytrzebarozwiązać.
Zatem
S
(x
)
jestwartościąrozwiązaniadladanych
xE
X
0
.
Wartość
S
(x
)
powinniśmywyznaczyćprzypomocywłaściwychdladanegozadaniametod
(algorytmów),którychdladanegozadania(problemu)możebyćwiele.
Niezawszeuzyskaniewartości
S
(x
)
jestmożliwe.Dlategowłaściwympodejściembędzie
rozważeniemożliwościwyznaczenie
8
-przybliżenia
S
(
x
,
8
)
±
y
()
x
wielkości
S
()
x
,tzn.
takiegoelementu
y,dlaktóregozachodzi
()
|
x
^
E
X
o
y
()
x
-
S
()
x
Ś
8
,
8
2
0
(1.2)
przyczym
y
()
x
E
Y
dlakażdego
xE
X
0
.
Zauważmy,żedla
8
±
0
wartości
y
()
|
oraz
S
()
|
niebędąsięróżniływsensienormy.
JeżeliprzestrzeńYbędzieobiektemogólniejszymnp.przestrzeniąmetrycznązmetryką
p
(
a
,
b
),
a
,
b
E
Y
,towyrażenie(1.2)możnaskonstruowaćwoparciuometrykęiprzyjmie
onopostać
x
^
E
X
o
p
(
y
(
x
),
S
(
x
))
Ś
8
,
8
2
0
..
(1.2a)
Powody,dlaktórychwyznaczamywielkość
y,anie
()
|
S
()
|
sąróżne.
Międzyinnymijesttaki,żewyznaczając
y
()
|
częstonieposiadamydokładnychdanych
zadania,lecztylkopewnąinformacjęotychdanych.Częstorównieżwyznaczeniewielkości
S
()
|
jesttrudneizadowalamysięjegopewnymprzybliżeniem,któregojakośćokreśla
wyrażenie(1.2).
Formalnieinformacjęodanychmożemyprzedstawićnastępująco.
Niechdanybędzieoperator
I
:
X
1ą
Z
gdzie
X
0
C
X
1
C
X
Z-zadanaprzestrzeńobiektówopisującychdane.
OperatorIzadanyprzez(1.3)nazywamyoperatoreminformacji.
(1.3)
