Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 30% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se PHP
Discount week - April - 30

15. diel - K čomu sú algoritmy?

V predchádzajúcom cvičení, Riešené úlohy k 11.-12. lekciu C # .NET, sme si precvičili získané skúsenosti z predchádzajúcich lekcií.

Po začiatkoch, kedy si sa zoznámil či zoznámila s tým, čo je to premenná, ako funguje cyklus for a kedy použiť switch, sa ponúka otázka, čo ďalej? Pravdepodobne by mali prísť na rad objekty, či nejaká tvorba HTML s CSS, Bootstrap či sa vrhnúť na Android. Aj keby ste sa venovali však čisto jazyku C, stále je základná syntax len akési podhubie, z ktorého sa skladajú dobré programy. V tomto článku si povieme niečo o tom, prečo by nás algoritmy mali zaujímať a prečo sa im nejde vyhnúť (pre tvoje zdravie a tvojho budúceho šéfa).

Čo je to algoritmus?

V tej najjednoduchšej definícii je algoritmus postup pre riešenie konkrétneho problému. Čo musí algoritmus spĺňať, aký má byť atď., Na to sú na webe iné články. My sa uspokojíme s riešením problému. Programovanie, viac než takmer akékoľvek iné povolanie, je o riešení problému. Aj keď máte v hlave predstavu treba nové hry či fungujúci aplikácie pre trh, vzápätí narazíte na niekoľko problémov, s ktorými sa musíte nejako popasovať a zvoliť si konkrétny metódu riešenia. Najskôr sa pozrime na dva hlavné problémy programov.

Pamäť

Hoci by sa zdalo, že slovné spojenie "nedostatok pamäte" je fráza z učených kníh na konci minulého storočia, stretávame sa s tým všetci. Zvlášť, ak budete písať aplikácie pre Android. Ak vaša aplikácia bude zaberať 1GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, keď sa zväčší pamäť, zväčší sa aj veľkosť programov as nedostatkom pamäte sa musíme zápasiť nanovo.

Čas

Ak je problém s pamäťou znepokojujúce, čas je úplne hrôzostrašný. Používatelia aplikácií majú príšernú vlastnosť, nedočkavosť. Keď napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď ... nemaže si med okolo úst, aj my sme takí užívatelia. Nechceme čakať, až náš skvelý program vyhodí výsledok. Nemusí to byť ani zložité výpočty. Ak programujeme hru, očakávame, že hneď po stlačení klávesy sa panáčik pohne. Očakávame, že po otvorení okna sa nám zobrazí zoznam užívateľov zoradený podľa mena.

Konkrétne príklady pre algoritmizácia

Ukážeme si, že všetky ostatné problémy sa priamo alebo nepriamo dotýkajú týchto dvoch základných kameňov úrazu.

Interakcie so svetom

Tento výukový obsah pomáhajú rozvíjať nasledujúce firmy, ktoré možno hľadajú práve teba!

Ak ste zaregistrovali hru Kingdom Come Deliverance, je to hra, ktorá sa môže pochváliť svetom, kde môžete interagovať s každou postavou as mnohými objekty. To má niekoľko problémov, prvá je napríklad pamäťový nárok, keby sme každú postavu a každý domček poctivo vytvorili, svet o veľkosť mesta s 300 ľuďmi by zaberal obrovské množstvo pamäte, ktorú by nakoniec hráč asociál vôbec nevyužil ...

Príbeh zo života

Tu si predstavme, že máme E-shop pre predaj jedného kusu oblečenia, konkrétne kožených búnd. Náš e-shop má rôzne animácie pre predaj búnd. Lenže potom zistíte, že váš program má fungovať aj v angličtine. Dobre, dáte jednoduchý if-else pre jazyky a prepíšete stránku do angličtiny. Lenže potom sa ozvú ľudí z Nemecka, že by bolo dobré tam dať aj nemčinu. Dobre, dáte tam i nemeckú verziu. Potom si tam šéf vymyslí, že by ste mohli pridať aj bazár kožených búnd, čo je super nápad, ale budete to kodi vy. Najskôr na to stránka nebola pripravená, takže robíte novú stránku s odkazom na pôvodnú, ktorá je zase trojjazyčný, tentoraz už zvolíte efektívny návrh, keby firma prenikla do Francúzska. Bazár bude formou aukcií, zadáte čas a potom čakáte, či ľudia môžu prihadzovať. Lenže sa ukázalo, že kolegovia z Ruska mohli prihadzovať aj po tom, čo váš čas ubehol a kolegovia z Anglicka prišli o hodinu. Tak to ľahko poupravíte.

Rozrástli ste sa a máte toľko búnd, že sa zákazníci ťažko orientujú, tak sa váš šéf rozhodne, že bundy rozdelíte do kategórií, a zákazník bude môcť vyhľadávať podľa ceny a mená. Dobre, nachystáte si kávu a idete na to. Našli ste si návod, ako niekto naprogramoval vyhľadávanie podľa ceny aj podľa mena a máte to tam. Sotva to dopíšete, a šéf príde s tým, že by bolo pekné, keby zákazník mohol pridať kritériá a že by mohol hľadať napríklad len zo svojich troch obľúbených značiek a v nejakom cenovom rozmedzí .. Objednáte si na budúci týždeň dovolenku a začnete písať. Nájdete si riešenie pre viacnásobné kľúče pri vyhľadávaní a niekoľkofázovou triedenia. Za týždeň to všetko máte a už sa tešíte, ako si oddýchnete, keď v tom vám volá zákaznícka linka, že váš program nefunguje. Kód, ktorý ste stiahli z netu, nefunguje pre veľké dáta. Vaša niekoľkých-jazyková stránka trpí tým, že tam niekedy skáče iný jazyk a vy máte možnosť si na dovolenku zobrať vašu prácu a vyriešiť všetko, čo za vás "pokazil" niekto iný.

