Přípravný kurz informatiky

Vysoké učení technické v Brně Fakulta informačních technologií

Přípravný kurz informatiky Příručka

Autoři

Roman Bílek Radek Burget Luděk Haša Vladimír Kutálek Daniel Mika Jiří Petřek David Řezáč Jiří Staroba Dalibor Zacios

Editoři

Josef Schwarz, David Řezáč

Vydavatel

c FIT VUT Brno, 2002–2003

Vydání

Druhé, revidované

Publikace je určena pouze pro vnitřní potřebu FIT VUT Brno. Vysázeno systémem LATEX

Obsah

5

Obsah Obsah

5

Předmluva

7

1 Základní pojmy z oblasti počítačů a internetu 1.1 Vývoj počítačů . . . . . . . . . . . . . . . . . . 1.2 Von Neumannova architektura počítače . . . . . 1.3 Informatika a informace . . . . . . . . . . . . . 1.4 Internet . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

9 9 10 11 12

2 Hardware a software 2.1 Úvod . . . . . . . . . . . . . . . . . . . . 2.2 Základní prvky počítače . . . . . . . . . 2.3 Základní jednotka . . . . . . . . . . . . . 2.4 Monitor . . . . . . . . . . . . . . . . . . 2.5 Klávesnice . . . . . . . . . . . . . . . . . 2.6 Myš . . . . . . . . . . . . . . . . . . . . 2.7 Skener . . . . . . . . . . . . . . . . . . . 2.8 Tiskárny . . . . . . . . . . . . . . . . . . 2.9 Programovací jazyky . . . . . . . . . . . 2.10 Přehled programovacích jazyků . . . . . 2.11 Příklady vyšších programovacích jazyků 2.12 Překladač . . . . . . . . . . . . . . . . . 2.13 Interpretované programovací jazyky . . . 2.14 Operační systémy . . . . . . . . . . . . . 2.15 Aplikační software . . . . . . . . . . . . 2.16 Multimediální software . . . . . . . . . . 2.17 Software pro INTERNET . . . . . . . . 2.18 Kontrolní otázky . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

15 15 15 15 18 19 20 20 20 21 22 22 23 23 24 26 27 27 28

. . . .

31 31 31 34 35

3 Číselné soustavy 3.1 Úvod . . . . . . 3.2 Celá čísla . . . 3.3 Desetinná čísla 3.4 Výpočty . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6

Přípravný kurz informatiky 3.5

Příklady k procvičení . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Datové typy 4.1 Úvod . . . . . . . . . . . . . 4.2 Standardní datové typy . . . 4.3 Uživatelem definované typy 4.4 Příklady k procvičení . . . .

36

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

37 37 38 40 40

5 Aritmetické a logické výrazy, posloupnosti 5.1 Úvod . . . . . . . . . . . . . . . . . . . . . 5.2 Aritmetické výrazy . . . . . . . . . . . . . 5.3 Logické výrazy . . . . . . . . . . . . . . . 5.4 Číselné posloupnosti . . . . . . . . . . . . 5.5 Příklady k procvičení . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

41 41 41 43 50 52

. . . . . . . .

54 54 54 56 61 62 63 64 72

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6 Algoritmy 6.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . 6.2 Co je algoritmus . . . . . . . . . . . . . . . . . 6.3 Návrh programu . . . . . . . . . . . . . . . . . 6.4 Programování . . . . . . . . . . . . . . . . . . 6.5 Slovníček důležitých pojmů z oblasti algoritmů 6.6 Kontrolní otázky . . . . . . . . . . . . . . . . 6.7 Vybrané algoritmy . . . . . . . . . . . . . . . 6.8 Příklady k procvičení . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

Předmluva

7

Předmluva Tato příručka je určena uchazečům o studium na Fakultě informačních technologií VUT v Brně, kteří se přihlásili do přípravného kurzu pro přijímací zkoušku z informatiky. Účelem kurzu je seznámit studenty se základy programového a technického vybavení počítačů. Učební text připravili studenti doktorského studijního programu FIT VUT, kteří budou v přípravném kurzu přednášet. Upozorňujeme, že jde pouze o doprovodný učební text ke kurzu informatiky. Jeho obsah i forma odrážejí záměr autorů – vysvětlit základní pojmy tohoto oboru v rozsahu, který se vyučuje na některých středních školách, aby byli absolventi tohoto kurzu co nejlépe připraveni na přijímací zkoušku z informatiky na FIT VUT. Autoři

8

Přípravný kurz informatiky

1. Základní pojmy z oblasti počítačů a internetu

9

Kapitola 1 Základní pojmy z oblasti počítačů a internetu 1.1

Vývoj počítačů

Až do 80. let převládala klasifikace počítačů do tzv. generací, kde každá generace je charakteristická svou konfigurací, rychlostí počítače a základními stavebními prvky. Vznikly čtyři generace, ale už během třetí generace tato klasifikace začala selhávat, proto se klasifikace počítačů v současné době opírá především o výkonnost. První počítače obsahovaly reléové a elektronkové součástky. Charakterizoval je velký příkon, velká poruchovost, vysoká cena a malá rychlost. Program se psal přímo ve strojovém kódu, zpočátku se sestavoval na propojovacích deskách, později se zaváděl z děrné pásky nebo děrných štítků. Počítače se využívaly k numerickým výpočtům. Operační systémy ani programovací jazyky neexistovaly. Počítače druhé generace (1955 až 1965) začaly používat tranzistor, což vedlo ke zlepšení všech parametrů. Programy jsou psané v jazyce symbolických adres, ve Fortranu, Cobolu, Algolu. Jsou vyvinuty první operační systémy. V počítačích třetí generace (1965 až 1980) se začínají používat integrované obvody. Vedle velkých střediskových počítačů (mainframes) vznikají minipočítače a první mikropočítače. Zavádí se multiprogramování a multitasking. Multiprogramování – dokud jeden proces čeká na provedení vstup/výstupní operace, druhý proces je zpracováván procesorem, kde proces je vykonávaný program. Multitasking – pokud není procesu odebrán procesor, protože nezačal provádět vstup/výstupní operaci, je mu procesor odebrán po uplynutí jistého časového intervalu a přidělen jinému procesu. U počítačů čtvrté generace (od roku 1980) dochází k výraznému nárůstu spolehlivosti. Dochází k velkému rozšíření osobních počítačů. Pro náročnější úlohy se používají pracovní stanice, dochází k ústupu od střediskových počítačů, a tím k poklesu ceny a ke zvýšení dostupnosti počítačů. Vznikají víceprocesorové systémy a rozšiřují se počítačové sítě (počítače propojené sítí) a distribuované systémy (celá síť se chová jako jediný výpočetní prostředek). V současné době se počítače a mikroprocesory rozšiřují do všech odvětví lidské činnosti. V podobě embedded systémů lze se s nimi setkat i v zařízeních, kde by to člověk ani nečekal. Embdeded (vestavěné) systémy jsou tvořeny mikroprocesorem a

10


pamětí s programem a jsou součástí jiného zařízení nebo stroje pro vykonávání určité funkce. Osobní počítače se staly běžným pomocníkem a nástrojem pro efektivní řešení různých úloh. Dále se však používají i výkonnější počítače, jako jsou pracovní stanice, minipočítače atd. Používají se clustery počítačů – skupina vzájemně propojených počítačů, které pracují jako jeden paralelní počítač. Počítače lze podle výkonnosti rozdělit: • Osobní počítače – jsou to jednouživatelské mikroprocesorové počítače. Jsou nejrozšířenější a nejdostupnější. Používají se např. pro zpracování kancelářských a ekonomických agend, pro připojení k Internetu, mnohdy k hraní her. Také lze mezi ně zahrnout kapesní počítače PDA (Personal Digital Assistant). • Pracovní stanice – jsou také většinou jednouživatelské. Používají se pro náročnější aplikace (CAD, navrhování), pro grafické aplikace, pro aplikace, které potřebují větší výpočetní sílu. Mohou být i víceprocesorové. • Minipočítače – víceuživatelské počítače. Počet uživatelů se pohybuje mezi 10 až 100. • Sálové počítače – jsou to velké nákladné sálové počítače pro stovky uživatelů. Používají je výpočetní střediska. • Superpočítače – jsou nejrychlejší a nejdražší počítače. Jsou vyvinuty tak, aby určité úlohy spočítaly co nejrychleji. Tím se liší od sálových počítačů, které jsou vyvinuty tak, aby obsloužily co nejvíce úloh najednou. Používají se pro simulace, vědecké výpočty, vojenské výpočty apod.

1.2

Von Neumannova architektura počítače

Za první elektronický počítač je považován elektronkový počítač ENIAC (Electronic Numerical Integrator and Calculator), který byl postaven na Universitě státu Pensylvánie v roce 1946. Tento počítač se programoval drátovými propojkami a přepínači, data se zadávala pomocí děrných štítků. Až druhý počítač, dokončený v roce 1952 na stejné univerzitě s označením EDVAC, byl již řízen programem uloženým v paměti. Jeho koncepce se stala nejrozšířenější a nejznámější počítačovou architekturou. Jedním z jeho hlavních tvůrců byl matematik John von Neumann, podle něhož se tato koncepce nazývá – von Neumannova. Na obrázku 1.1 lze vidět strukturu von Neumannova počítače. Počítač je tvořen pamětí, aritmeticko-logickou jednotkou (ALU), řadičem a bloky vstupů a výstupů. ALU s řadičem tvoří procesor. Vnitřní struktura počítače se nemění v závislosti na zpracovávané úloze. Vnitřní struktura musí být maximálně univerzální, tak, aby dokázala vyjít vstříc potřebám úloh nejrůznějšího typu. Veškeré přizpůsobení konkrétním úkolům je řešeno výhradně programem. Program P je tvořen posloupností instrukcí. Instrukce programu I jsou prováděny sekvenčně, jedna za druhou. Program se při jeho běhu zpravidla nemodifikuje, data D lze během programu modifikovat. Instrukce programu jsou uloženy v jedné paměti


11

společně s daty. Instrukce i data jsou zakódovány binárně do posloupností nul a jedniček. Paměť tvoří jednotlivá paměťová místa, do kterých lze zapisovat nebo z nich číst po zadání příslušné adresy paměťového místa.

Obr. 1.1: Von Neumanova architektura počítače

Vytvoření von Neumannovy architektury představuje velmi důležitý počin pro vývoj výpočetní techniky. Tato architektura se stala nejrozšířenější, její principy se používají dodnes a má ji většina současných počítačů. Existují však i alternativní architektury: Harvardská koncepce – oddělená paměť pro program a pro data (dnes ji používají např. některé jednočipové mikropočítače). Data-flow koncepce – provádění programu je řízeno tokem dat.

1.3

Informatika a informace

Informatika (computer science) je matematická disciplína, zabývající se strukturou, zpracováním a využitím informací. Zpracováním informace se rozumí jejich získání, ukládání, zobrazení, třídění, přenos, vyhledávání, rozšiřování atd. Informace je vše, co podává zprávu o věcech nebo událostech, které se staly nebo které nastanou. Množství informace ve zprávě je dáno pravděpodobností výskytu této informace ve zprávě. Čím menší je tato pravděpodobnost, tím vyšší je množství informace ve zprávě. V běžném životě informace získáváme neustále svými smysly. Většinou však pojmem informace chápeme znalosti a intelektuální poznatky. Tyto poznatky získáváme např. slovním sdělením (komunikace s lidmi, výklad ve škole, poslech rozhlasu), obrazovým sdělením (televize, video), četbou (knihy, noviny), pomocí výpočetní techniky (Internet, CD-ROMy, databáze). K informatice patří např. tyto disciplíny: • teorie informace, • formální logika,

12

Přípravný kurz informatiky • teorie automatů, formálních jazyků a gramatik, • kybernetika a robotika, • umělá inteligence, • počítačová simulace, • počítačová grafika, • programování, • výpočetní technika.

V počítačích jsou všechny informace kódovány ve dvojkové soustavě, jsou tedy reprezentovány posloupností nul a jedniček. Nejmenší jednotka informace v počítači je jeden bit (značka b), tento bit potom reprezentuje hodnotu 0 nebo 1. Tvůrci počítačů se shodli, že na zakódování základních znaků bude použito osm bitů. Pomocí těchto osmi bitů označovaných jako 1 bajt (angl. byte, značka B, 1B = 8b) lze zakódovat 256 znaků (28 ). Jelikož jednotka bajt je příliš malá, používají se tyto její násobky: • 1 KB (kilobajt) = 210 B = 1 024 B • 1 MB (megabajt) = 220 B = 1 048 576 B • 1 GB (gigabajt) = 230 B = 1 073 741 824 B • 1 TB (terabajt) = 240 B = 1 099 511 627 776 B V praxi se často používá 1 MB = 1 000 KB, 1 GB = 1 000 MB. Proto pro odlišení byly zavedeny pro binární hodnoty jednotky KiB, MiB, GiB, TiB. Tyto jednotky se však zatím příliš nerozšířily.

1.4

Internet

Internet je celosvětová soustava vzájemně propojených počítačových sítí. Počítačovou síť tvoří několik vzájemně propojených počítačů. Internet nikdo nevlastní, své vlastníky mají pouze dílčí sítě. Přístup k Internetu, díky jeho službám, přináší hlavně kvalitní komunikaci mezi jeho uživateli a velké množství informací, také však zábavu a relaxaci. Internet vznikl na bázi počítačové sítě Arpanet. Šlo o experimentální projekt amerického ministerstva obrany. Tento projekt se hlavně zaměřil na sdílení síťových zdrojů. Hlavní snahou byl požadavek, aby síť mohla fungovat i při výpadku některých počítačů v síti zničených v případné nukleární válce. Proto byla vyvinuta síť, kde odpojení určité části počítačů neovlivnilo chod zbytku sítě. V roce 1969 došlo k propojení prvních čtyř počítačů na amerických univerzitách. Později byly připojeny další počítače a v roce 1973 došlo k připojení prvních počítačů mimo USA. Na rozdíl


13

od původního záměru, kdy měl sloužit Arpanet pro vojenské účely, se Arpanet stal velmi populární sítí zejména mezi vědci a studenty, kteří kromě pracovních úkolů používali síť hlavně pro vzájemnou komunikaci. Síť se rozšiřovala, stala se plně mezinárodní a začalo se jí říkat Internet. Internet byl nejdříve využíván hlavně ve školství a vědě. Proto byly odmítány veškeré komerční aktivity a následovaly bojkoty a protesty proti těmto pokusům. Rozvoj komerčních aktiv nastal až v roce 1991. V tomtéž roce přichází na Internet služba World Wide Web (WWW), která slouží k přenosu hypertextových a grafických informací. Díky WWW se Internet stal přístupný nejen pro počítačové fandy a akademickou obec, ale i pro uživatele, kteří s počítači nemají mnoho společného. Všechny standardy Internetu byly a jsou vydávány ve formě dokumentů RFC (Request for Comment), které jsou volně dostupné a šiřitelné. Tato dostupnost velmi pomohla popularitě Internetu, jelikož umožnila komukoliv implementaci a vývoj nástrojů pro Internet. Internet poskytuje mnoho služeb. K hlavním službám patří: E-mail – elektronická pošta (vznik 1971). Telnet – služba pro připojení k vzdálenému počítači (1972). FTP – služba pro přenos souborů po síti (file transfer protocol – 1973). IRC (Internet Relay Chat) – služba pro živou komunikaci účastníků. Umožňuje komunikovat více uživatelům současně (1988). Gopher – informační a vyhledávací systém. Informace jsou uloženy pouze v textové podobě (1991). WWW (World Wide Web) – služba pro zpřístupnění hypertextových a grafických informací a dokumentů. Dokumenty mohou obsahovat odkazy na jiné dokumenty, obrázky, multimediální záznamy, databázové aplikace, informační servery, apod. Nejoblíbenější a nejpoužívanější služba Internetu, která zapříčinila jeho prudký rozvoj (1991).

14


2. Hardware a software

15

Kapitola 2 Hardware a software 2.1

Úvod

