načítání...
nákupní košík
Košík

je prázdný
a
b

Kniha: Algoritmy - Piotr Wróblewski

Algoritmy
-11%
sleva

Kniha: Algoritmy
Autor:

Český překlad čtvrtého vydání bestselleru Algorytmy, struktury danych i techniki programowania . Hledáte jako programátoři vhodný algoritmus pro zamýšlený program? Chcete stávající ... (celý popis)
Titul doručujeme za 4 pracovní dny
Vaše cena s DPH:  399 Kč 355
+
-
rozbalKdy zboží dostanu
11,8
bo za nákup
rozbalVýhodné poštovné: 39Kč
rozbalOsobní odběr zdarma

hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%   celkové hodnocení
0 hodnocení + 0 recenzí

Specifikace
Nakladatelství: » Computer press
Médium / forma: Tištěná kniha
Rok vydání: 2015-03-11
Počet stran: 368
Rozměr: 167 x 225 mm
Úprava: 367 stran : ilustrace
Vydání: 1. vyd.
Název originálu: Algorytmy, struktury danych i techniki programowania
Spolupracovali: překlad Jakub Goner
Vazba: brožovaná lepená
ISBN: 9788025141267
EAN: 9788025141267
Ukázka: » zobrazit ukázku
Popis / resumé

Příručka shrnuje základní informace o algoritmech, coby základu každého počítačového programu. Aktualizované vydání. Výklad postupů pro řešení jednotlivých algoritmických problémů, které lze uplatnit při vlastním programování. Pro ilustraci popisovaných řešení je použit jazyk C++. Každá z kapitol obsahuje i praktické příklady, otázky a cvičení.

Popis nakladatele

Český překlad čtvrtého vydání bestselleru Algorytmy, struktury danych i techniki programowania . Hledáte jako programátoři vhodný algoritmus pro zamýšlený program? Chcete stávající koncepci programu optimalizovat? Jste při vývoji omezeni dostupnými technickými prostředky a potřebujete je využívat co nejefektivněji? Neobjevujte Ameriku a použijte ve svých projektech ten správný algoritmus. V aktualizovaném vydání bestselleru se naučíte nejznámější a nejčastěji používané algoritmy. Výklad se neomezuje pouze na suché popisy jednotlivých postupů, seznámíte se i s jejich principy a možnými příklady využití. Při nasazení v praxi pak zvolíte vhodné řešení odpovídající problému a podmínkám. Každá z kapitol obsahuje i praktické příklady, otázky a cvičení, na kterých si můžete čerstvě nabyté znalosti vyzkoušet. Publikace vás mimo jiné naučí: - Analyzovat složitost algoritmů - Optimalizovat vytvořené algoritmy - Využívat vhodné struktury při práci s daty - Zpracovat numerické výpočty - Třídit, řadit a vyhledávat údaje - Využívat nejrůznější metody kódování a komprese - Pracovat s grafy, prohledávat je Čtenáři si mohou na adrese http://knihy.cpress.cz/K2114 pod odkazem Soubory ke stažení stáhnout soubory se zdrojovými kódy použitými v knize. O autorovi: Piotr Wróblewski působil řadu let ve společnostech orientovaných na IT a telekomunikace, psal software na zakázku a vedl počítačová školení. Je autorem několika knih zaměřených na počítače, jeho bestseller Algoritmy vyšel v několika vydáních, a to nejen v Polsku.

Předmětná hesla
Kniha je zařazena v kategoriích
Recenze a komentáře k titulu
Zatím žádné recenze.


Ukázka / obsah
Přepis ukázky

259

KAPITOLA 11

Numerické

algoritmy

Desítky let se počítače používaly primárně a  hlavně

k urychlení výpočtů (mnoho lidí dodnes „počítač“považuje za výkonnější „kalkulačku“). Oblast těchtoaplikací je stále aktuální. Měli bychom si však uvědomit, že

opakované vymýšlení stejných řešení má jen minimální

praktický význam. V uplynulých letech se objevila celá

