Návrat na detail prednášky / Stiahnuť prednášku / Technická Univerzita Košice / Letecká fakulta / Základy informatiky

alforitmy-základy tvorby + teoria (algoritmy.doc)

Riešenie každej úlohy sa skladá z postupnosti logických úsudkov (Aristoteles). Počítačový program sa skladá z množiny príkazov, ktoré riešia zadanú úlohu. Pred písaním programu je potrebné nájsť algoritmus, postup  riešenia úlohy (Postupnosť krokov).  Proces hľadanie algoritmu pre danú úlohu je algoritmizácia úlohy.

Algoritmizácia úlohy má tri etapy:

formulácia- slovné zadanie úlohy ( definovanie vstupov a výstupov úlohy)
analýza- úloha sa zovšeobecňuje, určujú sa podmienky postupu ( popis ako získať z daných vstupov dané výstupy)
zostavenie algoritmu- presné vyjadrenie logiky a postupu riešenia.

Výsledkom algoritmizácie úlohy je algoritmus. Algoritmus je presný  systém pravidiel určujúci postup riešenia zadanej úlohy, pri ktorom získame z daných vstupov požadovaný výstup. Rozdiel medzi algoritmom a programom počítača je v tom, že program musí vyhovovať až do najmenších detailov pravidlám konkrétneho programovacieho jazyka. Aj najmenšia chyba môže viesť k nekontrolovateľnému správaniu počítača. Ten istý algoritmus môže byť realizovaný v rôznych programovacích jazykoch .

Každý algoritmus musí mať nasledovné vlastnosti:

1. elementárnosť- postup je zložený z činností, ktoré sú pre realizátora elementárne a zrozumiteľné.
2. determinovanosť- pre každý krok algoritmu je jednoznačne určený nasledujúci krok.
3. hromadnosť- algor. musí vždy vychádzať z meniteľných vstupných údajov,t.j.mal by byť použiteľný pre riešenie každej úlohy daného typu.
4. rezultatívnosť- algor. vedie po konečnom počte krokov k výsledku.
5. konečnosť- postup skončí vždy v určitom čase a po vykonaní konečného počtu činností.
6. efektívnosť- postup sa uskutočňuje v čo najkratšom čase a s využitím čo najmenšieho počtu prostriedkov.

Zápis algoritmov

1. slovný zápis- pre vyjadrenie algor. je nám blízky, dobre sa nám v ňom uvažuje, ale ako prostriedok analýzy zložit. úloh je nevýhodný pretože je neprehľadný, nedostatočne zvýrazňuje zmeny postupu, môžu sa v ňom vyskytnúť nepresnosti
2. pomocou vývojových diagramov- vývojový diagram úlohy je bloková grafická reprezentácia postupnosti operácií, kt. má realizovať úlohu v súlade s príslušným algoritmom.

Základné pojmy - algoritmy.doc súbor (algoritmus, program, vstupné údajé výstupné údaje, zápis algoritmov, sekvenčnosť, binárne vetvenie, cyklus, typy cyklov, premenná, konštanta, výraz, príkaz priradenia, podmienený príkaz, algoritmizácia, dátové štruktúry - celočíselné, reálne,  znakové, logické, polia, záznam, vývojový diagram )

Vývojový diagram

Algoritmus možno popísať aj slovne, ale prehľadnejší spôsob zadania algoritmu je bloková schéma alebo vývojový diagram.
Vývojový diagram je znázornenie algoritmu, postupu riešenia danej úlohy. Vývojový diagram môže obsahovať :

1. príkaz na načítanie vstupov,
2. príkaz na priradenie hodnôt premenným,
3. rozhodovacie bloky so znakmi "+", "-" ("+" znamená, že podmienka je splnená a znamienko "-", že nie je splnená)

Overenie správnosti algoritmovOverenie správnosti algoritmov možno realizovať tak, že do schémy algoritmu dosadíme konkrétne hodnoty a vykonáme jeden  krok za druhým podľa vývojového diagramu.  Vývojový diagram je navrhnutý správne, keď pre každý  vstup z definičného oboru dosiahneme požadovaný výstup. Po overení správnosti vývojového diagramu možno pristúpiť k napísaniu programu v konkrétnom programovacom jazyku.