V této kapitole se budeme zabývat pojmy z oblasti technického (hardware) a programového vybavení osobních počítačů (software). Patří sem veškeré součástky vytvářející počítač a také periferie připojené k počítači – klávesnice, myši, tiskárny, monitory, atd. Hardwarem počítače laicky rozumíme všechno to, na co si může uživatel sáhnout. Samotný hardware ovšem k efektivní práci nestačí. Počítač je potřeba nějakým způsobem řídit. K tomu slouží programové vybavení počítače zvané software. Základním programovým vybavením je operační systém, který se stará o komunikaci uživatele s hardwarem. Služeb operačního systému využívají ostatní programy. Pomocí těchto uživatelských programů můžeme psát texty, vytvářet tabulky, grafy, provádět výpočty, připojit se na internet, přehrát si uložené video, spustit si oblíbenou hudbu a mnohé jiné akce.

2.2

Základní prvky počítače

Nejjednodušší sestava počítače se skládá z monitoru, klávesnice, základní jednotky a myši. K počítači mohou být připojeny i jiné periferie – tiskárna, joystick, skener, reproduktory, plotr či nějaká jiná speciální zařízení (např. sonda měření emisí apod.).

2.3

Základní jednotka

Základní jednotka PC (Personal Computer) je uzavřena do skříně počítače. Skříň počítače zpravidla obsahuje tyto komponenty: základní desku, procesor, operační paměť, mechaniku pružných disků, pevný disk, mechaniku CD-ROM, grafickou kartu, zvukovou kartu, síťovou kartu, řadič disků, napájecí zdroj, propojovací kabel.

2.3.1

Základní deska

Základní deska je konstrukční celek obsahující základní elektronické obvody počítače zobrazené na blokovém schématu.

16


Obr. 2.1: Blokové schéma základní desky počítače

2.3.2

Procesor

Procesor je integrovaný číslicový obvod, který do jisté míry řídí činnost všech ostatních fyzických zařízení počítače. Obsahuje funkční jednotky pro výpočet aritmetických a logických operací, paměťová místa označovaná jako registry a pomocné obvody sloužící k řídící činnosti. Rychlost procesoru ovlivňuje výkon celého počítače. Takt procesoru se udává v hertzích; je to jednotka udávající počet základních impulsů procesoru za sekundu. Každý impuls může znamenat provedení jedné elementární instrukce na nejnižší úrovni procesoru. Frekvence dnešních procesorů dosahují řádově několika GHz (giga hertz).

2.3.3

Operační paměť

Operační paměť má k dispozici procesor pro uložení programů a výsledků. Je zde uložen program (nebo jeho část), kterým je řízen procesor. Důležitým parametrem je kapacita paměti. Čím větší paměť, tím větší množství dat lze v jednom okamžiku uložit. Jednotkou kapacity paměti je B (Byte). Byte je složen z 8 bitů. Bit je prostor pro uložení základní informace – nuly nebo jedničky. Současná kapacita operační paměti osobních počítačů se udává v MB (megabytech, 1 MB = 1024 kB = 1024 x 1024 B). Operační paměť se v počítačové terminologii označuje jako RAM (Random Access Memory – paměť s libovolným přístupem). Správné označení by ale mělo být RWM (Read Write Memory – paměť pro čtení a zápis), neboť je takto skutečně používána.


17

RAM je energeticky závislá, tzn. po vypnutí počítače ztrácí svůj obsah (narozdíl od dalších typů pamětí zmíněných dále).

2.3.4

Mechanika pružných disků

Pružné disky patří mezi přenosná média pro uchování dat. Pružný disk je tvořen plastovým kotoučem, na jehož povrchu je tenká vrstva magnetického materiálu. Celý kotouč je uzavřen v plastovém obdélníkovém pouzdře. Záznam dat na médium je prováděn magneticky. Jednotlivá data jsou zapisována do soustředných kružnic, tzv. stop (tracks), na obě strany diskety. Každá stopa je rozdělena ještě na tzv. sektory (sectors), jež tvoří nejmenší úsek média, na který je možné zapisovat a číst z něho.

Obr. 2.2: Sektory a stopy na disku

2.3.5

Pevné disky

Pevné disky jsou média pro uchování dat s vysokou kapacitou záznamu. V současnosti jsou pevné disky standardní součástí každého PC. Jedná se o pevně uzavřenou jednotku umístěnou v počítači. Uvnitř této jednotky se nachází několik nad sebou umístěných rotujících kotoučů (disků). Tyto disky se otáčejí po dobu, kdy je pevný disk připojen ke zdroji elektrického napájení a čte se z něj nebo se na něj zapisují data. Rychlost otáčení bývá 3 600 až 15 000 otáček za minutu.

2.3.6

CD-ROM

Výhodou těchto médií je velká kapacita, která dnes dosahuje hodnot 650 MB (74 minut u audio nahrávky), 700 MB (80 minut) nebo až 870 MB (99 minut). Princip práce mechaniky je jiný než u pevných disků, není totiž založen na magnetickém jevu, ale využívá laserové techniky. Podle toho, zda se světlo laserového paprsku odrazí (nebo neodrazí) od povrchu disku a aktivuje fotocitlivou diodu, rozpozná elektronika CD mechaniky, zda na příslušném místě disku byla zapsána 1 nebo 0. Na CD ovšem

18


nejsou data uložena přímo, ale s využitím kódů umožňujících opravu v případě (mírného) poškození média. Podrobný popis poměrně složitého způsobu uložení dat na CD překračuje rámec této příručky a je možné jej nalézt na internetu.1 Existují též varianty CD-R a CD-RW, které umožňují jednou (resp. vícekrát) zapsat data na médium. Při zápisu na CD-R se ohřeje organické barvivo na médiu; CD-RW funguje na principu fázové změny.

2.3.7

Grafická karta

Grafická karta je speciální deska s elektronickými obvody, která se zasunuje do rozšiřujícího slotu (konektoru na sběrnici) na základní desce. Za účasti procesoru generuje signály pro monitor a vytváří na monitoru obraz. V některých případech je videokarta integrována přímo na základní desce počítače. Obraz může být buď v textovém režimu (na monitoru se zobrazují znaky) nebo v režimu grafickém (obrazovka monitoru je chápána jako plocha o určitém počtu bodů – každý bod má svou pozici a barvu). Zobrazovací jednotka má schopnost vygenerovat určitou škálu barev. Maximální možný počet všech odstínů je dán hlavně velikostí paměti videoadaptéru. Obecně platí, že větší paměť dovoluje současně zobrazit větší počet odstínů. V souvislosti s tím, kolik obrazových bodů (pixelů) je schopná daná grafická karta (a monitor) zobrazit mluvíme o rozlišení obrazovky. První grafické adaptéry měly rozlišení 320x200 pixelů (CGA), pokrok však šel rychle kupředu. Po nástupu grafických karet typu EGA a VGA (640x480 bodů) přišly na řadu karty s rozlišením 800x600 nebo 1024x768 (SVGA), a nyní je běžné rozlišení 1280x1024 nebo 1600x1200 pixelů.

2.3.8

Zvuková karta

Zvuková karta je určena pro zpracování zvukového signálu. Stejně jako ostatní karty se může zasunout do příslušné pozice konektoru sběrnice. Posledním trendem výroby základních desek je integrovat zvukovou kartu přímo na základní desku. Ke zvukové kartě se připojují reproduktory, mikrofon apod. Obvykle se setkáme se dvěma reproduktory, ale pokud chceme vytvořit dojem prostorového zvuku, používá se více reproduktorů.

2.3.9

Síťová karta

Jedná se o speciální desku, která umožňuje propojit více počítačů. Propojení počítačů nazýváme sítí. Tato karta se stará o vysílání a přijímání signálů mezi účastníky sítě. Nejběžnější rychlosti přenosu jsou 10 Mbitů a 100 Mbitů za sekundu.

2.4

Monitor

Úkolem monitoru je obrazová komunikace mezi obsluhou a počítačem. Monitor nás vizuálně informuje o tom, co se v počítači právě děje. To, co na monitoru vidíme, 1

Např. na stránkách http://www.cdr.cz nebo http://www.cdrfaq.org (květen 2003).


19

vytváří grafická karta. Monitory rozdělujeme podle několika kritérií. Prvním dělícím kritériem je velikost obrazovky. Ta se obvykle udává v anglické míře v palcích. Většina dnešních monitorů má uhlopříčku o velikosti 15 nebo 17 palců. Existují monitory menší (14”, 13”), ale i větší (19”, 20”, 21”). Monitory lze rozdělit i podle konstrukce. Setkáme se s klasickou obrazovkovou konstrukcí obdobnou televizní (CRT) nebo s principem zobrazování pomocí tekutých krystalů (LCD).

Obr. 2.3: Obrazovka

Podle zobrazených barev dělíme monitory na monochromatické a barevné. Celkový obraz se skládá z jednotlivých bodů obrazovky. U barevného monitoru se barva každého bodu vytváří součtově, tzn. že jeden bod je reprezentován trojicí barev (R – červená, G – zelená a B – modrá). Tyto barvy jsou situovány těsně vedle sebe, a tak je lidské oko vnímá jako jeden barevný bod. V současnosti začínají klasické CRT monitory vytlačovat LCD monitory, které ovšem fungují na jiném principu. Jejich výhodou oproti klasickým monitorům jsou mnohem menší rozměry, hmotnost a nižší energetické nároky.

2.5

Klávesnice

Jde o jedno z nejstarších textových (pouze pro vstup textu) vstupních zařízení. Slouží k zadávání pokynů pro počítač. Skládá se ze soustavy tlačítek (písmena, číslice nebo speciální znaky). Po stisku klávesy je vygenerován příslušný kód a ten je odeslán do počítače. Počítač tento kód přijme a dále zpracuje (nejčastěji zobrazí znak odpovídajícího kódu na displeji).

20

2.6


Myš

Je to standardní grafické (pro vstup dvourozměrné grafické informace) vstupní periferní zařízení. Je s počítačem spojeno přes sériový port nebo rozhraní USB (Universal Serial Bus) nebo pomocí konektoru PS/2. Lze použít i spojení pomocí rádiových vln. Klasická myš má v sobě zabudovanou kuličku. Pohyb kuličky generuje signály a ty zpracovává procesor uvnitř počítače.

2.7

Skener

Grafické vstupní zařízení, které na optickém principu převádí texty, fotografie či diapozitivy do digitální podoby, s nimiž umí pracovat PC. Snímaná předloha je osvětlena a od ní odražené světlo dopadá na světlocitlivý snímač CCD (Charge Coupled Device). CCD je integrovaný obvod s řadou světelných senzorů. Výstupní napětí každého senzoru je úměrné množství dopadajícího světla a je následně digitalizováno.

2.8

Tiskárny

Jsou to nejrozšířenější periférie, tisknou údaje z počítače na papír nebo jiná média (fólie, samolepky, obálky, . . . ). Jsou textové i grafické, případně pracují v obou režimech.

2.8.1

Jehličková tiskárna

Základním konstrukčním prvkem je tisková hlava, v níž je zasazena skupina jehliček. Tisková hlava se pohybuje zleva doprava. Tam, kde se má otisknout bod, se vysune z tiskové hlavy jehlička a dotkne se papíru. Protože mezi jehličkou a papírem je barvící páska, výsledný bod se zobrazí na papíře. Množina vytištěných bodů představuje znak (u textových tiskáren) nebo obrázek (u tiskáren grafických).

2.8.2

Inkoustová tiskárna

Princip tisku je podobný jehličkové technologii. Nad svisle se pohybujícím papírem přejíždí ve vodorovném směru tisková hlava. Ta je osazena miniaturními tryskami, do nichž se přivádí speciální inkoust, který je z trysek vytlačen pomocí membrány piezoelektrického měniče a jako drobounká kapička pak vystříkne na papír. Obraz či text jsou na papíře složeny z malých teček. Inkoustová hlava má však k dispozici více trysek, než bylo jehliček u jehličkové technologie, navíc se inkoust na papíře nepatrně rozpije a kapičky se slijí do rovnoměrného obrazu. Výsledkem je velice kvalitní výstup.

2.8.3

Laserová tiskárna

Vychází se z elektrostatického principu: opačně polarizované náboje se přitahují. Základem technologie je světlocitlivý válec. Ten je před začátkem tisku nabit kladným


21

nábojem. Otáčí se konstantní rychlostí a je postupně osvětlován laserovým paprskem, který příslušná tisková místa vybíjí. Tato místa válce přitahují kladně nabitý toner (velmi jemný prášek skládající se z umělé hmoty, barviva a železa). Z válce se toner obtiskne na papír, do kterého je za vysoké teploty zažehlen.

Obr. 2.4: Princip laserové tiskárny

2.9

Programovací jazyky

Komunikační schopnost počítačů a lidí je doposud velmi rozdílná. Zprvu se pro zadávání nových postupů – algoritmů – používal strojový kód, který vycházel z jazyka počítačů. Protože i počítače se liší, existují samozřejmě i různé strojové kódy. Všechny příkazy i zadávaná data byla tedy reprezentována čísly. Pokud chtěl programátor vytvořit nový program, musel jej převést na soustavu čísel, které zadal do počítače. Tento způsob byl však málo efektivní. Proto bylo nutné vymyslet, jak by tuto činnost bylo možné zjednodušit. Pro lidi je jednodušší, mohou-li komunikovat slovy. Proto byly nejprve jednotlivým instrukcím v číselném tvaru přiřazeny jejich slovní mnemotechnické významy. Tak vznikl strojově orientovaný programovací jazyk. Počítač však stále rozuměl jen číslům, proto bylo nutné vytvořit program – překladač, který by zápis v tomto programovacím jazyce převedl zpět na soustavu čísel. Další vývoj směřoval k programovacím jazykům více nezávislým na strojovém kódu. Vznikly vyšší programovací jazyky – nejznámější jsou Fortran, Basic, Pascal, C, C++.

22


2.10

Přehled programovacích jazyků

2.10.1

Strojově orientované jazyky – assemblery

Tyto jazyky ve své podstatě jsou jen mnemotechnickým vyjádřením strojového kódu. I když existují různé implementace, které obsahují i podporu pro objektově orientované programování, ztrácejí tyto jazyky na popularitě. Svůj význam měly při vytváření výpočetně náročných částí programu. V dobách, kdy byly počítače daleko méně výkonné, mělo svou cenu v tomto jazyku psát i celé aplikace. Jejich nevýhodou je závislost na typu procesoru. Navíc neustále rostoucí výkon počítačů a stále se zlepšující optimalizační techniky používané v překladačích vyšších programovacích jazyků výhody strojově orientovaných jazyků značně eliminují. Často se setkáváme s označením těchto jazyků slovem assembler, i když správně toto slovo označuje překladač (viz dále) ze strojově orientovaného jazyka do strojového kódu. Nevýhodou je, že pro každý typ počítače je assembler jiný.

2.10.2

Vyšší programovací jazyky

Vyšší programovací jazyky lze rozdělit na imperativní, deklarativní. Imperativní programovací jazyk se vyznačuje tím, že v něm programátor přímo popisuje způsob řešení daného problému – tj. algoritmus. Nejznámějšími příklady imperativního programovacího jazyka jsou právě Basic, Pascal či C. Dále existují deklarativní jazyky, které popisují pouze problém (to, co se má řešit) a nikoliv výpočetní mechanismus (jak se to má řešit). Používají se např. v oblasti umělé inteligence nebo databází, a příkladem mohou být Lisp, Prolog nebo SQL.

2.11

Příklady vyšších programovacích jazyků

Basic – tento programovací jazyk existuje v mnoha variantách. Většinou se jedná o jednoduchý interpretovaný (viz dále) jazyk obsahující jen příkazy pro základní matematické operace, příkazy skoku a prostředky pro vstup a výstup dat. Na některých počítačích nahrazoval i operační systém. Fortran – první jazyk používaný pro vědecko-technické výpočty. Algol 60 – tento jazyk obsahoval zcela nové koncepty, jako je bloková struktura programu, bez kterých si neumíme moderní programovací jazyk představit. Pascal – vytvořený profesorem N. Wirthem pro výuku programování. Navazuje na přístup, který se objevil v jazyce Algol 60. Pascal má však nové prostředky pro strukturované programování. Kromě základních datových typů jako je číslo nebo znak má i složitější tzv. strukturované, datové typy jako je soubor, množina, záznam apod. C – umožňuje psaní velmi efektivních programů, v současné době má v systémovém programování téměř výlučné postavení. Operační systémy jako MS-DOS, Windows, Unix, Linux, OS/2 jsou vesměs téměř celé napsané v jazyku C.