řada hotových programů, které dokáží řešit typickématematické problémy (např. hledat řešení soustav rovnic, interpolovat a  aproximovat, integrovat

a derivovat, provádět symbolické úpravy atd.). Těm, kdo potřebují používat pokročilématematické funkce, lze tedy doporučit nákup vhodného nástroje, k nimž patří mj. Matlab (http://www.

mathworks.com), Mathcad (http://www.mathsoft .com) nebo Mathematica (http://www.wolfram.

com). Tyto soft warové balíky, které občas mívají i bezplatné verze, se neomezují jen naautomatizaci výpočtů, ale navíc spolupracují s jinými programovacími jazyky a poskytují grafi ckouprezentaci výsledků.

V  této kapitole představíme několik užitečných metod z  oblasti numerických algoritmů, které

lze potenciálně uplatnit v rámci větších programátorských projektů. Nebudeme příliš zabíhat do

matematických důkazů uvedených poznatků, ale pokusíme se ukázat, jakým způsobem je možné

numerický algoritmus převést na spustitelný kód jazyka C++. Podoba algoritmů popsanýchv této kapitole vychází hlavně z těchto prací: skripta [Kla87] dostupného v Polsku a klasického díla

[Knu10]. Čtenářům by však neměly činit potíže ani jiné příručky, které pojednávají o tématunumerických algoritmů, protože jich v posledních letech vyšlo poměrně hodně. Všechny programy

přetištěné v této kapitole je nutné brát jako „výukové“ implementace, které poskytují představu

o využití jazyka C++ při řešení výpočetních úloh. Méně nároční uživatelé je však mohou převzít

jako hotové „kuchařské recepty“.

Vyhledávání nulových bodů funkcí

Matematici dosti často stojí před úkolem vyhledat nulové body funkce. Existuje mnohonumerických metod, které umožňují tento úkol vyřešit pomocí počítače. V této kapitole se omezíme na

jednu z jednodušších – tzv. Newtonovu metodu. Princip této metody zjednodušeně spočíváv systematickém přibližování k nulového bodu pomocí tečen ke křivce, jak je patrné na obrázku 11.1.

V této kapitole:

 Vyhledávání nulových bodů

funkcí

 Iterativní výpočet hodnot

funkce

 Interpolace funkcí

Lagrangeovou metodou

 Derivování funkcí

 Integrování funkcí

Simpsonovou metodou

 Řešení soustav lineárních

rovnic Gaussovou metodou

 Závěrečné poznámky


260

KAPITOLA 11 Numerické algoritmy

Newtonova metoda klade na zkoumanou funkci y = f(x) řadu omezení. V analyzovaném intervalu

[a, b] se například nachází právě jeden kořen, funkce na okrajích intervalu nabývá hodnot lišících

se znaménkem a její první a druhá derivace v tomto intervalu nemění své znaménko.

Obrázek 11.1: Newtonův algoritmus vyhledávání nulových bodů

Z hlediska programátora lze Newtonův algoritmus vyjádřit jako iterativní opakování následujících

operací (i označuje fázi iterace):

 stop, jestliže |f(z

i

)| < ε

Symbol ε označuje určitou kladnou konstantu (např. 0,00001), která zajišťuje, že se algoritmus

zastaví. Úplně na začátku samozřejmě inicializujeme proměnnou z

jistou počáteční hodnotou.

Navíc potřebujeme znát explicitní rovnice f a f‘ (funkci a její první derivaci)

1

.

Navrhněme rekurzivní

2

verzi algoritmu, která jako parametry přijímá mj. ukazatele na funkce

reprezentující f a f‘. Podívejme se na příklad, jak lze pomocí Newtonovy metody vypočítat nulové

body funkce f(x) = 3x

2

 − 2. Procedura nula přesně odráží schéma, které jsme uvedli na začátku:

newton.cpp

const double epsilon=0.0001;

double f(double x) // funkce f(x)=3x^2-2

{

return 3*x*x-2;

}

double fp(double x) // derivace f’(x)=(3x^2-2)’=6x

{

return 6*x;

}

1 Musíme je do kódu programu v C++ zapsat „natvrdo“.

2 Všimněme si, že se jedná o příklad tzv. koncové rekurze, kterou lze přirozeným způsobem převést naalgorit

micky rovnocennou iterativní verzi.

ݖ

ݖൌ

௜ିଵ

݂ሺݖ