Úloha - Najväčší spoločný deliteľ čísiel x, y

Poznámky :

1) Vývojové diagramy častokrát prezentujú funkciu v matematickom zmysle.  ( príklad NSD : N x N - > N) Každá matematická funkcia má svoj definičný obor, tak isto aj algoritmy majú svoj definičný obor. Keď zadáme vstupy do algoritmu, ktoré nepatria do definičného oboru, tak algoritmus nemusí byť funkčný. ( Príklad, keď do nášho algoritmu NSD napr. dosadíme nesprávne, záporné hodnoty x = -12, y = -16 tak v algoritme vznikne nekonečný cyklus )

2)  Jeden problém môže riešiť viac algoritmov. Problém najväčšieho spoločného deliteľa poznali aj v starovekom Grécku.
Euklides tento problém riešil nasledovným algoritmom (slovný zápis algoritmu )

Vstup: X, Y kladné celé čísla , Výstup: NSD(X,Y)i)            a = X, b = Y, ii)     MOD = a/b  { MOD pomocná premenná, zvýšok po celočíselnom delení, v matematike je to funkcia modulo }
iii)      a = b
iv)           b = MODv)       Opakuj kroky ii) - iv) kým platí podmienka (b <> 0).
vi)      NSD(X,Y)=a

Obsah :

Cvičenie vysvetluje základné okruhy predmetu Programovanie a využitie počítačov na Ústave aeronautiky , TU Košice.
Medzi základné okruhy predmetu patria vývojové diagramy. Pomocou  príkladu súčtu čísiel 1 + 2 + .. + N je vysvetlený pojem vývojového diagramu, algoritmu a zložitosti algoritmu.
Ďalšiou oblasťou predmetu je programovanie v jazyku C++. Uvedený príklad (výpočet faktoriálu) vysvetluje datové typy int a double a rozdiely medzi datovými typmi.
Ďalší okruh predmetu je algoritmizácia úloh. Algoritmizácia je dôležitou súčasťou predmetu programovania, na základe algoritmov možno písať programy. Na popis postupu, ako algoritmizovať úlohy (ako hľadať riešenie), slúži kombinatorická hra NIM. ( zložitejší problém )

Cieľom tejto časti cvičenia je vysvetliť pojem zložitosti algoritmov. Vieme že jeden problém môžeme riešiť viacerými algoritmami. Rôzne algoritmy, ktoré riešia ten istý problém môžeme porovnať podľa počtu vykonaných operácií .1) Nakreslíte vývojový diagram na výpočet  sumy  1 + 2 + 3 + .. + n, kde n>100 je celé číslo.

1a)

1b)

Cieľom tejto časti cvičenia je ukázať použitie a význam dátových typov  int,  double,  a upozorniť na ich správne použitie.2) Napíšte program na výpočet n! faktoriálu, n>0, celé číslo.  Tento program môžeme napísať v jazyku C++ takto

#include <stdio.h>#include <conio.h>int cislo,vysledok,i;main(){clrscr();printf("Vypocet faktorialu\n\n");printf("Zadajte cislo:");scanf("%d",&cislo);vysledok=1;for(i=1;i<=cislo;i++) vysledok=vysledok*i;printf("\n\n%d!=",cislo);printf("%d",vysledok);getch();}

Tento program po spustení v IDE C++ napíše:

Vypocet faktorialu
Zadajte cislo: 77!  = 5040

Po zadaní vstupu  Zadajte cislo: 8 program napíše 8! = -25216, čo nie je správne. Chyba vznikla preto, lebo v premennej vysledok došlo k pretečeniu, premenná je typu int, čo je celočíselný typ rozsahu  [-32768, 32767]. Náš algoritmus môžeme upraviť tak, že celočíselný rozsah premennej vysledok nahradíme s rozsahom reálneho čísla, dátovým typom double. Potom je nutné opraviť deklaráciu premennej double vysledok; inicializáciu vysledok=1.0; a pri formatovaní výstupu, format printf("%f",vysledok);  
Program teda, môžeme modifikovať takto :     int cislo,i,
     double vysledok;
       .........
     vysledok=1.0;    
       .........
     printf("%f",vysledok);Takto v premennej vysledok budú už double - reálne hodnoty, ktoré majú väčší rozsah  [3.4E-38, 3.4E+38], preto po zadaní Zadajte cislo: 8 , dostaneme správny výsledok
             8!  = 40320.00000
      