23

C++ – představuje rozšíření jazyka C o prostředky pro objektově orientované programování (viz dále). Java – je síťově orientovaný interpretovaný programovací jazyk vyvinutý firmou Sun Microsystems. Obecně však lze v Javě vytvořit cokoli, od operačního systému po podnikový informační systém. Díky tomu, že je Java interpretovaný jazyk, může program v Javě běžet na jakékoli platformě (tj. může být na tuto platformu portován velice rychle).

2.12

Překladač

Jak jsme si řekli v úvodu této kapitoly, samotný počítač rozumí jen řeči čísel. Proto se program napsaný v programovacím jazyce musí před svým spuštěním přeložit do strojového kódu. Dříve platilo, že překlad provedený ze zdrojového textu napsaného v assembleru byl daleko efektivnější než překlad provedený z vyššího programovacího jazyka. S použitím nových technik v překladačích se postupně tyto rozdíly stírají. Překladač je tedy program, který převádí data nebo kód programu z jednoho (vstupního) formátu (tvaru) do ekvivalentního (výstupního) formátu.

Obr. 2.5: Způsob práce překladače

V případě složitějších programů bývá zdrojový kód rozdělen do několika relativně nezávislých modulů, které se po zpracování překladačem spojují do konečného spustitelného programu pomocí tzv. linkeru.

2.13

Interpretované programovací jazyky

Doposud jsme se zabývali pouze překládanými programovacími jazyky. Druhou možností je, že zdrojové texty našich aplikací nejsou překládány do jiného (spustitelného) tvaru, ale jsou spouštěny s pomocí speciálního programu – interpretu. Interpret je tedy program, který na rozdíl od překladače příkazy zdrojového textu zapsané v programovacím jazyce nepřevádí do jiného tvaru, ale okamžitě je vykonává. Tento způsob je nyní velmi moderní při vytváření internetových aplikací. Například webový prohlížeč – interpret, vykonává příkazy jazyka pro tvorbu internetových stránek (HTML) a výsledek (webovou stránku) okamžitě zobrazuje na monitoru uživatele. Interpretace zdrojového textu ale není nic nového. Stejného principu je použito i při zpracování příkazů zadaných na příkazovém řádku operačního systému. Výhodou tohoto řešení je např. možnost okamžité opravy zdrojového textu bez nutnosti jeho překládání. Naopak nevýhodou je, že zdrojový text je pokaždé nutné znovu zpracovávat a nelze

24


v něm dopředu provést žádné optimalizace, tak jak to provádí překladač. Běh takového programu je tedy pomalejší, což u současných rychlých počítačů přestává být na překážku.

2.13.1

Příklady interpretovaných programovacích jazyků

HTML – HyperText Markup Language – jazyk používaný pro tvorbu internetových stránek JavaScript – používá se rovněž pro tvorbu internetových stránek. PHP – Professional Home Page – používá se pro tvorbu tzv. dynamických webových stránek, které na rozdíl od statických nejsou fyzicky uloženy na disku serveru, ale při každém požadavku na jejich čtení se nejprve musí na straně serveru vytvořit a teprve pak je možné jejich odeslání klientskému prohlížeči internetových stránek. SQL – databázový dotazovací jazyk, který je dnes standardem, který je součástí všech významných databázový systémů současnosti. Podstatou SQL je používání interaktivních dotazů při práci s databází; jazyk rovněž obsahuje příkazy pro další obvyklé činnosti s databází.

2.14

Operační systémy

Operační systém (zkráceně OS) je základní programové vybavení počítače. Jeho úkolem je sloužit uživateli a aplikacím a vytvořit most mezi nimi a počítačem samotným.

2.14.1

Základní funkce operačního systému

Mezi základní funkce operačního systému by mělo patřit alespoň: • zajištění možnosti ukládání dat na pevném disku v určitém formátu v rámci souborového systému, • ovládání periferních zařízení počítače, • zadávání příkazů operačního systému a spouštění aplikací. Moderní operační systém tedy nabízí aplikacím řadu služeb, které zpřístupňuje přes tzv. API (Application Programming Interface) funkce a neumožňuje aplikacím přímý přístup k hardwaru počítače. Pokud nějaký program chce tisknout na tiskárně, musí zavolat příslušnou službu operačního systému. Obrázek 2.6 ukazuje vrstvový model u operačního systému MS-DOS a jak by to mělo vypadat u moderního operačního systému. Zatímco u MS-DOSu přistupují aplikace i na hardware, u moderního operačního systému je toto znemožněno.


25

Obr. 2.6: Vrstvový model

2.14.2

Stručná charakteristika vybraných OS

MS-DOS – prováděl jen tu nejzákladnější obsluhu periferních zařízení. Mnoho aplikací využívalo jen jeho funkce pro práci se souborovým systémem, zatímco další zařízení si ovládaly samy (nejčastěji grafické karty). Obsluhu periferií jako je myš či zvuková karta prováděly specializované programy nazývané ovladače, které však nebyly součástí OS. Windows – má téměř výsadní postavení jako operační systém na osobních počítačích PC díky velkému výběru různých druhů aplikací. Poslední verze byly rozšířeny o vlastnosti nutné pro víceuživatelský a síťový OS, takže se začíná prosazovat i jako OS na serverech. Unix – používá se především jako víceuživatelský síťový operační systém na velkých systémech (serverech). Linux – nejrozšířenější OS typu Unix, protože je šířen volně a jeho příznivci pro něj implementovali velké množství tzv. Open Source aplikací, které jsou rovněž šířeny volně. Jeho velkou výhodou je velká stabilita a dostupnost kvalitních programů pro správu počítačové sítě a vytvoření internetového serveru. V současné době má Linux pevné postavení hlavně jako operační systém serverů.

2.14.3

Rozdělení operačních systémů

OS lze dělit podle různých hledisek, jednou z možností je rozlišení na: • OS, kde může být aktivní pouze jeden proces (monoprogramové), např. MSDOS. • OS, kde může být aktivních více procesů současně (multiprogramové, viz multitasking níže) a které umožňují i současnou práci více uživatelů (tzv. víceuživatelské). Příkladem je OS Unix nebo Linux.

2.14.4

Víceprogramové operační systémy

Víceprogramové operační systémy umožňují běh více procesů současně.

26


Multitasking Na běžném počítači s jedním procesorem může v daném okamžiku běžet jen jedna aplikace. Ostatní musí čekat, až na ně „přijde řadaÿ a procesor bude přidělen právě jim. Multitasking se dělí na preemptivní a nepreemptivní. Preemptivní znamená, že o přidělování procesoru jednotlivým aplikacím rozhoduje OS. Ten pak tedy může zajistit pravidelné „střídáníÿ aplikací při využívání procesoru a uživatel pak získá dojem, jako by tyto aplikace běžely skutečně současně, zatímco u nepreemptivního se pro přepínání úloh vyžaduje spolupráce aplikací s OS, kdy každá aplikace sama OS signalizuje, kdy má přidělit procesor někomu jinému.

2.15

Aplikační software

2.15.1

Kancelářský software

Pojem kancelářský software zahrnuje hlavně programy používané pro psaní textů, vytváření tabulek, běžné výpočty atd. Aplikace pro psaní textů lze v první řadě rozdělit na textové editory a textové procesory. Textovým editorem lze provádět pouze vlastní zápis textu, jeho zarovnávání, případně vkládání obrázků (Poznámkový blok, T602). Textové procesory nabízejí i další možnosti, k nimž patří formátování textu, spolupráce s jinými aplikacemi atd. (příkladem je MS-Word, Text602). Mnohé programy se snaží zobrazit text tak, jak by měl vypadat po vytištění a umožňují jeho interaktivní editaci (MS-Word, WinText602). Naopak v systému TEXje třeba do textu psaného s pomocí obyčejného textového editoru vkládat i speciální formátovací znaky a takovýto zdrojový soubor je třeba nejprve přeložit do formátu vhodnějšího pro prohlížeč, který pak lze s jeho pomocí zobrazit na obrazovku. V tomto případě tedy není možné provádět interaktivně editaci zobrazeného výstupu. Pokud je program pro psaní textu schopen jej na obrazovce monitoru ukázat přesně ve stejné podobě, jak bude vypadat i po vytištění, mluvíme o tzv. WYSIWYG, což znamená What You See Is What You Get a lze to volně přeložit jako přesně tak, jak to vypadá na obrazovce počítače, to bude vypadat i po vytištění na tiskárně. Tabulkové procesory byly navrženy pro záznam hodnot ve tvaru tabulky, které je pak možné zpracovat např. do podoby grafu, případně lze nad těmito daty provádět různé výpočty (např. program Excel). Databázové programy se používají pro záznam údajů a jejich snadnou editaci a vyhledávání. Za příklad lze jmenovat MS-Access, FoxPro, dBase, MySQL. Mezi kancelářskými aplikacemi dále obvykle nechybí nějaký jednoduchý program pro zpracování obrázků (příkladem může být Paintbrush, Photo Editor). Pro složitější manipulace s rastrovými obrázky jsou běžně používány programy GIMP či Adobe Photoshop. V současné době mnohé firmy nabízejí základní kancelářské aplikace jako jeden tzv. „balíkÿ programů – Microsoft Office, StarOffice.


2.16

27

Multimediální software

Multimediální programy lze velmi hrubě rozdělit na programy pro zpracování zvuku, videa a obrázků.

2.16.1

Zpracování zvuku

Programové vybavení na zpracování zvuku umožňuje mimo jiné záznam zvuku přehrát. Nejčastějšími formáty, v nichž je zvuk uložen, jsou soubory typu wav. Tyto soubory obsahují nekomprimovanou zvukovou nahrávku. Jsou příliš velké, ale zvuk v nich uložený je kvalitní. Poněkud s menší kvalitou se setkáme u formátů s kompresí – určité složky zvuku jsou vynechány, zvuk je navíc zhuštěn pomocí speciálního algoritmu a uložen na disk. Rozlišujeme přitom kompresi ztrátovou (tj. takovou, u níž při rekonstrukci signálu nedostaneme stoprocentně původní signál) a bezeztrátovou (při rekonstrukci dostaneme signál shodný s originálem před kompresí). Nejznámějším formátem se ztrátovou kompresí je formát mp3. Výhodou je malá velikost, nevýhodou je nutnost dekomprese při přehrávání. Multimediální software nabízí kromě přehrávání také různé druhy úprav zvukové nahrávky. Skladbu lze zrychlit nebo zpomalit, dají se z ní vybrat jen určité frekvenční složky, lze editovat jednotlivé segmenty, provádět speciální filtrace atd.

2.16.2

Zpracování obrázků

Pro zpracování statických obrazů se používají grafické editory, provádějí kreslení a transformace obrazů do požadovaného tvaru. Mezi takové operace patří otočení obrázků o libovolný úhel, zvětšení a zmenšení, detekce hran, ostření, transformace barev, retušování fotografie apod. Výsledný obrázek se ukládá do grafického formátu. V současné době existuje spousta druhů grafických souborů (např. gif, jpeg, png). Jednotlivé implementace se liší, ale v zásadě má každá struktura hlavičku (rozměry obrázku, typ obrázku, počet bajtů na bod) a za ní následují obrazová data (barvy jednotlivých bodů v obrázku).

2.16.3

Zpracování videa

Programy zpracování videa obsahují všechny funkce vztahující se k úpravám obrazu. Většina nástrojů dokáže video přetáčet, stříhat, přidávat libovolné efekty do výsledného filmu a pracovat současně i se zvukem, který je součástí videa. Výsledné video je uloženo ve videosouboru. Nejčastější záznam je typu mpeg, avi.

2.17

Software pro INTERNET

Pod pojmem INTERNET rozumíme síťové propojení počítačů po celém světě. Internet tedy poskytuje přístup z jednoho počítače na počítač jiný, fyzicky umístěný třeba stovky kilometrů od počítače, u kterého zrovna sedíte. Ke komunikaci mezi

28


jednotlivými počítači se používá speciální software. Podle toho, k čemu se používá, rozlišujeme: • webové prohlížeče (MS Internet Explorer, Mozilla, Netscape, Opera), • FTP klienti, • emulátory terminálů, • programy pro elektronickou poštu (Outlook, Mozilla, Ximian Evolution, Pine).

2.17.1

Webové prohlížeče

Tyto programy dokáží zobrazovat obsah WWW (World Wide Web) stránek. WWW stránka je obyčejný textový soubor napsaný v jazyce HTML. WWW prohlížeče ho načtou a úhledně zobrazí na monitoru. WWW stránka se zobrazí jako text a obrázky (jsou-li součástí takové stránky). Mezi nejznámější webové prohlížeče patří MS Internet Explorer a Netscape Comunicator. V záhlaví takového programu se zadá WWW adresa a požádá se o přístup na tuto WWW stránku. Pokud se uspěje, vzdálený počítač mu pošle obsah WWW stránky a ten se zobrazí.

2.17.2

FTP

Pokud potřebujeme získat data (soubory) ze vzdáleného počítače, použijeme program využívající protokol FTP. Zkratka FTP (File Transfer Protocol) znamená protokol pro přenos souborů. Je to konkrétní množina pravidel, podle nichž se přenášejí soubory po síti. Program s podporou FTP dovoluje zkopírovat data ze vzdáleného počítače na svůj vlastní a naopak nahrát lokální data na vzdálený počítač.

2.17.3

Terminály

Někdy je potřeba pracovat na počítači, který je vzdálen od místa, kde se právě vyskytujeme. Terminál nám dává možnost pracovat na vzdáleném počítači, aniž bychom byli fyzicky přítomni u vzdáleného počítače. Pomocí terminálu se přihlásíme na vzdálený počítač. Veškerá činnost se provádí na vzdáleném počítači přičemž terminál nám zobrazuje pouze výsledky.

2.17.4

Elektronická pošta

Software pro elektronickou poštu nabízí posílání a přijímání dopisů v elektronické podobě. Elektronickým dopisem rozumíme elektronicky zpracovaný text, který je obohacen o adresu příjemce. Adresa příjemce obsahuje speciální znak – @. V elektronickém dopise můžeme odeslat i jiné soubory než textové, a to ve formě tzv. příloh.

2.18

Kontrolní otázky

Příklad 2.1: Jaké komponenty obsahuje skříň počítače PC?


29

Příklad 2.2: K čemu slouží procesor v počítači? Příklad 2.3: Stručně definujte operační paměť. Příklad 2.4: Kolik bajtů je jeden MB? Příklad 2.5: Nakreslete strukturu disku (sektory a stopy na disku) Příklad 2.6: Popište princip čtení CD-ROM disku. Příklad 2.7: K čemu se využívá síťová karta? Příklad 2.8: K čemu se používá skener? Příklad 2.9: Vyšší programovací jazyk: a) je pro lidi méně pochopitelný než strojový kód. b) je nezávislejší na typu procesoru než assembler. c) vyžaduje speciální znalost architektury počítače. Příklad 2.10: Překladač je obecně program, který provádí překlad ze zdrojového tvaru: a) do nějakého cílového tvaru. b) pouze do strojového kódu procesoru Intel 80386. c) do posloupnosti celých čísel. Příklad 2.11: Program zpracovávající příkazy z příkazového řádku operačního systému je: a) překladač. b) nakladač. c) interpret. Příklad 2.12: Internetový prohlížeč webové stránky: a) iteruje. b) překládá. c) interpretuje.

30


Příklad 2.13: Multitasking a) umožňuje „současný běh více úlohÿ. b) slouží k ovládání periferních zařízení. c) je položka v menu (nabídce funkcí programu) udržující přehled o právě probíhajících úlohách. Příklad 2.14: Textový procesor je: a) program pro psaní textů. b) knihovna pro vědecko-technické výpočty. c) interpret příkazů z příkazové řádky. Příklad 2.15: Pojem WYSIWYG znamená: a) čip grafické karty pro trojrozměrnou grafiku. b) text zobrazený na obrazovce se ve stejné podobě i vytiskne. c) zobrazený text nelze interaktivně editovat.