௜ିଵ

݂

ሺݖ

௜ିଵ


Iterativní výpočet hodnot funkce

261

double nula(double x0, double(*f)(double), double(*fp)(double) )

{

if(fabs( f(x0) ) <epsilon)

return x0;

else

return nula(x0-f(x0)/fp(x0),f,fp);

}

int main()

{

cout << „Nulový bod funkce 3x*x-2 se rovná „<

// výsledek 0,816497

}

Díky ukazatelům na funkci je procedura nula univerzálnější, ale samozřejmě nic nebrání tomu,

abychom tyto funkce používali přímo.

Iterativní výpočet hodnot funkce

S efektivním postupem výpočtu hodnoty mnohočlenů se seznámíme v kapitole 13, kde popíšeme

tzv. Hornerovo schéma. Nyní se budeme zabývat algoritmem na iterativní výpočet hodnoty funkce,

který se sice v praxi nepoužívá příliš často, ale občas může být užitečný.

Předpokládejme, že nás zajímá jistá funkce y = f(x). Převeďme ji do tzv. implicitní formy:

F(x, y) = 0.

Označme parciální derivaci, která se počítá podle proměnné y, jako F‘

y

(x,  y), kde F‘

y

(x,  y)  ≠  0

v každé iteraci.

S jistým zjednodušením můžeme pomocí Newtonovy metody vypočítat hodnotu pro určité xite

rativním způsobem:

 stop, jestliže |y

n+1

 − y

n

| < ε

Počáteční hodnota y

by měla být co nejbližší hledané hodnotě y.

Problém výpočtu hodnoty funkce f(x) jsme v popsané metodě převedli na hledání nulovéhobo

du funkce F(x, y).

Vý h o dy Newtonovy metody se projevují zvláště u některých funkcí, jejichž kvocient se může (ale

nemusí) značně zjednodušit.

Příklad: Pro y = 1/x máme F(x, y) = x − 1/y a F‘

y

(x, y) = 1/y

2

. Z podmínky F(x, y) = 0 dostáváme

iterativní vzorec y

n+1

 = 2y

n

 − x(y

n

)

2

.

Výše uvedené vzorce lze vyjádřit následujícím programem v jazyce C++:

wartf.cpp

const double epsilon=0.00000001;

double hodn(double x, double yn)

{

double yn1=2*yn-x*yn*yn;

if(fabs(yn-yn1)<epsilon) // fabs = absolutní hodnota

return yn1;

ݕ

௡ାଵ

ݕൌ

ிሺ௫ǡ௬

ങಷ

ങ೤

ிሺ௫ǡ௬ሻ


262

KAPITOLA 11 Numerické algoritmy

else

return hodn(x,yn1);

}

int main()

{

cout << „Funkce y=1/x má pro x=7 hodnotu „<

// výsledek: 14,2857

}

Interpolace funkcí Lagrangeovou metodou

V předchozích částech této kapitoly jsme často využívali explicitní vzorce funkce a její derivace.

Jak ovšem postupovat, disponujeme-li částí grafu funkce (tzn. známe její hodnoty pro konečnou

množinu argumentů), případě by výpočet funkce podle vzorce byl vzhledem k  jeho složitosti

velmi časově náročný? V obou případech si můžeme pomoci metodami tzv. interpolace funkce.

Přitom se k funkci přibližujeme pomocí jednodušší funkce (např. mnohočlenu určeného stupně)

tak, aby interpolační funkce procházela známými body grafu původní funkce (viz obrázek 11.2).

Obrázek 11.2: Interpolace funkce f(x) pomocí mnohočlenu F(x)

V příkladu znázorněném na obrázku máme k dispozici 7 dvojic (x

, y

)... (x

6

, y

6

) a na jejichzá

kladě dokážeme vypočítat mnohočlen F(x), díky němuž lze hodnoty f(x) určovat mnohem snáze

(ačkoli občas mohou být výsledky daleko od pravdy).

Interpolační mnohočlen lze konstruovat pomocí výpočetně náročného Vandermondovadetermi

nantu, který umožňuje najít koefi cienty hledaného mnohočlenu

3

. Pokud nás ovšem zajímá pouze