Čo s tým?

Tu sme sa dotkli hneď dvoch tém. Prvá téma, ktorým sa venujú tieto články XXXXX, je otázka správnych techník v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru šiel ako po masle. To druhé je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Ak najskôr triediť, potom až osekať či naopak. A sme pri otázke času, ak najprv osekáme, potom napríklad z desaťtisícov položiek triedime len 134. A tá rýchlosť je potom jasná. Navyše, ak len tak prijímame kód niekoho iného, musíme mu teda veriť tomu, že vie, čo to robí. Síce si môžeme kód vyskúšať, ale čo keď jeho algoritmus funguje len pre malé dáta?

Je veľa problémov, ktoré nikto neriešil a mali by sme vedieť, ako postupovať pri riešení problémov. K tomu slúžia naše sekcie pre výučbu algoritmov.

Ukážka na záver - triedenie pomocou selection sort

Skúsme si teraz sami skúsiť, ako by sme mohli čísla v poli zotrieďiť. Skúsme použiť ten najzákladnejší a najskôr najmenej vhodný, triedenie výberom.

Idea algoritmu (neefektívne selection sort)

Môžeme si povedať, že v Hlavička poli vždy vyberieme najmenší doteraz nevybratý prvok a ten vložíme do nového poľa. Potom budeme vyhľadávať väčšie:

0. (3,1,5,4)
1. (1)
2. (1,3)
3. (1,3,4)
4. (1,3,4,5)

Prečo je tento kód neefektívne? Pretože si musíme vytvárať pole bokom, tzn. pre pole veľkosti milión vytvoríme druhej pole o rovnakej veľkosti.

Idea algoritmu (efektívna selection sort)

Pole budeme triediť na mieste, tak aké je aj znenie tohto algoritmu.

Majme poľa veľkosti n. Pôjdeme od prvého prvku poľa a nájdeme najmenší prvok. Ten vymeníme s prvým prvkom. Vieme, že menšie prvok sa v poli nevyskytuje, takže máme jeden zoradený prvok. Posunieme sa a hľadáme najmenší prvok vo zvyšku poľa. Ten zase vymeníme s druhým atď ... Ukážka algoritmu:

0. (3,1,5,4)            původní pole
1. (1,3,5,4)            nejmenší je 1, tedy vyměníme 1 s 3
2. (1,3,5,4)            nejmenší je 3, 3 je na vhodném místě, neměníme nic
3. (1,3,4,5)        nejmenší je 4, vyměníme 4 a 5, zbyl nám poslední prvek, který
                        musí být největší, proto algoritmus končí, máme setříděno

Teraz si predvedieme jeho implementáciu:

public static void selectionSort(int[] pole) {
for (int i = 0; i < pole.length - 1; i++) {
    int indexMinima = i;
    for (int j = i + 1; j < pole.length; j++) {
    if (pole[j] < pole[indexMinima]) indexMinima = j;
    }
    int temp = pole[i];
    pole[i] = pole[indexMinima];
    pole[indexMinima] = temp;
    }
}

Teraz už mi nezostáva, než tí popriať veľa zdaru sa svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by normálneho človeka nenapadli. Ale o tom to predsa je, že?


 

Predchádzajúci článok
Riešené úlohy k 11.-12. lekciu C # .NET
Všetky články v sekcii
Základné konštrukcie jazyka C # .NET
Článok pre vás napísal Ondřej Michálek
Avatar
Ako sa ti páči článok?
Ešte nikto nehodnotil, buď prvý!
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Aktivity (1)

 

 

Komentáre

Avatar
Honza
Člen
Avatar
Honza:7.9.2020 10:22

Jako úvod pěkné, ale následující by chtělo ještě doplnit :-)
První téma, kterým se věnují tyto články XXXXX,

 
Odpovedať
7.9.2020 10:22
Avatar
Vlasta Řenčová :28.9.2020 17:26

Super článek (narazila jsem na něj dlouho po dokončení Základních konstrukcí, ale stejně byl velice zajímavý. Jen by to chtělo nějakého beta-čtenáře, v textu je pár chyb (opakující se slova ve větách apod.) :-)

 
Odpovedať
28.9.2020 17:26
Avatar
David Mrázek:1.10.2020 13:44

"pole" je vedeno jako int[] a nedá se použít jako int

Odpovedať
1.10.2020 13:44
kde je vůle, tam je cesta
Tento výukový obsah pomáhajú rozvíjať nasledujúce firmy, ktoré možno hľadajú práve teba!
Avatar
Odpovedá na David Mrázek
Ondřej Michálek:1.10.2020 13:53

Urcite, je to sotek. Nedavalo by smysl priradit pole. Ma tam byt temp, chci proste prohodit dve hodnoty. Diky za opravu!

Odpovedať
1.10.2020 13:53
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
Václav Dachs:30. marca 21:16

Super článek, pomohlo to uvědomit a srovnat si v hlavě pár věcí. Díky

Odpovedať
30. marca 21:16
S úsměvem jde všechno lépe :-)
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 5 správy z 5.