3. Číselné soustavy

31

Kapitola 3 Číselné soustavy 3.1

Úvod

Číselnou soustavou rozumíme soubor pravidel, podle kterých pojmenováváme a zapisujeme čísla. Během lidské historie se objevila celá řada různých číselných soustav. Známá je například babylónská číselná soustava, která byla, jako jedna z prvních, poziční. To znamená, že pro určení hodnoty čísla byla významná pozice jednotlivých znaků v zápisu čísla. Zajímavé je, že Babyloňané používali při zápisu malých čísel (1–59) soustavu desítkovou, pro zápis větších čísel pak soustavu šedesátkovou. Z té doby se až dodnes zachovalo dělení hodiny na 60 minut, minuty na 60 sekund apod. Jiným typem číselných soustav jsou soustavy aditivní. Příkladem je římská číselná soustava. Zde pozice číslic nehraje takovou roli. Římská číselná soustava používá pro vyjádření hodnoty čísla sedm znaků – I, V, X, L, C, D, M. Jejich skládáním (a sečtením) se pak dosáhne požadované hodnoty, např. MDCLXXVI = 1676. Tento zápis čísel je však pro výpočty nevhodný. Desítková soustava je poziční soustava o základu deset. K zapisování čísel používáme deseti znaků: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, které se nazývají číslice (cifry). V zápisu čísla má každá číslice hodnotu, která je určená jejím postavením (pozicí). S touto číselnou soustavou se setkáváme v každodenním životě.

3.2

Celá čísla

Číslo xz = an an−1 an−2 . . . a1 a0 zapsané v soustavě o základu z má v soustavě desítkové hodnotu: (3.1) x10 = an z n + an−1 z n−1 + . . . + a1 z 1 + a0 z 0 kde z je základ číselné soustavy, ai jsou jednotlivé cifry v zápise čísla. Příklad: Pro desítkovou soustavu 532 = 5.102 + 3.101 + 2.100

32


3.2.1

Číselné soustavy a počítače

Ve světě počítačů se ovšem často používají soustavy s jiným základem než deset. Jsou to zejména soustavy o základu dvě, osm a šestnáct. Pro určení základu, ve kterém je určité číslo zapsáno, použijeme rozlišovacího znaku zapsaného za danou hodnotou. Pro číslo v desítkové soustavě to bude d, pro soustavu dvojkovou b, osmičkovou o a konečně pro soustavu šestnáctkovou h.1 Například číslo ve dvojkové soustavě bude mít zápis 1101b. Jiným způsobem naznačení základu číselné soustavy, ve které je číslo zapsáno, je připsání základu do pozice dolního indexu za číslem. Např. 111012 nebo F10016 . Pokud není uvedena žádná soustava, předpokládá se soustava o základu deset. Dvojková soustava Dvojková (též binární) soustava používá k zápisu čísla právě dvou číslic: 0 a 1. Pro přímou korespondenci se stavy neprotéká/protéká proud je právě tato soustava základní pro současné elektronické počítače. Příklad: Příkladem zápisu čísla ve dvojkové soustavě může být 1101b. Jeho hodnotu v desítkové soustavě získáme snadno s využitím vztahu (3.1). Základem z je číslo 2. Řešení: 1101b = 1.23 + 1.22 + 0.21 + 1.20 = 8 + 4 + 0 + 1 = 13d Poznamenejme, že např. číslo 101b nečteme „sto jednaÿ, ale „ jedna nula jednaÿ. Podobně je tomu i v případě soustav s jiným základem. Osmičková soustava Zápis čísla v binární soustavě je sice pro vyjádření čísla v oblasti digitálního zpracování dat výhodné, pro člověka však už méně. Problémem je zejména velký počet číslic pro vyjádření hodnoty čísla. Proto se někdy k zápisu čísla používá soustava osmičková. Příklad: Číslo v osmičkové soustavě a jeho hodnota v soustavě desítkové 735o = 7.82 + 3.81 + 5.80 = 448 + 24 + 5 = 477d Mezi osmičkovou a dvojkovou soustavou je možné čísla snadno převádět zpaměti. Trojice číslic čísla ve dvojkové soustavě od desetinné čárky postupně převedeme podle tabulky 3.1. Pokud nám nějaké číslice „chybějíÿ, doplníme nuly. Takže například číslo 1100111011b = 1473o. Převodní tabulky lze samozřejmě použít i v opačném směru: 725o = 111010101b. 1

Mnemotechnická pomůcka – využitím alternativních pojmenování soustav: d dekadická, b binární, o oktalová a h hexadecimální soustava.


33 N10 0 1 2 3

N2 N 8 000 0 001 1 010 2 011 3

N10 4 5 6 7

N2 N8 100 4 101 5 110 6 111 7

Tab. 3.1: Převod mezi dvojkovou a osmičkovou soustavou

Šestnáctková soustava Ještě kompaktnější zápis čísla nám umožňuje soustava šestnáctková. Znaky pro zápis čísel jsou: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (písmena mohou být i malá). Příklad: Převod čísla ze soustavy šestnáctkové do soustavy desítkové A39Fh = 10.163 + 3.162 + 9.161 + 15.160 = 41 887d Podobně jako v případě osmičkové soustavy je možné snadno převádět čísla mezi zápisem ve dvojkové, osmičkové soustavě s zápisem v soustavě o základu 16. N10 0 1 2 3 4 5 6 7

N2 N16 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7

N10 8 9 10 11 12 13 14 15

N2 N16 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F

Tab. 3.2: Převod mezi dvojkovou a šestnáctkovou soustavou

Takže podle tabulky 3.2 můžeme převést číslo F3Ah = 111100111010b. A nyní můžeme v případě potřeby dvojkové číslo dále převést do soustavy osmičkové: 111100111010b = 7472o.

3.2.2

Převody ze soustavy desítkové

Převod čísla z desítkové soustavy do jiné provádíme metodou postupného dělení základem cílové soustavy. Zbytek po dělení průběžně zapisujeme – tvoří výsledné číslo (pozpátku). Postup ilustruje příklad.

34


Příklad: Převeďte číslo 41d do dvojkové soustavy.

41 20 10 5 2 1

Základ 2 2 2 2 2 2

Podíl Zbytek 20 1 10 0 5 0 2 1 1 0 0 1

Řešení: Po převodu tedy 41d = 101001b.

3.3

Desetinná čísla

Samozřejmě rovněž desetinnou část čísla je možné reprezentovat v jiné než v desítkové soustavě. Převod (desetinné části) čísla xz = 0, a−1 a−2 . . . a−m ze soustavy o základu z do desítkové soustavy je možné realizovat takto: x10 = a−1 z −1 + a−2 z −2 + . . . + a−m z −m

(3.2)

Příklad: Pro desítkovou soustavu 0, 129 = 1.10−1 + 2.10−2 + 9.10−3 Příklad: Převeďte číslo 101, 101b do soustavy desítkové. Řešení: Použijeme vztahy (3.1) a (3.2) a dostaneme: 101, 101b = 1.22 + 0.21 + 1.20 + 1.2−1 + 0.2−2 + 1.2−3 = 5, 625d

3.3.1

Převod z desítkové soustavy

Celou část čísla převedeme podle návodu v odstavci (3.2.2). Desetinnou část čísla postupně násobíme základem cílové číselné soustavy. Pokud dojde k přenosu do řádu jednotek, opíšeme toto číslo (tvoří část výsledku), na jeho místo napíšeme nulu a postup opakujeme, dokud nedosáhneme dostatečné přesnosti. 2 Příklad: Převeďte číslo 34, 7525d do soustavy šestnáctkové. 2

V soustavách s jiným číselným základem než 10 jsou také čísla, která nelze přesně zapsat na konečný počet desetinných míst. Například číslo 1, 310 lze soustavě o základu 3 zapsat jako 1, 13 . Naopak číslo 1, 510 nelze v soustavě o základu 3 zapsat na konečný počet cifer (1, 510 = 1, 13 ).


35

Řešení: Celou část čísla převedeme do šestnáctkové soustavy zvlášť: 34d = 22h. Nyní postupným násobením převedeme desetinnou část čísla:

0,7525 0,04 0,64 0,24 0,84 0,44 0,04

Základ 16 16 16 16 16 16 16

Součin Přenos 12,04 12d = Ch 0,64 0d = 0h 10,24 10d = Ah 3,84 3d = 3h 13,44 13d = Dh 7,04 7d = 7h 0,64 0d = 0h

Vidíme, že číslo 34, 7525d je v šestnáctkové soustavě číslem periodickým: 34, 7525d = 22, C0A3D7h.

3.4

Výpočty

Základní aritmetické operace lze samozřejmě provádět i s čísly zapsanými v soustavě s jiným základem než 10. Je ovšem nutné brát v úvahu, že přenosy mezi řády se uplatní při dosažení základu soustavy. Příklad: Sčítání a odčítání v jiných číselných soustavách. 243o 355o 620o

FA3h −9D4h 5CFh

Pracujeme-li s čísly v různých číselných soustavách, je nejjednodušší převést všechna čísla do stejné soustavy a provést výpočet v ní. Na závěr výsledek případně převedeme do soustavy, ve které je požadován výsledek. Příklad: Vyhodnoťte výraz 65d + 172o − A3h, výsledek zapište v binární soustavě. Řešení: Převedeme všechna čísla do osmičkové soustavy: 65d = 101o A3h = 243o Provedeme příslušné aritmetické operace v osmičkové soustavě: 101o + 172o − 243o = 30o Nyní převedeme číslo 30o do dvojkové soustavy. 30o = 11000b

36


3.5

Příklady k procvičení

Příklad 3.1: Převeďte do dvojkové, osmičkové a šestnáctkové soustavy: a) 33d b) 63d c) 16d d) 99d Příklad 3.2: Převeďte do desítkové soustavy: a) 100110b b) 1001o c) 101h d) BABAh e) 377o f) 704o g) 705h Příklad 3.3: Vypočtěte, výsledek je požadován v desítkové soustavě a) 145h + 34h + 72o + 101b b) 111b - 72h + 34o + 100b c) 23h + 53o - 77o + 1101b d) F09h - 34o - 777o - 1111b Příklad 3.4: Zapište čísla v šestnáctkové soustavě a) 1,16d b) 23,451d c) 48,925d d) 7,5d Příklad 3.5: Vypočtěte, výsledek je požadován v osmičkové soustavě a) 5,43d + 7,11o + 1A,4Fh b) 4,77o - 2,Ah + 4,14d c) 33,57d - 20h - 0,33o d) 11,22o + 22,11d - 12,12h

4. Datové typy

37

Kapitola 4 Datové typy 4.1

Úvod

Každá proměnná (datový objekt, jehož hodnota se může v průběhu výpočtu programu měnit), kterou chceme v programu použít, musí mít předem určeno, zda se do ní bude ukládat celé číslo, desetinné číslo, text, logická hodnota apod. Proto existuje v každém programu deklarační část a v ní byla zavedena určitá klíčová slova (programovacím jazykem definované oddělovače programových konstrukcí), která nám umožňují jednoznačně určit tzv. datový typ. Datový typ proměnné určuje: 1. množinu hodnot, kterých může proměnná nabývat během programu, 2. množinu operací, které lze s touto proměnnou provádět. Datové typy se dělí několika způsoby: • Podle podpory programovacím nástrojem: – standardní (celočíselný, reálný, char, string, boolean) – definované uživatelem (výčtový typ, typ interval, pole, záznam, množina, soubor, ukazatel) • Podle typu: – ordinální (integer, word, char. . .), kdy každá hodnota daného typu má přesně určeného následníka i předchůdce – neordinální (string, real, pointer. . .) • Podle struktury: – jednoduché – nemají vnitřní strukturu, s proměnnou lze pracovat jako s celkem (integer, char, real. . .) – strukturované – hodnoty mají vnitřní strukturu (členění na složky), s proměnnou strukturou typu lze pracovat buď jako s celkem nebo s jeho jednotlivými složkami (array, file, record. . .)

38


Každému datovému typu odpovídá v programovacím jazyku specifická konstrukce, jíž je daný datový typ popsán.

4.2 4.2.1

Standardní datové typy Celočíselné datové typy

Hlavním reprezentantem celočíselných datových typů je typ integer. Rozsah hodnot, kterých může nabývat, je závislý na velikosti paměti, která je mu vyhrazena. V jazyce Turbo Pascal je standardní velikost datového typu integer 2 bajty. To však není pravidlem, obecně je vždy rozsah datového typu závislý na použité architektuře systému. Množina základních operací: • aritmetické: +, −, ∗, /, div (celočíselné dělení), mod (zbytek po dělení) • relační: =, <>, >, >=, <, <= (s logickým výsledkem) Standardní funkce v jazyce Turbo Pascal: • sqr(x) druhá mocnina • abs(x) absolutní hodnota • inc(x) zvýší proměnnou o 1 • dec(x) sníží proměnnou o 1 Příklad: Zjistěte výsledek operace 123 div 45 a 123 mod 45. Řešení: Jedná se o celočíselné dělení a zbytek po celočíselném dělení 45 ∗ 2 + 33 = 123 123 div 45 = 2 123 mod 45 = 33

4.2.2

Desetinné číselné datové typy

Základním reprezentantem desetinných datových typů je typ real. Používá se pro vyjádření hodnot s pohyblivou řádovou čárkou. Rozsah hodnoty typu real závisí na překladači, v Turbo Pascalu se definuje na 6 bajtů s jedenácti číslicemi mantisy a s rozsahem exponentu 10−38 až 10+38 . Množina základních operací: • aritmetické: +, −, ∗, / • relační: =, <>, >, >=, <, <=

4. Datové typy

39

Standardní funkce v jazyce Turbo Pascal: • sqr(x), sqrt(x), abs(x), sin(x), cos(x), ln(x), exp(x) • round(x) převod typu real na celočíselný zaokrouhlením. • trunc(x) převod typu real na celočíselný odseknutím desetinné části.

4.2.3

Logické datové typy

Standardním logickým datovým typem je typ boolean, který se používá k vyjádření logických hodnot a má pouze dvě možné hodnoty: vypnuto – 0 , zapnuto – 1, nebo také True – pravda, False – nepravda. Logické hodnoty jsou výsledkem např. všech relačních operací. Množina základních operací: • relační: =, <>, >, >=, <, <= Standardní operátory: • not(x) negace – „obrátíÿ hodnotu na opačnou • x and y logický součin – je-li pravda x, je výsledkem y, jinak nepravda • x or y logický součet – je-li pravda x, pak je výsledkem pravda, jinak y • x xor y neshodnost – je-li x = y, pak je výsledkem nepravda, jinak pravda

4.2.4

Datový typ znak

K zobrazení jednotlivých znaků se používá datový typ char. Typ char v paměti zabírá obvykle 1 bajt. Lze jím tedy zpravidla zobrazit 256 možných hodnot. Znaky s kódy 0 až 31 (včetně) se jmenují řídicí, a v minulosti se používaly k řízení dálnopisných operací, nyní se používají např. při řízení tisku a jiných výstupních zařízení. Množina základních operací: • relační: =, <>, >, >=, <, <= Standardní funkce : • ord(x) funkce vrací číslo (pořadí) znaku (kódovou hodnotu) • chr(x) funkce vrátí znak, který odpovídá danému číslu (kódu)

4.2.5

Datový typ řetězec

Řetězec, datový typ string, je posloupnost znaků. Možnosti, jak řetězec uložit v paměti, jsou dvě. Jazyk Turbo Pascal definuje řetězec pomocí posloupnosti maximálně 256 znaků, z nichž první reprezentuje délku řetězce. Další možností je posloupnost jednotlivých znaků zakončených znakem s kódem 0. Viz 4.2.4.

40


4.3 4.3.1

Uživatelem definované typy Strukturované datové typy

Pro zpracování více hodnot stejného typu se používá strukturovaná proměnná typu pole. Pole reprezentuje posloupnost hodnot stejného typu. Celá struktura se dělí na jednotlivé části – prvky pole. U datového typu pole je potřeba správně nadefinovat i datový typ jeho složky. Typem složky pole může být opět pole nebo libovolný jiný strukturovaný typ. Datový typ pole, jako takový, nás omezuje v jedné podstatné věci. Jeho prvky musí být stejného typu. Proto existuje datový typ záznam, který nám umožňuje nadefinovat typ, složený ze skupiny v podstatě libovolných datových typů. Pokud bychom si chtěli vytvořit např. seznam přátel, bylo by velmi výhodné použít datový typ záznam, který by obsahoval dvě složky typu řetězec – jméno a příjmení, pak např. celočíselný datový typ integer – věk, aj.