hodnota funkce v určitém bodě z, existuje prostší a efektivnější Lagrangeova metoda:

Navzdory dosti odstrašující formě lze výše uvedený vzorec snadno převést na kód jazyka C++,

který obsahuje dva vnořené cykly for.

3 Viz např. https://cs.wikipedia.org/wiki/Vandermondova_matice.

ܨሺݖሻ ൌ ሺݔെݖ

ሻሺݔെݖ

ሻǥሺݔെݖ

ሻ෍

ݕ



௝ୀ଴

x

x

1

x

2

x

3

x

4

x

5

x

6

y

y

6

y

x

f(x)

F(x)legenda:

ݔെݖ൫

൯ෑ൫ݔ

ݔെ

௜ୀ଴ǡ௜ஷ௝


Derivování funkcí

263

U následujícího výpisu však hrozí riziko dělení nulou (pokud se hodnota z rovná některémuz uz

lů). Na procvičení můžete uvedenou funkci vylepšit a rozšířit ji o kontrolu vypočítaných hodnot

a příslušnou signalizaci chyb.

interpol.cpp

const int n=3; // stupeň interpolačního mnohočlenu

// pole hodnot funkce (y[i]=f(x[i]))

double x[n+1]={3.0, 5.0, 6.0, 7.0};

double y[n+1]={1.732, 2.236, 2.449, 2.646};

// (ve skutečnosti funkce na výpočet kořene z hodnoty ‚x‘

double interpol(double z, double x[n], double y[n])

{ // vrácení hodnoty funkce v bodě ‚z‘

double wnz=0, om=1, w;

for(int i=0; i<=n; i++)

{

om=om*(z-x[i]);

w=1.0;

for(int j=0; j<=n; j++)

if(i!=j) w=w*(x[i]-x[j]);

wnz=wnz+y[i]/(w*(z-x[i]));

}

return wnz=wnz*om;

}

int main()

{

double z=4.5;

cout << „Funkce sqrt(x) má v bodě „ << z << „ hodnotu „

<< interpol(z,x,y) <

}

Derivování funkcí

V předchozích částech této kapitoly jsme často využívali vzorce funkce a její derivace, které byly

přímo zapsány do kódu C++. Výpočet derivace však občas bývá náročný a pracný. Hodí se proto

metody, které tento problém dokáží vyřešit a obejdou se přitom bez explicitního vzoru funkce.

Mezi oblíbené metody numerického derivování patří tzv. Stirlingův vzorec. Popis jeho odvození

přesahuje rámec této publikace. Předvedeme proto pouze praktické výsledky a do matematických

důkazů se nebudeme pouštět.

Stirlingův vzorec umožňuje jednoduše vypočítat derivace f‘ a f‘‘ v bodě x

pro jistou funkci f(x),

jejíž hodnoty známe v tabulkové formě:

...(x

−2h, f(x

−2h)), (x

−h, f(x

−h)), (x

, f(x

)), (x

+h, f(x

+h)), (x

+2h, ,0f(x

+2h))...

Parametr h je jistý stálý krok v oboru hodnot x.

Stirlingova metoda využívá tzv. pole centrálních rozdílů, jehož konstrukce je znázorněna na obrázku

11.3. Rozdíly δ se počítají shodným způsobem v celém poli, např.:

δ f(x

− 3/2 h) = f(x

− h) − f(x

− 2h) atd.


264

KAPITOLA 11 Numerické algoritmy

Přijmeme-li zjednodušený předpoklad, že budeme vždy počítat derivace pro centrální bod x = x

,

nabývají Stirlingovy vzorce následující podoby:

xf(x)δ f(x)δ

2

f(x)δ

3

f(x)δ

4

f(x)

x

− 2hf(x

− 2h)

− δ f = (x

− 3/2 h)

x

− hf(x

− h) δ

2

f(x

− h)

δ f = (x

− 1/2 h)δ

3

f = (x

− 1/2 h)

x

f(x

) δ

2