V ďalšej časti cvičenia budeme sa zaoberať s algoritmizáciou úloh, konkrétnejšie budeme sa zaoberať s kombinatorickou hrou NIM. Pri algoritmizácii úloh v prvom kroku je potrebné oboznámiť sa s problémom. Problém hry NIM popisujú ich pravidlá, ktoré možno vyskúšať v hre. Táto hra môže slúžiť aj na meranie schopnosti hľadania algoritmov. Táto úloha je zložitá preto môžeme celý problém rozložiť na čiastočné problémy, ktoré vysvetlujú aj analýzu celej problematiky.

NIM1 : Napíšte program v jazyku  C++, ktorý vygeneruje počiatočnú pozíciu hry NIM. (Nová hra)
(Vlastnosti počiatočnej pozície : počiatočná pozícia má 4 riadky ( môže mať ľubovoľný počet ), v každom riadku je náhodne vygenerovaný počet zápaliek ( 1 až 8 (maximálny počet môže byť ľubovoľný), miesto zápaliek v textovom móde C++ budeme používať znak x. Pozícia v hre NIM pre programy je charakterizovaná so štvoricou čísiel [p1,p2,p3,p4], tento program vygeneruje do prvého riadku p1 znakov x, .. a do štvrtého riadku p4 znakov )
Príklad počiatočnej pozície :

xxxxxxxxxxxxxxxxxxx

NIM2 : Napíšte program na odobratie j zápaliek z i-tého riadku v hre NIM (Ťah - Hráč)(Výstupom tejto časti programu je číslo riadku i a počet zápaliek j na odobratie z daného i-tého riadku)
Príklad :

xxxxxxxxxxxxxxxxxxxZadajte Vas tah (cislo riadku, pocet zapaliek) :

NIM3 : Napíšte program na vyhodnotie ťahu (i,j) v hre NIM.(Na vstupe je pozícia hry [p1,p2,p3,p4] a dvojica (i,j), treba tu otestovat, ci 1<=i<=4 a j<=pi vtedy ťah je možný, keď ťah nie je možný, tak zavolať program NIM2)

NIM4 : Napíšte program na realizáciu ťahu (i,j) hráča v hre NIM.(Na vstupe je pozícia hry [p1,p2,p3,p4] a ťah - dvojica (i,j), vieme, že ťah (i,j) je možný, realizácia ťahu znamená zmenu pozície[p1,p2,p3,p4] na novú pozíciu kde pi = pi - j a potom nakreslenie novej pozície )

NIM5 : Napíšte program na vyhodnotenie pozície [p1,p2,p3,p4] v hre NIM.([p1,p2,p3,p4] = [0,0,0,0], tak koniec hry,
- keď posledný ťah robil PC, tak Hráč prehral, treba aktualizovať výsledok, to je dvojica [Hrac,PC], PC=PC + 1 a napísať na obrazovku, že Chcete odvetu ?,
- keď posledný ťah robil hráč tak treba aktualizovať výsledok, Hrac=Hrac + 1 a napísať na obrazovku Gratulujem vyhrali ste, v prípade keď (p=[0,0,0,0]) treba s opýtať Nova hra., keď áno tak skok na NIM1.Keď [p1,p2,p3,p4] <> [0,0,0,0] a posledný ťah robil PC, tak treba zavolať NIM2, keď posledný ťah robil Hráč tak zavolať program NIM6 - ťah PC )

NIM6 : Napíšte program na odobratie j zápaliek z i-tého riadku v hre NIM (Ťah - PC - hlavný program)(Tento algoritmus, ako vyberá PC ťah, simuluje postup úplneho začiatočníka v tejto hre. Vstup [p1,p2,p3,p4] pozícia v hre, Výstup (i,j) - ťah PC. Postup náhodný výber 1<=i<=4, tak, že 0 < pi, potom j je náhodné číslo z intervalu 1..pi, skok na NIM3 )