4.3.2

Ostatní

Pokud potřebujeme definovat výčet jednotlivých hodnot, kterých může daná proměnná nabývat, slouží k tomu datový typ výčet. Definovat rozsah hodnot můžeme pomocí datového typu interval. Pro definici množiny existuje odpovídající datový typ množina.

4.4


Příklad 4.1: Vypočtěte následující výrazy: a) trunc((trunc(3.234)+round(2.35))/2) b) (inc(30)+1) mod 4 c) DEDAh div BABAh Příklad 4.2: Vypočtěte následující výrazy: a) inc(sqr(9))+5*EAEAh b) chr(ord(’Ch’)+ord(’5’)) c) inc(ord(’b’))*dec(chr(’g’)) Příklad 4.3: Vypočtěte výslednou logickou hodnotu: a) (A and B) and (not(A) and not(B)) b) 10001010b xor 00010111b c) (TRUE and FALSE) or (not(FALSE) and TRUE) d) (1 or 0) and (0 and 1 or 0) e) chr(10) = chr(sqrt(100)) f) ord(chr(ord(’0’)) = ord(’1’)

5. Aritmetické a logické výrazy, posloupnosti

41

Kapitola 5 Aritmetické a logické výrazy, posloupnosti 5.1

Úvod

Tato kapitola pojednává o některých částech matematiky, které úzce souvisejí s informatikou. Aritmetické a logické výrazy jsou nedílnou součástí téměř každého počítačového programu. Proto je pro pokročilejší práci s počítačem nezbytné pochopit význam těchto výrazů a způsob jejich vyhodnocování počítačem. Uvedeny jsou také logické úlohy procvičující analytické myšlení, které je v informatice velmi potřebné.

5.2 5.2.1

Aritmetické výrazy Prvky aritmetických výrazů

Mezi základní stavební kameny aritmetických výrazů patří čísla, konstanty, proměnné a operátory. Čísla jsou prvky číselných množin. Svým zápisem vyjadřují přímo svou hodnotu. Známe například množinu čísel přirozených, celých, racionálních, reálných, komplexních apod. Podle příslušnosti čísla k některé z těchto množin rozlišujeme typ čísla, například celé číslo nebo reálné číslo. Konstanta je pojmenovaná číselná hodnota. Slouží zejména pro zjednodušení zápisu výrazů s často používanými čísly. Příkladem může být matematická konstanta π. U konstant stejně jako u čísel rozlišujeme typ, a to podle typu čísla, které reprezentují. Proměnná, podobně jako konstanta, reprezentuje nějaké číslo, avšak toto číslo (hodnota proměnné) se může měnit. Například v rovnici 3x + 5 = 11 je x proměnná. Také u proměnných je možné rozlišovat jejich typ podle typu hodnot, které mohou reprezentovat. Operátory jsou pojítkem, jehož využitím můžeme z čísel, konstant a proměnných vytvářet aritmetické výrazy. Operátory rozlišujeme podle počtu argumentů, ke kte-

42


rým se váží. Například znaménka + a − jsou unárními operátory, protože se váží jen k jednomu argumentu (např. +3, −x). Operátory pro základní aritmetické operace sčítání +, odčítání −, násobení · a dělení / nebo : jsou binárními operátory. Další vlastností, kterou u operátorů posuzujeme, je priorita. Priorita určuje přednost operátorů při vyhodnocování výrazů. Například operátory pro násobení a pro dělení mají obvykle vyšší prioritu, než operátory pro sčítáni a odčítání. Proto se výraz 3 + 2 · 4 vyhodnotí takto: 3 + 2 · 4 = 3 + 8 = 11 a ne takto: 3 + 2 · 4 = 5 · 4 = 20. Když potřebujeme, aby se jednotlivé části výrazu vyhodnocovaly v jiném pořadí než podle priorit operátorů, použijeme k tomu závorky, např. (3 + 2) · 4 = 5 · 4 = 20. Jestliže se stejný operátor vyskytuje ve výrazu více než jednou, řídí se vyhodnocování výrazu tzv. asociativitou tohoto operátoru. Například operátory +, −, ·, / jsou obvykle asociativní zleva. To znamená že výraz 3 + 2 + 4 se vyhodnocuje takto: 3 + 2 + 4 = 5 + 4 = 9. Naopak operace umocňování je asociativní zprava, a proto se 4 4 4 výraz 23 vyhodnocuje jako 23 = 281 a nikoli 23 = 84 . Dodejme, že kromě obvyklého zápisu binárních operátorů mezi své argumenty (tzv. infixová notace), např. 2 + 3, známe také notaci prefixovou, např. + 2 3, a postfixovou, např. 2 3 +. Tyto způsoby zápisu se uplatňují zejména u operátorů s vyšší aritou (počtem argumentů operátoru) než 2, například u ternárních operátorů.

5.2.2

Převody mezi číselnými typy

Jak už bylo uvedeno výše, rozeznáváme několik množin čísel a příslušných číselných typů. Pro převádění mezi těmito typy jsou definovány operace přetypování. Pro převod mezi dvěma konkrétními typy může existovat více možných operací přetypování. Proto je při práci s aritmetickými výrazy, které obsahují různé číselné typy, potřeba přesně definovat, jaké operace se mají při převádění mezi těmito typy použít. Například pro převod komplexního čísla na číslo reálné můžeme použít operaci absolutní hodnota komplexního čísla, reálná složka komplexního čísla, apod. Stejně tak pro převod z reálného na celé číslo máme na výběr několik operací zaokrouhlení (k nule, k +∞, k −∞, podle následující číslice apod.). Některé aritmetické operátory navíc automaticky provádějí konverzi typu výsledku. Například celočíselné dělení vrací celou část podílu, kterým obecně nemusí být celé číslo. Podobně operace modulo (mod ) vrací zbytek po celočíselném dělení. Zejména je-li výsledek celočíselného dělení záporný, je nutné specifikovat, zda se bude zaokrouhlovat k nule, nebo k −∞.

5.2.3

Řešené příklady

Příklad: Určete hodnotu aritmetického výrazu: 1.2 + ceil(5/4), kde funkce ceil provádí zaokrouhlení čísla k +∞ Řešení: Protože zaokrouhlení čísla k +∞ znamená nalezení nejmenšího celého čísla, které není menší než zaokrouhlované číslo, je výsledkem funkce ceil číslo 2 a hodnota výrazu je 1.2 + 2 = 3.2.


43

Příklad: Určete hodnotu aritmetického výrazu: −14/5 + 4, kde operace / představuje celočíselné dělení, které zaokrouhluje výsledek k nule. Řešení: Výraz se vyhodnotí takto: −14/5 + 4 = −2 + 4 = 2

5.3 5.3.1

Logické výrazy Matematická logika

Logika je věda, která studuje zákony správného myšlení, nebo jinými slovy, která se zabývá otázkami, jak lze správně usuzovat. Přibližme si předmět logiky příkladem v tabulce 5.1. Někdo možná namítne, že tvrzení „letadlo je rychlejší než autoÿ platí Jestliže platí, že letadlo je rychlejší než vlak letadlo je rychlejší než vlak a vlak je rychlejší než auto, a auto je rychlejší než vlak, pak platí, že letadlo je rychlejší než auto. letadlo je rychlejší než auto. Logika nám objasňuje, proč je úsudek správný. úsudek nesprávný. Tab. 5.1: Předmět logiky v obou případech. Nezabývejme se tím, že tomu tak ve skutečnosti nemusí být. Tyto otázky totiž nejsou pro logiku rozhodující. Logika se zabývá jen otázkami, zda byl z daných předpokladů vysloven správný závěr, a tak z hlediska logiky platí závěry uvedené v tabulce 5.1. Později poznáme, že předpoklady a závěr správného úsudku v tabulce 5.1 lze vyjádřit zápisem (X ∧ Y ) ⇒ Z, který platí obecně pro všechny druhy podobného usuzování. A tak se dostáváme k pojmu matematická logika. Zjednodušeně můžeme říci, že matematická logika je obor, který studuje, jak lze matematickými metodami tvořit z jednoduchých výroků výroky složitější a jak pravdivost těchto složitějších výroků závisí na pravdivosti jednotlivých výchozích výroků. Použili jsme slova výrok. Jde o základní pojem matematické logiky. Výrok je každé tvrzení, o němž má smysl říci, zda je pravdivé nebo nepravdivé (true nebo false, 1 nebo 0). Objasněme si pojem výroku na následujících větách: a) Číslo 2 je sudé. b) Labe protéká Prahou. c) Dnes je sobota. d) Na Uranu existuje život.

44

Přípravný kurz informatiky e) Otevřete okno! f) Auto vidí zatáčku.

O tom, že věta a) je výrok, a to pravdivý výrok, není jistě pochyb. Výrokem je i věta b), ale v tomto případě jde o nepravdivý výrok. Výrokem je i věta c), i když je pravdivost či nepravdivost tohoto výroku časově podmíněna – pravdivý je v sobotu, v ostatní dny je nepravdivý. Je výrokem věta d)? Mohlo by se zdát, že nikoli, ale není tomu tak. I když o existenci života na Uranu nemáme důkazy, v každém případě musí být toto tvrzení buď pravdivé, nebo nepravdivé, a proto je i věta d) výrokem. Výrokem samozřejmě není věta e), protože o pravdivosti této věty nelze hovořit. Výroky nejsou ani jiné rozkazovací nebo tázací věty nebo věty, které nemají smysl, jako je tomu u věty f). Je výrokem tvrzení vyjádřené matematickým jazykem x + 1 = 3? Není. Proč? Pokud neznáme hodnotu výrokové proměnné x, nemůžeme o pravdivosti tvrzení x + 1 = 3 hovořit. Z tohoto tvrzení se stane výrok teprve tehdy, když za proměnnou dosadíme některý prvek vhodné množiny. Například po dosazení x = 2 vytvoříme pravdivý výrok 3 = 3 a po dosazení x = 1 nepravdivý výrok 2 = 3. Výroky budeme označovat velkými písmeny A, B, C, . . . X, Y, Z. Říkali jsme si, že u každého výroku můžeme říci, je-li pravdivý nebo nepravdivý. V matematické logice říkáme, že každý výrok má určitou pravdivostní hodnotu, kterou vyjadřujeme znaky 1 a 0 podle této dohody: pravdivý výrok má pravdivostní hodnotu 1, nepravdivý výrok má pravdivostní hodnotu 0.

5.3.2

Logické operace

Podobně jako známe základní početní operace sčítání, odčítání, násobení a dělení, známe i základní logické operace s výroky, jejichž názvy, označení a jiné údaje jsou shrnuty v tabulce 5.2. Dodejme k této tabulce, že jejím smyslem je získat ucelený název označení čteme

jiné označení

negace A neplatí A; není pravda, že A A0 ; ¬A; non A

disjunkce A∨B

konjunkce A∧B

implikace A⇒B

ekvivalence A⇔B

nonekvivalence A 6≡ B

A nebo B

AaB

jestliže A, pak B

A právě tehdy, když B

buď A nebo B

A vel B

A · B; A&B

A→B

A ∼ B; A≡B

A 6∼ B; A 6⇔ B; A xor B

Tab. 5.2: Základní logické operace přehled o logických operacích, který svou stručností samozřejmě nemůže obsahovat podrobnosti, o nichž budeme hovořit postupně. Zapamatujte si však, že slova, jimiž spojujeme jednoduché výroky a která označujeme • znaky

, ∨, ∧, ⇒, ⇔, 6≡ se nazývají logické spojky nebo operátory,

• výrazy A ∨ B, A ⇒ B apod., případně i složitější výrazy, (A ∧ B) ∨ (A ∧ B), (A ⇒ B) apod. se nazývají logické formule.


45

Obraťme pozornost k jednotlivým logickým operacím. Ještě dřív však upozorněme na důležitou skutečnost. V dalším výkladu budeme používat výroků, které s matematikou nesouvisejí. Je to proto, aby vám byla pravdivost či nepravdivost toho či onoho výroku pokud možno bez hlubšího uvažování jasná. Uveďme příklad. Použijeme-li matematického výroku „ jestliže je číslo dělitelné devíti, pak je dělitelné také třemiÿ, je jeho pravdivost jistě méně zřejmá, než když použijeme výroku „ jestliže je slunečno, pak se můžeme opalovatÿ. Z tohoto hlediska posuzujte i použité příklady výroků. Negace Negací výroku A je výrok A, který vznikne slovním obratem „není pravda, že Aÿ nebo jiným slovním obratem v tomto významu. Objasněme si pojem negace na výrocích v tabulce 5.3. Je to jasné? Jistě ano, a tak přejděme k jiné otázce. Vysloví-li chlapec Negací výroku A „auto jedeÿ „auto nejedeÿ

je výrok A „auto nejedeÿ nebo „není pravda, že auto jedeÿ „auto jedeÿ nebo „není pravda, že auto nejedeÿ

Tab. 5.3: Negace pravdivý výrok A = „ jsem chlapecÿ, pak negací tohoto pravdivého výroku je nepravdivý výrok A = „nejsem chlapecÿ. Vysloví-li děvče nepravdivý výrok A = „ jsem chlapecÿ, pak negací tohoto nepravdivého výroku je pravdivý výrok A = „nejsem chlapecÿ. Tyto skutečnosti můžeme vyjádřit tabulkou 5.4, která se nazývá tabulkou pravdivostních hodnot. Z ní je patrné, že negací pravdivého výroku A = 1 je nepravnegace A 1 0

A 0 1

Tab. 5.4: Tabulka pravdivostních hodnot negace divý výrok A = 0 a naopak negací nepravdivého výroku A = 0 je pravdivý výrok A = 1. Dobře si její smysl uvědomte, protože tabulky pravdivostních hodnot logických operací a jiných výrokových formulí patří k základním pojmům výrokové a matematické logiky. Disjunkce Disjunkcí (logickým součtem) dvou výroků A, B je výrok označovaný A ∨ B, kde znak ∨ vyjadřuje spojku „neboÿ.

46


Uveďme příklad. Zvolme následující výroky: A = „ČR byla mistrem světaÿ a B = „ČR byla mistrem Evropyÿ. Disjunkcí výroků A, B je výrok „ČR byla mistrem světa nebo mistrem Evropyÿ, který zapisujeme výrokovou formulí A ∨ B. Pravdivostní hodnoty disjunkce při čtyřech různých uspořádaných dvojicích pravdivostních hodnot výroků A, B a tabulky pravdivostních hodnot disjunkce jsou uvedeny na obrázku 5.1. K uvedeným informacím snad není třeba nic dodávat. UpozorVýrok A Výrok B Disjunkce A ∨ B V případě, mistrem světa byla 1 byla 1 nebyla 0 nebyla 0

= „ČR byla mistrem světaÿ = „ČR byla mistrem Evropyÿ = „ČR byla mistrem světa nebo Evropyÿ

že ČR Evropy disjunkce byla 1 je pravdivá 1 nebyla 0 je pravdivá 1 byla 1 je pravdivá 1 nebyla 0 není pravdivá 0

Tabulka pravdivostních hodnot disjunkce A B A∨B 1 1 1 1 0 1 0 1 1 0 0 0