f(x

4

f(x

)

δ f = (x

+ 1/2 h)δ

3

f = (x

+ 1/2 h)

x

+ hf(x

+ h) δ

2

f(x

+ h)

δ f = (x

+ 3/2 h)

x

+ 2hf(x0 + 2h)

Obrázek 11.3: Pole centrálních rozdílů v Stirlingově metodě

Kontrolních bodů funkce může být samozřejmě mnohem více než 5. Zde se zaměříme na velmi

jednoduchý příklad s pěti hodnotami funkce, který vede k poli centrálních rozdílů nízkého řádu.

Vzorový program v C++, který počítá derivace určité funkce f(x), může vypadat takto:

pochodna.cpp

const int n=5; // řád počítaných centrálních rozdílů činí n-1

double t[n][n+1]=

{

{0.8, 4.80}, // dvojice (x[i], y[i]) pro y=5x*x+2*x

{0.9, 5.85}, // (zapsané jsou dva první sloupce, a nikoli řádky)

{1, 7.00},

{1.1, 8.25},

{1.2, 9.60}

};

struct DERIVACE{double f1,f2;};

DERIVACE stirling(double t[n][n+1])

// funkce vrací hodnoty f‘(z) a f‘‘(z), kde z je centrálním

// prvkem: zde t[2][0]; pole ‚t‘ je nutné předtím centrálně

݂

ᇱሺ௫ሻ

ͳ

݄

െݔቀ݂ߜ

ͳ

ʹ

൅ݔቀ݂ߜቁ൅݄

ͳ

ʹ

ቁ݄

ʹ

ͳ

͸

ߜ

െݔቀ݂

ͳ

ʹ

ߜቁ൅݄

൅ݔቀ݂

ͳ

ʹ

ቁ݄

ʹ

ͳ

͵Ͳ

ߜ

െݔቀ݂

ͳ

ʹ

ߜቁ൅݄

൅ݔቀ݂

ͳ

ʹ

ቁ݄

ʹ

ቍڮ൅

݂

ᇱᇱ

ሺݔሻ ൌ

ͳ

݄

ߜ൬

݂ሺݔሻ ൅

ͳ

ͳʹ

ߜ

݂ሺݔሻ െ

ͳ

ͻͲ

ߜ

݂ሺݔሻ ൰ڮ൅


Integrování funkcí Simpsonovou metodou

265

// inicializovat, jeho správnost se nekontroluje

{

DERIVACE res;

double h=(t[4][0]-t[0][0])/(double)(n-1); // krok argumentu ‚x‘

for(int j=2;j<=n;j++)

for(int i=0;i<=n-j;i++)

t[i][j]=t[i+1][j-1]-t[i][j-1];

res.f1=((t[1][2]+t[2][2])/2.0-(t[0][4]+t[1][4])/12.0)/h;

res.f2=(t[1][3]-t[0][5]/12.0)/(h*h);

return res;

}

int main()

{

DERIVACE res=stirling(t);

cout << „f‘=“ << res.f1 << „, f‘‘=“ << res.f2 <

} Když se už zabýváme numerickým derivováním, měli bychom zdůraznit, že je poměrně nepřesné. Čím je hodnota parametru h menší, tím větší vliv na výsledek mají chyby zaokrouhlení.Zvětšování parametru h však odporuje ideji Stirlingovy metody (která má přece napodobovat skutečné derivování!). Stirlingova metoda se nehodí k derivování na okrajích intervalů proměnlivostiargumentu funkce. Pokud vás toto téma zajímá, můžete najít další informace v příslušné literatuře. Téma je totiž širší, než se může zdát. Integrování funkcí Simpsonovou metodou Některé funkce se těžko integrují, protože výpočet jejich integrálu je dosti symbolicky náročný. Abychom dostali požadovaný výsledek, musíme občas provést hodně obtížných transformací (např. substituce, rozklady na posloupnosti atp.). Můžeme si však pomoci interpolačními metodami (které komplikovanou funkci nahradí přibližnou a výpočetně jednodušší formou). Princip numerického integrování je znázorněn na obrázku 11.4. Obrázek 11.4: Přibližné integrování funkce

Legenda: interpolační parabola

křivka integrandu




       
Knihkupectví Knihy.ABZ.cz - online prodej | ABZ Knihy, a.s.
ABZ knihy, a.s.
 
 
 

Knihy.ABZ.cz - knihkupectví online -  © 2004-2018 - ABZ ABZ knihy, a.s. TOPlist