ALGORITMIZACEÚVODNÍ PŘEDNÁŠKA

2

SLOVO ALGORITMUS VZNIKLO ZE JMÉNA ARABSKÉHO MATEMATIKA AL-KHWARIZMIHO, KTERÝ V DEVÁTÉM STOLETÍ SEPSAL ROZSÁHLOU KOLEKCI ALGORITMŮ.

POČÍTAČOVÉ ALGORITMY MAJÍ VĚTŠINOU PODOBU PROGRAMŮ. PROTOŽE SE TERMÍN ALGORITMUS VZTAHUJE SPÍŠE K POSLOUPNOSTI OPERACÍ NEŽ KE KONKRÉTNÍMU ZPŮSOBU, JAKÝM JSOU POPSÁNY, JE MOŽNÉ VYJÁDŘIT STEJNÝ ALGORITMUS V MNOHA RŮZNÝCH PROGRAMOVACÍCH JAZYCÍCH.

???

4

EUKLIDOVA ÚLOHA

Úloha: najděte největšího společného dělitele čísel 6 a 15

Řešení: Popišme postup tak, aby byl použitelný pro dvě libovolná přirozená

čísla, nejen pro 6 a 15:

• označme zadaná čísla x a y a menší z nich d

• není-li d společným dělitelem x a y, pak zmenšíme d o 1, test opakujeme a skončíme, až d bude společným dělitelem x a y

Poznámka: Význam symbolů x, y a d použitých v algoritmu:

• jsou to proměnné (paměťová místa), ve kterých je uložena nějaká hodnota, která se může v průběhu výpočtu měnit

5

ŘEŠENÍ

Úloha: najděte největšího společného dělitele čísel 6 a 15

krok x y d poznámka6 15 ? zadání vstupních dat

1 6 15 6

2 6 15 6 d není dělitelem y, proveď krok 3

3 6 15 5

2 6 15 5 d není dělitelem x, proveď krok 3

3 6 15 4

2 6 15 4 d není dělitelem x ani y, proveď krok 3

3 6 15 3

2 6 15 3 d je dělitelem x i y, proveď krok 4

4 6 15 3 výsledek je hodnota 3

6

ZOBECNĚNÍ

Úloha: najděte největšího společného dělitele Přesnější popis:

Vstup: přirozená čísla x a y

Výstup: nsd(x,y)

Postup:

1. Je-li x<y, pak d má hodnotu x, jinak d má hodnotu y

2. Opakuj krok 3, pokud d není dělitelem x nebo d není dělitelem y

3. Zmenši d o 1

4. Výsledkem je hodnota d Sestavili jsme algoritmus pro výpočet největšího společného dělitele dvou

přirozených čísel

7

NAVRHNĚTE ALGORITMUS PRO PŘÍPRAVU KÁVY

1.UVAŘIT KÁVU

2. ZAPNOUT SPORÁK

3. UVAŘIT NEZBYTNÉ MNOŽSTVÍ VODY

4. NASYPAT MLETOU KÁVU DO ŠÁLKU

5. ZALÍT KÁVU VAŘÍCÍ VODOU

6. OSLADIT PODLE CHUTI

7. POČKAT, NEŽ KÁVA ZÍSKÁ PŘÍSLUŠNÉ AROMA.

8

SESTAVTE ALGORITMUS

9

ŘEŠENÍ

10

VZESTUPNÉ SETŘÍDĚNÍ BALÍČKU KARET

1. KARTU VYJMEME A TA SE STANE PRVNÍ KARTOU SETŘÍDĚNÉHO BALÍČKU. PAK HLEDÁME NEJMENŠÍ KARTU VE ZBYTKU BALÍČKU. POSTUP SE OPAKUJE, DOKUD NEVYČERPÁME NESETŘÍDĚNÉ KARTY. PROTOŽE MÁME n KARET, Z NICHŽ PRO KAŽDOU POTŘEBUJEME n POROVNÁNÍ, ALGORITMUS JE ŘÁDU n^2.

2. REKURZIVNÍ TŘÍDĚNÍ – PROJDEME BALÍČKEM JEDNOU A PŘEMÍSTÍME KARTY S HODNOTOU MENŠÍ NEŽ PRŮMĚR DO SPODNÍ POLOVINY BALÍČKU; KARTY S NADPRŮMĚRNÝMI HODNOTAMI ZŮSTANOU V HORNÍ POLOVINĚ. PAK KAŽDOU POLOVINU BALÍČKU SETŘÍDÍME STEJNÝM ALGORITMEM. REKURZIVNÍ POUŽITÍ ALGORITMU NA OBĚ POLOVINY BALÍČKU ZNAMENÁ JEHO REKURZIVNÍ POUŽITÍ NA KAŽDOU POLOVINU PŮLBALÍČKŮ ATD. KAŽDÝ REKURZIVNÍ KROK PŮLÍ POČET KARET, KTERÉ SE MAJÍ TŘÍDIT; REKURZE KONČÍ, ZBÝVÁ-LI JEDINÁ KARTA – V TOM PŘÍPADĚ JE JIŽ SETŘÍDĚNÁ. VZHLEDEM K TOMU, ŽE ALGORITMUS ZAHRNUJE OPAKOVANÉ DĚLENÍ KARET, DOKUD NEMÁME POUZE JEDINOU , POTŘEBUJE ČAS ÚMĚRNÝ TOMU, KOLIKRÁT LZE ROZDĚLIT n KARET – JINÝMI SLOVY DVOJKOVÝ LOGARITMUS POČTU KARET

11

ELEGANTNĚJŠÍ ALGORITMUS

EXISTUJE ELEGANTNĚJŠÍ REKURZIVNÍ ALGORITMUS, PRO KTERÝ NEPOTŘEBUJEME, ABY BYLY KARTY SEKVENČNĚ OČÍSLOVÁNY; JE VHODNÝ NAPŘ. K SEŘAZENÍ VELKÉHO POČTU VIZITEK.

ALGORITMUS SE NAZÝVA MERGE SORT

( TŘÍDĚNÍ SLÉVÁNÍM)

TŘÍDĚNÍ SLÉVÁNÍM TĚŽÍ ZE SKUTEČNOSTI, ŽE JE JEDNODUCHÉ SLÍT DVA JIŽ SETŘÍDĚNÉ SLOUPEČKY DO JEDNOHO (ROVNĚŽ SETŘÍDĚNÉHO) TAK, ŽE POSTUPNĚ BEREME NEJVYŠŠÍ KARTY Z JEDNOHO NEBO DRUHÉHO SLOUPCE (VŽDY BEREME TU VYŠŠÍ).POKUD SLOUPEC SESTÁVÁ Z JEDINNÉ KARTY , PAK JE JIŽ SETŘÍDĚNÝ. JINAK ROZDĚL SLOUPEC NA DVA A REKURZIVNĚ POUŽIJ „MERGE SORT“ K SETŘÍDĚNÍ OBOU POLOVIN A JEJICH ZKOMBINOVÁNÍ S VYUŽITÍM VÝŠE POPSANÉ PROCEDURY

12

PROBLÉM OBCHODNÍHO CESTUJÍCÍHO

DOMÁCÍ ÚKOL

End of Lecture

Good Night.