Disjunkce A ∨ B je pravdivá, je-li pravdivý alespoň jeden z výroků A, B. Obr. 5.1: Příklad s tabulkou pravdivostních hodnot disjunkce něme však, že spojka „neboÿ má v hovorovém jazyku odlišný smysl. Zamysleme se nad větami: a) „ČR byla mistrem světa nebo mistrem Evropyÿ, b) „na mistrovství Evropy získala ČR zlatou, nebo stříbrnou medailiÿ Ve větě a) spojka „neboÿ nevylučuje možnost že byla ČR současně mistrem světa i mistrem Evropy, spojka „neboÿ má v tomto případě tzv. nevylučovací (slučovací) smysl a právě takto chápeme spojku „neboÿ v matematické logice. Ve větě b) má spojka „neboÿ vylučovací smysl, protože když ČR získala zlatou medaili, nemohla získat současně stříbrnou medaili a naopak. Jen mimochodem – abychom v psaném jazyce vyjádřili, v jakém smyslu je třeba chápat spojku „neboÿ, píšeme před spojku „neboÿ ve vylučovacím smyslu čárku. Konjunkce Konjunkcí (logickým součinem) dvou výrazů A, B je výrok označovaný A ∧ B, kde znak ∧ vyjadřuje spojku „aÿ nebo někdy „a zároveňÿ, „a takéÿ apod. Příklad konjunkce výroků A, B a tabulka pravdivostních hodnot konjunkce A∧B jsou na obrázku 5.2. Podobně jako u spojky „neboÿ musíme být opatrní i pří používání a chápání spojky „aÿ. Podívejme se, v čem spočívá například problém na obrázku 5.3. Problém je i v tom, že se v běžné řeči používá spojka „aÿ v případech, kdy by bylo vhodnější užít spojky „neboÿ, například ve výroku „vlak jezdí v neděli a ve dnech po dni pracovního kliduÿ.

5. Aritmetické a logické výrazy, posloupnosti Výrok A Výrok B Konjunkce A ∧ B V případě, že na návštěvu David Martin přišel 1 přišel přišel 1 nepřišel nepřišel 0 přišel nepřišel 0 nepřišel

47

= „na návštěvu přišel Davidÿ = „na návštěvu přišel Martinÿ = „na návštěvu přišel David a Martinÿ

konjunkce 1 je pravdivá 1 0 není pravdivá 0 1 není pravdivá 0 0 není pravdivá 0

Tabulka pravdivostních hodnot konjunkce A B A∧B 1 1 1 1 0 0 0 1 0 0 0 0

Konjunkce A ∧ B je pravdivá, jsou-li pravdivé zároveň oba výroky A, B. Obr. 5.2: Příklad s tabulkou pravdivostních hodnot konjunkce Výrok „prodáváme jen tužky dlouhé a ořezanéÿ může znamenat jen dlouhé tužky, které jsou tužky dlouhé (ořezané i neořeořezané zané) a tužky ořezané (dlouhé i krátké) Obr. 5.3: Dvojznačnost spojky „aÿ Implikace Implikací dvou výroků A, B je výrok označovaný A ⇒ B, kde znak ⇒ vyjadřuje slovní obrat ve smyslu „ jestliže platí výrok A, pak platí výrok Bÿ. Příklad implikace výroků A, B a tabulka pravdivostních hodnot implikace A ⇒ B je na obrázku 5.4. Možná vás překvapuje, že je implikace pravdivá, když je výrok A nepravdivý (třetí a čtvrtý řádek tabulky). Proč tomu tak je? Vyslovená implikace vychází z předpokladu, že je neděle, ale netvrdí nic o tom, zda je muzeum otevřeno nebo uzavřeno v ostatních dnech, a tak když tento předpoklad není splněn a je například pondělí, může být muzeum otevřeno i uzavřeno, takže tato situace není v rozporu s vysloveným tvrzením. Ekvivalence Ekvivalencí dvou výroků A, B je výrok označovaný A ⇔ B, kde znak ⇔ vyjadřuje slovní obrat ve smyslu „výrok A platí právě tehdy, když platí výrok Bÿ. Příklad a tabulka pravdivostních hodnot ekvivalence A ⇔ B je na obrázku 5.5. Nonekvivalence Nonekvivalencí dvou výroků A, B je výrok označovaný A 6≡ B, kde znak 6≡ vyjadřuje slovní obrat ve smyslu „platí buď výrok A nebo platí výrok Bÿ. Příklad a tabulka

48

Přípravný kurz informatiky Výrok A Výrok B Implikace A ⇒ B

V případě, je neděle je neděle není neděle není neděle

že 1 1 0 0

= „ je neděleÿ = „muzeum je otevřenoÿ = „ jestliže je neděle, pak je muzeum otevřenoÿ

a muzeum je otevřeno není otevřeno je otevřeno není otevřeno

1 0 1 0

implikace je pravdivá 1 není pravdivá 0 je pravdivá 1 je pravdivá 1

Tabulka pravdivostních hodnot implikace A B A⇒B 1 1 1 1 0 0 0 1 1 0 0 1

Implikace A ⇒ B je nepravdivá, je-li výrok A pravdivý a výrok B.nepravdivý. V ostatních případech je implikace pravdivá. Obr. 5.4: Příklad s tabulkou pravdivostních hodnot implikace Výrok A Výrok B Ekvivalence A ⇔ B

= = =

„kouř směřuje k jihuÿ „vítr vane od severuÿ „kouř směřuje k jihu právě tehdy, když vítr vane od severu“

V případě, že

kouř k jihu směřuje 1 směřuje 1 nesměřuje 0 nesměřuje 0

a vítr od severu ekvivalence vane 1 je pravdivá 1 nevane 0 není pravdivá 0 vane 1 není pravdivá 0 nevane 0 je pravdivá 1

Tabulka pravdivostních hodnot ekvivalence A B A⇔B 1 1 1 1 0 0 0 1 0 0 0 1

Ekvivalence A ⇔ B je pravdivá, jsou-li pravdivé zároveň oba výroky A, B. Obr. 5.5: Příklad s tabulkou pravdivostních hodnot ekvivalence pravdivostních hodnot nonekvivalence A 6≡ B je na obrázku 5.6.

5.3.3

Řešené příklady

Příklad 5.1: Byl zveřejněn následující inzerát: „Přijme se pracovnice, která má středoškolské vzdělání nebo 5 let praxe a ovládá těsnopis.ÿ Přihlásila se uchazečka, která neměla středoškolské vzdělání, ale měla 8 let praxe a výborně ovládala těsnopis, dále uchazečka, která měla středoškolské vzdělání, 8 let praxe, ale neovládala těsnopis, a konečně uchazečka, která měla jen středoškolské vzdělání, ale neměla žádnou praxi a neovládala těsnopis. Můžete rozhodnout, která z uchazeček byla přijata?

5. Aritmetické a logické výrazy, posloupnosti Výrok A Výrok B Nonekvivalence A 6≡ B

= = =

49

„venku je krásněÿ „venku je škareděÿ „buď je venku krásně nebo je venku škaredě“

V případě, že

venku a venku nonekvivalence je krásně 1 není krásně 1 je pravdivá 1 je krásně 1 není krásně 0 není pravdivá 0 není krásně 0 je krásně 1 není pravdivá 0 není krásně 0 je krásně 0 je pravdivá 1

Tabulka pravdivostních hodnot nonekvivalence A B A 6≡ B 1 1 0 1 0 1 0 1 1 0 0 0

NonEkvivalence A 6≡ B je pravdivá, je-li pravdivý právě jeden z výroků A, B. Obr. 5.6: Příklad s tabulkou pravdivostních hodnot nonekvivalence Řešení: O tom, která z uchazeček byla přijata, nelze rozhodnout. Text inzerátu není formulován jednoznačně, připouští dvojí výklad vyjádřený výrokovými formulemi (A∨B)∧C a A∨(B ∧C), takže podmínky inzerátu splňují všechny tři uchazečky. Například i třetí uchazečka v souladu s výrokovou formulí A ∨ (B ∧ C). Příklad 5.2: Při střídání hráčů v hokejovém utkání se měl trenér rozhodnout, koho z hráčů A, B, C, D, E, má vyslat na led, jestliže si byl vědom, že a) B by měl hrát, když bude hrát A, b) když bude hrát E, měli by hrát i hráči A a D c) B a C by neměli hrát společně, protože nejsou sehraní, d) C a D by měli společně hrát nebo společně zůstat na střídačce, e) měl by hrát D nebo E Které hráče měl trenér vyslat na led, aby byly všechny podmínky splněny? Řešení: Jestliže jednoduché výroky „A bude hrátÿ, „B bude hrátÿ, . . . označíme písmeny A, B, . . . a slovní text tohoto problému přeložíme do jazyka výrokové logiky, dospějeme k závěru, že řešením je nalezení všech uspořádaných pětic pravdivostních hodnot jednotlivých výroků A, B, C, D, E, pro které jsou pravdivé výrokové formule: (A ⇒ B), E ⇒ (A ∧ D) , (B ∧ C), (C ⇔ D), (D ∨ E). Řešení nalezneme vyplněním tabulky, která obsahuje pravdivostní hodnoty těchto formulí pro všech 32 uspořádaných pětic výroků A, B, C, D, E (5 dvouhodnotových výroků, tedy celkem 25 = 32 možností). V tabulce 5.5 je vyplněno několik řádků včetně toho, který obsahuje řešení. V tabulce nalezneme, že výrokové formule jsou všechny současně pravdivé jen při uspořádané pětici pravdivostních hodnot (0, 0, 1, 1, 0) výroků (A, B, C, D, E).

50

Přípravný kurz informatiky A 1 .. .

B 1 .. .

C 1 .. .

D 1 .. .

E 1 .. .

A⇒B 1 .. .

0 0 0 .. .

1 0 0 .. .

0 1 1 .. .

0 1 1 .. .

0 1 0 .. .

1 1 1 .. .

0

0

0

0

0

1

E ⇒ (A ∧ D) (B ∧ C) (C ⇔ D) (D ∨ E) 1 0 1 1 .. .. .. .. . . . . 1 1 1 0 0 1 1 1 1 1 1 1 .. .. .. .. . . . . 1 1 1 0

Tab. 5.5: Pravdivostní hodnoty výrokových formulí Vyplývá z toho, že výroky A, D, E jsou nepravdivé a výroky C, D pravdivé, neboli na led by měl trenér vyslat hráče C a D. Příklad 5.3: Když turista spěchal k nádraží, přišel na rozcestí, odkud vedla jedna cesta k nádraží a druhá ne. Na rozcestí byli dva bratři, z nichž jeden mluvil vždy pravdu a druhý vždy lhal, na jakoukoli otázku odpovídali jen „anoÿ nebo „neÿ a oba znali správnou cestu. O tom všem turista věděl, ale nevěděl, která cesta vede k nádraží a kdo z bratrů mluví pravdu a kdo lže. Turista ukázal na jednu z cest, položil jednomu z bratrů jedinou otázku a z odpovědi vyvodil, která z cest vede k nádraží. Nalezněte znění této otázky. Řešení: Turista musel položit takovou otázku, na kterou by oba bratři odpověděli stejně. Ukázal tedy na jednu z cest a zeptal se jednoho z bratrů: „Co by mi řekl tvůj bratr, kdybych se ho zeptal, zda tato cesta vede k nádraží?ÿ Jestliže cesta k nádraží vede, odpoví každý z bratrů na tuto otázku „neÿ. Pokud tato cesta k nádraží nevede, odpoví každý z bratrů „anoÿ.

5.4

Číselné posloupnosti

V matematice rozumíme pod pojmem posloupnost každou funkci, jejímž definičním oborem je množina přirozených čísel. Známe jednak nekonečné posloupnosti zapisované {an }∞ n=1 nebo jen {an }, je-li definičním oborem množina všech přirozených čísel, jednak konečné posloupnosti zapisované {an }kn=1 nebo jen {an }k1 , kde k je dané přirozené číslo. Číselná posloupnost je obvykle určena • výčtem prvků, například 1, 4, 7, 10 • vzorcem pro n-tý člen, například {3n − 2}41 , z čehož vypočteme jednotlivé členy posloupnosti postupným dosazováním přirozených čísel n = 1, 2, 3, 4 do daného vzorce, tedy v našem případě a1 = 3 · 1 − 2 = 1, a2 = 3 · 2 − 2 = 4 atd. • rekurentním vzorcem, například a1 = 1, an+1 = an + 3, z něhož vypočteme vždy následující člen posloupnosti an+1 z předcházejícího známého členu an , tedy v našem případě a1 = 1, a2 = a1 + 3 = 4, a3 = a2 + 3 = 7 atd.


5.4.1

51

Základní typy číselných posloupností

Aritmetická posloupnost Členy aritmetické posloupnosti jsou definovány rekurentním vzorcem an+1 = an + d, kde d je konstanta zvaná diference. Z toho tedy vyplývá, že rozdíl d = an+1 − an mezi libovolnými dvěma členy aritmetické posloupnosti je konstantní. Součet sn prvních n členů posloupnosti můžeme vypočítat podle vzorce sn =

n (a1 + an ). 2

Příklad: Posloupnost všech lichých přirozených čísel 1, 3, 5, 7, 9, . . . je aritmetickou posloupností s prvním členem a1 = 1 a diferencí d = 2. Geometrická posloupnost Členy geometrické posloupnosti definujeme rekurentním vzorcem an+1 = an · q, kde q je konstanta zvaná kvocient, která tentokrát udává konstantní podíl mezi libovolnými dvěma sousedními členy geometrické posloupnosti. Součet sn prvních n členů posloupnosti můžeme vypočítat podle vzorce s n = a1

qn − 1 q−1

pro q 6= 1.

Příklad: Posloupnost mocnin čísla 2, tedy 1, 2, 4, 8, 16, . . ., je geometrickou posloupností s prvním členem a1 = 1 a kvocientem q = 2. Fibonacciho posloupnost Tato posloupnost, pojmenovaná po italském matematikovi třináctého století, je definována následovně ( 1 pro n = 1, 2 an = an−1 + an−2 pro n > 2 Příklad: Jednomu páru dospělých králíků se narodí každý měsíc jeden pár králíků. Z narozených králíků se stanou dospělí králíci za dva měsíce a pak se každému dospělému páru narodí opět jeden pár. Otázka zní, kolik dospělých králíků žije v pátém měsíci, jestliže žádný neuhyne?

52


Řešení: Počet dospělých párů králíků tvoří v jednotlivých měsících posloupnost 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . , kde první dva členy jsou jedničky a každý další člen se rovná součtu dvou bezprostředně předcházejících členů, což je Fibonacciho posloupnost. Z toho vyplývá, že v pátém měsíci bude žít pět dospělých párů králíků.

5.5


Příklad 5.1: Určete hodnotu aritmetického výrazu: 7/2 − 0.2, kde operace / představuje celočíselné dělení, které zaokrouhluje výsledek k nule. Příklad 5.2: Prodavačka na stánku prodává vajíčka. Přijde k ní první kupec a ten si koupí polovinu vajíček a k tomu půlku vajíčka. Druhý kupec si koupí půlku zbytku a půlku vajíčka. Třetí kupec si koupí půlku zbývajícího zbytku a půlku vajíčka. Nezbylo ani jedno. Vajíčka se nedají půlit. Kolik vajíček bylo na začátku? Příklad 5.3: Máte devět na první pohled stejných mincí, ale jedna falešná je těžší. Podaří se vám jen dvojím vážením na miskových váhách bez závaží zjistit falešnou minci? Příklad 5.4: Z deseti sáčků s mincemi obsahuje devět sáčků pouze falešné mince a jeden pouze pravé. Každá pravá mince má hmotnost 1,1g a každá falešná mince má hmotnost 1,0g. Máte k dispozici váhu se dvěma miskami a sadu přesných závaží. Dokážete pomocí jediného vážení libovolného množství mincí určit sáček s pravými mincemi? Příklad 5.5: Za jaký nejmenší čas opečete tři topinky, když se na pánvičku vejdou jen dvě najednou a jedna strana se peče 1 minutu? (Čtyři minuty není správné řešení.) Příklad 5.6: Král měl tři dcery. Vždy pravdomluvnou Alžbětu, vždy lhající Boženu a Vlastu, která někdy lhala a někdy ne. Když se princ ucházel o pravdomluvnou Alžbětu, král mu ji přislíbil za podmínky, že smí každé princezně položit jen jednu otázku a pak, protože princ princezny podle podoby neznal, si podle odpovědi vybrat Alžbětu sám. Potom odvedl prince k princeznám. Seděly vedle sebe, princ chvíli přemýšlel a pak každé položil stejnou otázku: „Jak se jmenuje tvá sestra, která sedí uprostřed?ÿ Princezna vlevo odpověděla: „Alžběta,ÿ princezna uprostřed: „Boženaÿ a princezna vpravo: „Vlasta.ÿ Princ se na chvíli zamyslet a pravdomluvnou Alžbětu podle odpovědí poznal. Která z princezen to byla?


53

Příklad 5.7: Prvoci se rozmnožují tak, že z každého jedince vznikají dělením vždy dva samostatní jedinci. Do vodní nádrže byl nasazen 1. června jediný prvok, 2. června byli v nádrži dva prvoci, dalšího dne již čtyři prvoci, pak osm prvoků atd. Za předpokladu, že prvoci nehynuli, bylo v nádrži 30. června přesně 1 073 741 824 prvoků. Dokážete bez počítání určit datum, kdy byla prvoků přesně polovina? Příklad 5.8: Doplňte následující člen každé z posloupností, který má logicky následovat. a) A, D, G, J b) 1, 3, 6, 10 c) 21, 20, 18, 15, 11 d) 8, 6, 7, 5, 6, 4 e) 65536, 256, 16

54


Kapitola 6 Algoritmy 6.1

Úvod

Při práci na počítači používáme mnoho programů. Jedno mají společné: jsou napsány v nějakém programovacím jazyce. Potřeba zapisovat postupy práce vznikla již v dávnověku, kdy bylo potřeba zapsat návod jak něco udělat tak, aby tomu rozuměl nejen autor a byl tento zápis přesný a reprodukovatelný. Problémem bylo, že se používal obvyklý jazyk pro komunikaci mezi lidmi. Ten je sice krásný a libozvučný, především český jazyk, ale nehodí se pro jednoznačný zápis myšlenek. Jen kolik obsahuje synonym, antonym a homonym, slov s nejednoznačným významem! Proto se začal používat upravený daleko jednodušší jazyk, angličtina, a z něho jen zlomek slov. Každý autor programovacího či sdělovacího jazyka má potřebu vytvořit svůj ”dokonalý jazyk”, který se k danému účelu nejvíce hodí. Programy, bez ohledu na jazyk, ve kterém byly vytvořeny, vznikly činností zvanou programování. Programování je postup, při kterém vzniká program. Z této kapitolky byste měli získat základní přehled o programování.

6.2

Co je algoritmus

Algoritmus je posloupnost operací, které řeší daný úkol. Řešení úkolu musíme zapsat v drobných krocích, které je daný programovací nástroj schopen realizovat. Tyto operace na sebe navazují (závisejí na předchozí). Nyní se podíváme, jaké vlastnosti musí algoritmus splňovat.

6.2.1

Vlastnosti algoritmu

Hromadnost – algoritmus musí řešit danou úlohu pro různé vstupní hodnoty. Nepočítá 1 + 2 = 3, ale X + Y = Z, kde X, Y jsou vstupní hodnoty, které jsou (skoro) libovolné. Determinovanost – všechny operace i jejich návaznosti jsou jednoznačně určeny (definovány), nic nesmí být náhodné, neurčené. Důsledkem také je, že při stejných vstupních hodnotách dostaneme stejný výstupní výsledek.

6. Algoritmy

55

Konečnost – algoritmus musí celý proběhnout v konečném počtu kroků.

6.2.2

Zápis algoritmu

Z postupu vzniku programu víme, že algoritmus zapisujeme příkazy námi zvoleného programovacího jazyka. To je však přímo možné jen u velmi jednoduchých úloh. Složitější úlohy je nutné si rozdělit na podúlohy a ty teprve řešit, případně ještě rozdělit. Pro tuto dekompozici problému lze s výhodou použít vývojový diagram, což je grafické znázornění algoritmu.

6.2.3

Vývojové diagramy

Vývojové diagramy se používají ke grafickému zápisu algoritmů. Každý diagram je složen z normalizovaných značek propojených spojnicemi. Spojnice je čára propojující jednotlivé značky. Může být buď vodorovná nebo svislá. Není-li spojnice opatřena šipkou, předepisuje čtení diagramu zleva doprava nebo shora dolů. V případě, že má spojnice předepisovat čtení diagramu zprava doleva nebo zdola nahoru, musí být opatřena šipkou. Značky vývojových diagramů Každá značka ve vývojovém diagramu označuje určitou základní operaci, z nichž se skládá popisovaný algoritmus. Běžně se používají následující základní značky. Mezní značka: kreslí se na začátek a konec diagramu a do místa, kde se má běh algoritmu přerušit. Píšeme do ní obvykle na začátku algoritmu název, na konci slovo „ENDÿ a v místě přerušení „STOPÿ. Načtení dat (vstup): předepisuje načtení dat z vnějšího zdroje (např. klávesnice). Obsahuje jména proměnných, jejichž hodnoty se mají načíst. Výstup dat: předepisuje výstup dat, např. jejich zobrazení na obrazovce. Opět obsahuje jména proměnných, jejichž hodnota má být umístěna na výstup.

Obecná činnost: tato značka popisuje libovolnou činnost. Ta se obvykle do značky napíše. Na příkladu vidíme výpočet délky kružnice.

56

Přípravný kurz informatiky Větvení: touto značkou větvíme algoritmus v závislosti na tom, zda uvedená podmínka je či není splněna. Vstup značky je vždy shora, výstupy lze zakreslit libovolně. Větev algoritmu odpovídající splnění dané podmínky se obvykle označuje znaménkem +, větev opačná pak znaménkem −. Cyklus: označuje začátek a konec cyklu řízeného parametrem. Jednotlivé druhy cyklů jsou popsány v kapitole 6.3.2, kde nalezneme i příklad použití této značky. Vstup do podprogramu: tato značka předepisuje vykonání činnosti, která je definována jiným vývojovým diagramem (tzv. podprogram). Obsahem značky je jméno podprogramu, který se má vykonat. Spojka: nemá žádný funkční význam. Slouží pouze k dosažení větší přehlednosti rozsáhlých diagramů. Označuje přerušení diagramu a pokračování na jiném místě, které je označeno spojkou obsahující stejné číslo. Poznámka: slouží ke vpisování poznámek do diagramu. Připojuje se čárkovanou čarou buď k jiné značce, nebo ke spojnici.

6.3

Návrh programu

Návrh programu není činnost, která se provádí ad hoc, z hlavy. Existují postupy, které je vhodné dodržovat. Návrh programu probíhá v etapách, které není vhodné spojovat. Každá etapa musí být ukončena před tím, než se přejde do další fáze. Změna v předcházející etapě má značný vliv na další etapu, která z ní vychází.

6.3.1

Postup vzniku programu

1. Zadání úkolu – potřebujeme vyřešit nějaký problém, zefektivnit určitou činnost. V této fázi je nejdůležitější přesně určit, co potřebujeme řešit a jaký má být výsledek.

6. Algoritmy

57

2. Návrh postupu řešení – obvykle existuje několik možností řešení. Každé řešení má své výhody i nevýhody. Rozhodujeme se mezi efektivitou algoritmu a pracností naprogramování. 3. Algoritmizace – celý problém pak rozdělíme na podproblémy, nad kterými se znovu zamýšlíme, jak je řešit, až do úrovně, která je snadno řešitelná obvyklými programovacími jazyky. Algoritmus zapisujeme v určitém programovacím jazyce. Výběr programovacího jazyka je důležitý z hlediska možností, které nám nabízí a účelu k jakému chceme program použít. 4. Testování – úplné testování programu je prakticky nemožné, proto testování zpravidla spočívá v kontrole všech vstupních a odpovídající výstupních hodnot. Používá se způsob, při kterém pokud možno otestujeme všechny okrajové hodnoty vstupních dat. Chyby rozdělujeme na syntaktické, které překladač programovacího jazyka většinou ohlásí, jsou to např. překlepy a vynechání syntaktických útvarů. Dále chyby logické, které nejsou hlášeny, jen program nedělá co má. Důležitý zákon: Testováním zjistíme určitě jen to, že daný program má chybu. V případě, že nenalezneme chybu, neznamená to, že program je bez chyb, ale jen to, že jsme případnou chybu neodhalili. 5. Podpora programu a údržba – po správném a zdařilém otestování máme funkční program, ke kterému vytvoříme dokumentaci.

6.3.2

Základní konstrukce algoritmů

Každý algoritmus, který navrhujeme, musí mít logickou strukturu. Skládá se z bloků, které vykonávají přesně vymezenou činnost a tyto bloky na sebe logicky navazují. U algoritmu navrženého podle těchto zásad lze snadněji ověřovat jeho správnost, je přehledný a v neposlední řadě jej lze snadno implementovat v jakémkoliv programovacím jazyce. Popsaného stavu lze docílit tak, že se při návrhu algoritmu omezíme pouze na použití následujících konstrukcí: sekvence příkazů, podmíněný příkaz a cyklus. Použití těchto konstrukcí si nyní ukážeme pomocí vývojových diagramů. Sekvence příkazů Jedná se o prostou posloupnost příkazů, které jsou prováděny jeden po druhém (obrázek 6.1). Tato posloupnost se vždy provede celá a můžeme ji proto chápat jako jeden nedělitelný funkční blok vykonávající určitou činnost. V algoritmu lze tedy sekvenci příkazů chápat jako jediný příkaz. V následujících odstavcích budeme vždy znázorňovat konstrukce algoritmu s jedním příkazem. Každý příkaz lze nahradit sekvencí příkazů. Podmíněný příkaz Je příkaz, který je proveden pouze tehdy, pokud je splněna určitá podmínka. V zásadě lze rozlišit dva typy podmíněných příkazů.

58


Obr. 6.1: Posloupnost příkazů Neúplný podmíněný příkaz: Je znázorněn na obrázku 6.2. Příkaz P je proveden, pokud je zadaná podmínka C splněna. V případě nesplnění podmínky není proveden žádný příkaz. Možná je samozřejmě i opačná konstrukce, kdy se příkaz provede pouze tehdy, pokud podmínka není splněna. Pro tuto konstrukci se často používá označení if - then (vychází z programovacího jazyka Pascal).

Obr. 6.2: Neúplný podmíněný příkaz

Úplný podmíněný příkaz: Na obrázku 6.3 je znázorněn úplný podmíněný příkaz. V tomto případě je při platnosti podmínky C proveden příkaz P1 . Pokud podmínka C není splněna, je proveden příkaz P2 . Tato konstrukce bývá označována if - then - else. Cyklus Cyklus je taková konstrukce, ve které se jistý příkaz nebo sekvence příkazů může provádět opakovaně. Podle toho, jakým způsobem je řízen počet opakování příkazu, rozlišujeme tři základní druhy cyklů.

6. Algoritmy

59

Obr. 6.3: Úplný podmíněný příkaz Cyklus řízený podmínkou na začátku: Tento typ cyklu je znázorněn na obrázku 6.4. Nejdříve se vyhodnotí podmínka C. Pokud je splněna, provede se příkaz P a podmínka C se vyhodnocuje znovu. Cyklus končí v okamžiku, kdy podmínka C není splněna. Při pohledu na vývojový diagram je zřejmé, že příkaz P nemusí být proveden ani jednou. Tento typ cyklu se také často nazývá cyklus typu while. Často používaná je i varianta s obráceně postavenou podmínkou.

Obr. 6.4: Cyklus řízený podmínkou na začátku

Cyklus řízený podmínkou na konci: Jak je patrné z obrázku 6.5, u tohoto typu cyklu se nejprve provede příkaz P a teprve poté se vyhodnotí podmínka C. Není-li podmínka splněna, provádí se znovu příkaz P . Cyklus končí v případě, že podmínka C je splněna. Příkaz P se v tomto případě tedy provede vždy alespoň jednou. Často používaná je i varianta s obráceně postavenou podmínkou. Velmi často se u tohoto typu cyklu můžeme setkat s označením „cyklus typu repeatÿ nebo „repeat - untilÿ. Cyklus řízený parametrem: Jedná se o speciální případ cyklu, kde hlavním kritériem není obecná podmínka, ale hodnota zvláštní proměnné – parametru. Někdy se také můžeme setkat s označením „řídící proměnná cykluÿ. Na začátku je hodnota parametru nastavena na počáteční hodnotu start a v každém průchodu cyklu

60


Obr. 6.5: Cyklus řízený podmínkou na konci se hodnota parametru zvýší o hodnotu krok. Cyklus probíhá tak dlouho, dokud hodnota parametru nedosáhne koncové hodnoty stop. Z toho je zřejmé, že u tohoto typu cyklu lze předem určit, kolikrát bude příkaz P proveden (u ostatních typů to obecně možné není). Proto se cyklus řízený parametrem často označuje jako počítaný cyklus. Ze stejného důvodu se obvykle u tohoto typu cyklu uplatňuje požadavek, že příkaz P žádným způsobem nesmí měnit hodnotu parametru. Pro tento typ cyklu se také používá označení „cyklus typu forÿ. Znázornění cyklu vývojovým diagramem vidíme na obrázku 6.6. Z tohoto obrázku je patrná funkce parametru. Protože se však jedná o velmi často používanou konstrukci, lze tento cyklus zakreslit speciální značkou pro cyklus. Na obrázku 6.7 vidíme stejný cyklus zakreslený touto značkou. Obě vyjádření jsou z hlediska funkce zcela ekvivalentní.

Obr. 6.6: Cyklus řízený parametrem

6. Algoritmy

61

Obr. 6.7: Cyklus řízený parametrem (zjednodušené znázornění)

6.4 6.4.1

Programování Strukturované programování

Strojově orientované jazyky a starší vyšší programovací jazyky (Basic, Fortran) mají pro řízení běhu programu mechanizmus nazvaný skoky. Ty se dále dělí na podmíněné (skok na jinou část programu se provede při splnění nějaké podmínky) nebo nepodmíněné (skok se provede vždy). „Novějšíÿ vyšší programovací jazyky umožňují tzv. strukturované programování. Jeho podstatou je, že programovací jazyk obsahuje konstrukce, snažící se příkazy skoku „zamaskovatÿ a více odrážet logiku algoritmu. Strukturované programování je vlastně doporučení, jak by měl vypadat dobře napsaný program. Výše uvedené příkazy patří mezi příkazy strukturovaného programování. Jednou z jeho zásad je i pravidlo, že program musí být modulární, tedy musí se skládat z menších částí a ty zase z menších atd., dokud se nedostaneme k příkazům programovacího jazyka. Vlastní hlavní program pak sestává z volání několika modulů, které volají další moduly atd. Dělení na moduly obvykle odpovídá dělení při rozdělování problémů na podproblémy. Těmto modulům se v jazyce Pascal říká procedury.

6.4.2

Objektově orientované programování

V objektovém programování je rozvinuta myšlenka modularity (viz strukturované programování) asi takto: Objekt je aktivní modul, schopný provádět nějakou činnost, obsahující tzv. metody. Objekty mezi sebou komunikují tím, že si zasílají zprávy. Podobné objekty spadají na základě svých vlastností do skupin – tříd (obdoba typu). Mezi třídami existuje tzv. dědičnost, jedna třída může dědit vlastnosti jiné třídy a přidat další, své vlastnosti. Hlavními rysy jsou: zapouzdření – vytvářejí se tzv. objekty, které mohou mít obdobu reálného světa, obsahující kód programu i data, a dědičnost – lze vytvářet nové objekty (nazývané následníci nebo potomci), které dostanou všechny vlastnosti jiného objektu (nazývaného předchůdce nebo rodiče). Tyto vlastnosti mohou pak

62


změnit nebo upravit a přidat další vlastnosti. Polymorfismus – možnost předefinovat u následníka chování jinak, než jaké chování měl jeho předek. Při objektovém přístupu k tvorbě programu nezkoumáme způsob funkce programu, ale způsob změn dat. Objektový program je řízen tokem dat, neboli událostí. Dojde-li k nějaké události, třeba klepnutí myší na určité místo obrazovky nebo stisku klávesy, pak objekt, mezi jehož vlastnosti patří reagovat na tuto událost, zareaguje a pošle zprávu jinému objektu (či více objektům). Ty opět reagují, provedou nějakou činnost a pošlou zprávu dalším objektům atd. Takže v objektovém programování neexistuje vlastně ani hlavní program (jen vstupní procedura), vše je řízeno tokem dat a reakcemi jednotlivých objektů.

6.5

Slovníček důležitých pojmů z oblasti algoritmů

Programování je zápis algoritmu v programovacím jazyce. Tvorba programů má několik fází: přesné určení zadání úkolu, návrh postupu řešení, tvorbu algoritmu a výběr vhodného programovacího jazyka, zápis programu a odstranění syntaktických a logických chyb. Algoritmus je posloupnost operací, které řeší daný úkol. Řešení úkolu musíme zapsat v drobných krocích, které je daný programovací nástroj schopen realizovat. Tyto operace na sebe navazují (závisejí na předchozí), řeší úlohu v konečném počtu kroků. Vývojový diagram je jeden z mnoha vyjádření algoritmu. Je to jeho hierarchické grafické zobrazení. Proměnná je objekt, se kterým pracujeme v rámci programu a je charakterizován svým typem. Typ určuje velikost a charakter dat, která jsou danou proměnnou zpřístupněna. Identifikátor je označení proměnné, objektu, funkce, atd. (např. i, j, pocet, . . . ). Použití znaků v identifikátorech není zcela libovolné. Většinou se jedná jen o písmena a číslice, přičemž se v některých jazycích velikost písmen nerozlišuje. Datový typ určuje velikost a charakter dat a množinu operací s ním spojených. Syntaxe je přesné určení, jak se mají jednotlivé části programu zapisovat. Syntaktické chyby jsou odhaleny během překladu a jsou snadno odstranitelné. Sémantika definuje význam jednotlivých příkazů a programových konstrukcí. Deklarace je část programu, která zavádí nově pojmenovaný symbol, který může být v programu použit. Operátory, funkce, základní příkazy jsou základní stavební prvky programovacího jazyka, jejichž způsob zápisu (syntaxi) a význam (sémantiku) musíme znát. Např. +, −, ∗, /, if, then, else . . .

6. Algoritmy

63

Základní příkazy umožňují definovat takové programové konstrukce jako podmíněný příkaz, příkazy cyklu, podprogram, . . . Strukturované programování je metoda programování, při které dělíme problém do menších podproblémů, a ty znovu do meších podproblémů až se dostaneme na úroveň vyjadřovacích schopností jazyka. Jednotlivé podproblémy vyjadřujeme obvykle procedurami. Objektově orientované programování je nyní nejvíce používaný způsob programování. Program se skládá z objektů, které si zasílají zprávy. Objekty jsou rozděleny do tříd (obdoba typu) a tvoří hierarchickou strukturu. Vizuální způsob tvorby programu nám umožňuje soustředit se na vlastní algoritmus úlohy a grafické uživatelské rozhraní vytvořit z předpřipravených dílů (komponent). Komponenta je část programu s přesně definovaným rozhraním, která se dá samostatně šířit a je opakovaně využitelná.

6.6

Kontrolní otázky

• Jaký je postup vzniku programu? • Na co rozdělíme úlohu, kterou máme naprogramovat? • Co je to algoritmus? • Co je to programovací jazyk? • Jak se zapisoval program dříve a jak se často vytváří dnes? • Co jsou to syntaktické chyby? • Co jsou to logické chyby? • Máme jistotu, že v rozsáhlém fungujícím programu není žádná chyba? Proč? • Co je to algoritmus? Jaké má vlastnosti a jaké vlastnosti musí mít řešená úloha? • K čemu slouží vývojový diagram? • Co je to proměnná a co je to identifikátor? Jak spolu tyto dva pojmy souvisí? • Co to znamená, že proměnná je určitého datového typu? Jak souvisí deklarace s typy proměnných? • Jaké jsou logické a matematické operátory? • Co je to syntaxe programovacího jazyka?

64

Přípravný kurz informatiky • Co je to sémantika programovacího jazyka? • Vyjmenujte základní konstrukce používané v programování a vysvětlete jejich funkci. • V čem spočívá strukturované programování? Jaký je postup řešení úlohy? • V čem spočívá objektové programování? Jaký je postup řešení úlohy? • Vysvětlete pojmy objekt, třída, dědičnost, zpráva, událost, řízení tokem dat.

6.7

Vybrané algoritmy

Poznámka Popsané algoritmy jsou zapsány pomocí vývojových diagramů, které byly probrány v kapitole 6.2.3. Jako ukázka alternativního způsobu zápisu je použit jazyk Pascal s tím, že není striktně dodržena syntaxe jazyka (např. některé proměnné nejsou vždy deklarovány).

6.7.1

Výměna dvou čísel

Příklad: V proměnných a a b máme uložena čísla. Zaměňte hodnoty v obou proměnných navzájem. K dispozici máte proměnnou temp. Řešení: Je velmi snadné. Stačí hodnotu z proměnné a zkopírovat do proměnné temp, poté zkopírujeme hodnotu z b do a a nakonec do b vložíme hodnotu z temp. temp := a; a := b; b := temp; Zápis pomocí vývojového diagramu vidíme na obrázku 6.8. Z obrázku je zřejmé, že blok „obecná činnostÿ může obsahovat více příkazů. Zapsání každého příkazu zvlášť do jednoho bloku je samozřejmě také přípustné.

Obr. 6.8: Výměna dvou čísel s pomocnou proměnnou

Poznámka Tento způsob výměny hodnot lze použít pro jakýkoliv datový typ.

6. Algoritmy

6.7.2

65

Výměna dvou čísel bez pomocné proměnné

Příklad: V proměnných a a b máme uložena čísla. Zaměňte hodnoty obou proměnných navzájem. Tentokrát nemáte k dispozici žádnou pomocnou proměnnou. Řešení: Tentokrát není řešení obecné, lze je použít pouze pro datové typy, které mají nad sebou definovány operace sčítání a odčítání. Tedy čísla ano, ale např. záznamy již nikoliv (např. při výměně dvou záznamů při řazení). K hodnotě a přičteme hodnotu b. Dále do b vložíme (a−b). Nakonec od a odečteme aktuální hodnotu b. Algoritmický zápis je zapsán níže s konkrétními hodnotami. { a = 5, b = 3 } a := a + b; b := a - b; a := a - b;

6.7.3

{ a := 5 + 3 = 8 } { b := 8 - 3 = 5 } { a := 8 - 5 = 3 }

Výpočet faktoriálu

Příklad: Vypočtěte faktoriál ze zadaného čísla. Řešení: Tento příklad lze řešit dvěma způsoby – rekurzivně a nerekurzivně (pomocí cyklu). Zmíníme se o obou variantách: Nerekurzivní verze Zde je řešení evidentní – prostě násobíme hodnotou, kterou v každém dalším kroku zmenšujeme o jedničku. funkce Faktorial(N: integer) : integer; begin Faktorial := 1; for i:= N downto 1 do Faktorial := Faktorial * i; end; Stejný algoritmus lze zapsat i vývojovým diagramem na obrázku 6.9. Všimněte si záporného kroku počítaného cyklu. Záporné číslo značí, že hodnotu řídící proměnné po každé iteraci snižujeme, místo toho, abychom ji zvyšovali. V algoritmickém zápise je tato skutečnost vyjádřena slovem downto. Poznámka Tento příklad je jeden z mnoha možných. Nemáme např. ošetřen případ, kdy N < 0 (pokud to nezahrneme do testovací podmínky). Algoritmus by bylo možné modifikovat, aby „kontrolaÿ byla přímo v opakovací smyčce. Zkuste toto řešení najít.

66


Obr. 6.9: Výpočet faktoriálu Rekurzivní verze Rekurzivní volání znamená, že funkce volá sebe sama. Pro mnoho typů úloh je rekurzivní řešení mnohem jednodušší a přehlednější než nerekurzivní. Nevýhodou může být pro méně zkušeného programátora zdánlivá nesmyslnost kódu. funkce Faktorial(N: integer) : integer; begin if (N > 1) then Faktorial := Faktorial(N - 1) * N; else Faktorial := 1; end; Při pokusu o zápis rekurzivního algoritmu pomocí vývojového diagramu zjistíme, že pomocí dosud vysvětlených značek se jedná o neproveditelný úkol, protože nedisponujeme žádnými prostředky pro volání podprogramu s předáním návratové hodnoty (funkce). Tyto prostředky ve vývojovém diagramu sice existují, protože však používáme vývojové diagramy pouze pro zpřehlednění výkladu, nepovažujeme za účelné zabíhat do takových detailů. Poznámka 1 Všimněte si, že v rekurzivní verzi se nevyskytuje cyklus. V tomto případě je nahrazen právě rekurzí.

6. Algoritmy

67

Poznámka 2 Rekurze samozřejmě nemá jen samé výhody. Mezi nevýhody patří vyšší náročnost na paměť (v každém zanoření si musíme pamatovat návratovou hodnotu), rychlost, apod.

6.7.4

Zjištění maximální, minimální hodnoty

Příklad: Ze zadané posloupnosti čísel vyberte maximum (minimum). Řešení: Při průchodu posloupností si musíme maximum pamatovat ve zvláštní proměnné a testujeme, zda aktuální hodnota není větší než maximum. Pokud ano, uložíme tuto hodnotu do proměnné max. Po ukončeném průchodu posloupností máme v této proměnné maximum. Analogicky pro minimum. { Máme k dispozici pole velikosti N čísel } var Pole : array[1..N] of integer; max : integer; max := Pole[1]; for i := 2 to N do begin if (Pole[i] > max) then max := Pole[i]; end; Ekvivalentní zápis pomocí vývojového diagramu vidíme na obrázku 6.10.

6.7.5

Zjištění klesající/rostoucí posloupnosti

Příklad: Máme zadanou posloupnost čísel. Stanovte po průchodu touto posloupností, zda je klesající/rostoucí. Řešení: Tento úkol je ve skutečnosti obdoba předcházející úlohy s tím rozdílem, že použijeme proměnnou typu Boolean. Na počátku předpokládáme, že je posloupnost klesající a pokud během procházení zjistíme, že některý prvek toto pravidlo porušuje, změníme hodnotu této proměnné na false. V tomto okamžiku můžeme výpočet ukončit. Analogicky pro rostoucí posloupnosti. { Máme k dispozici pole velikosti N čísel } var Pole : array[1..N] of integer; klesajici : Boolean; klesajici := true; for i:=1 to (N-1) do

68


Obr. 6.10: Hledání maxima begin if (Pole[i] < Pole[i+1]) then begin klesajici := false; exit; end; end;

{ ukončení programu }

Popsaný algoritmus lze zapsat pomocí vývojového diagramu obdobným způsobem, jako algoritmus pro vyhledávání maxima. Zkuste si to.

6.7.6

Eratosthenovo síto

Příklad: Určete všechna prvočísla z N čísel. Řešení: První problém, který budeme řešit, je uložení těchto čísel. Jako první nás možná napadne – z jakého důvodu ukládat? Stačí přece každé číslo zkoumat, zda je či není prvočíslo . . .

6. Algoritmy

69

Další problém – jak vůbec tato prvočísla vyhledat? Naivní algoritmus, který by pro každé číslo zkoumal, zda je prvočíslo, je extrémně neefektivní (byť paměťově velmi nenáročný). Naštěstí existuje algoritmus zvaný Eratosthenovo síto. Myšlenka je následující: uložíme všechna zkoumaná čísla do pole a budeme postupně vyškrtávat násobky prvočísel – nejdřív tedy vyškrtneme všechna sudá čísla, poté násobky čísla tři atd. Na závěr je potřeba zjištěná prvočísla vypsat. i := 2; while (i < N) do begin j := 2*i; while (j <= N) do begin Pole[j] := 0; j := j + i; end; repeat i := i + 1; until (Pole[i] > 0); end; for i:=1 to N do if Pole[i] > 0 then write(Pole[i]);

{ budeme vyškrtávat od dvojnásobku... }

{ vyškrtáváme násobky ... } { posun indexu na (n+1). násobek }

{ nastavíme i na další prvočíslo }

{ vypíšeme nevyškrtnutá čísla }

Poznámka 1 První nápad bylo tedy pole čísel. Zkuste popřemýšlet nad další (a z hlediska spotřebované paměti efektivnější) reprezentací (bitové pole?). Co by bylo potřeba k použití této možnosti vytvořit (z hlediska strukturovaného programování)? Poznámka 2 Opět připomínám, že v našem reálném světě téměř vždy platí něco za něco – naivní algoritmus sice spotřebuje příliš mnoho strojového času, ale nemá prakticky žádné paměťové nároky. Naproti tomu Eratosthenovo síto je sice rychlý algoritmus, ale stojí nás pro vysoké hodnoty čísel N mnoho paměti. Opět bychom mohli udělat kompromis – provádět tento algoritmus např. pro čísla 1.. N4 , N4 +1.. N2 . . .

6.7.7

Bubble sort – řazení

Příklad: Seřaďte posloupnost daných čísel vzestupně pomocí algoritmu Bubble sort. Řešení: Algoritmus pracuje následovně: procházíme posloupností a pokud je následující prvek menší než aktuální, tak je navzájem vyměníme. Průchod opakujeme

70


tak dlouho, dokud nacházíme dvojice, které porušují seřazenost posloupnosti. Tímto způsobem nám „probublajíÿ hodnoty na správná místa. { řadíme pole N prvků typu Typ } var Pole : array[1..N] of Typ; temp : Typ; serazena : Boolean; serazena := false; while (not serazena) do begin serazena := true; { předpoklad, že je již seřazena } for i:=1 to (N-1) do begin if (Pole[i] > Pole[i+1]) then begin temp := Pole[i]; { vyměníme prvky } Pole[i] := Pole[i+1]; Pole[i+1] := temp; serazena := false; { zjistili jsme, že nebyla seřazena } end; end; end; Na obrázku 6.11 vidíme, že odpovídající vývojový diagram je skutečně složen z bloků popsaných v kapitole 6.3.2: cyklus s podmínkou na začátku (while), počítaný cyklus a podmíněné příkazy. Poznámka Tento algoritmus patří k nejpomalejším, ale nejjednodušším řadícím algoritmům (s výjimkou „řazeníÿ seřazené posloupnosti). Existuje celá řada modifikací (např. to, že v každém následujícím cyklu procházíme (n − 1) prvků, protože každým průchodem na konec pole „probubláÿ největší hodnota a není třeba ji testovat. Zkuste tuto modifikaci implementovat.

6.7.8

Matice

Příklad: Máme matici A o velikosti N × N čísel. Vytvořte transponovanou matici B. Poznámka Transponovaná matice je taková, že prvky, které původně byly na řádcích, jsou nyní ve sloupcích. Tzn. prvky z prvního řádku jsou nyní v prvním sloupci, atd.

6. Algoritmy

71

Obr. 6.11: Řadící algoritmus Bubble Sort Řešení: Řešení je nasnadě – budeme číst prvky z matice A a zapisovat je na správné místo v matici B var A,B : array [1..N,1..N] of Integer; for i := 1 to N do for j := 1 to N do B[i,j] := A[j,i]; Příklad: Modifikace – pokud pracujeme s rozsáhlými maticemi, může být někdy nutné transponovat matici do „sebe samaÿ.

72


Řešení: V tuto chvíli budeme muset využít pomocnou proměnnou (zdatnější by se mohli obejít i bez ní – viz kapitola 6.7.2) a budeme muset správně omezit počty průchodů, abychom si nepřehodili již přehozené prvky. Zde bude nejobtížnějším úkolem správně indexovat, abychom si omylem „nesáhliÿ vedle. Také je evidentní, že nemusíme transponovat prvky na hlavní diagonále – zrychlí nám to dobu provádění. var A : array [1..N, 1..N] of Integer; temp : Integer; for i := 1 to (N-1) do for j := (i+1) to N do begin temp := A[i,j]; A[i,j] := A[j,i] A[j,i] := temp; end;

6.8


Příklad 6.1: Pomocí vývojového diagramu vyjádřete algoritmus, který vypočte absolutní hodnotu zadaného čísla A. Příklad 6.2: Navrhněte a pomocí vývojového diagramu zapište algoritmus, který provede transpozici čtvercové matice M (záměnu řádků a sloupců) bez toho, aby byla tvořena nová matice – program může pouze měnit vstupní matici. Příklad 6.3: Navrhněte a pomocí vývojového diagramu zapište algoritmus, který provede reverzi pole prvků – tj. první prvek bude na posledním místě, druhý na předposledním, atd.

Přípravný kurz informatiky

Recommend Documents