V matematike, informatike a ďalších súvisiacich doktrínach je algoritmus definovaný ako súbor ustálených a jednoznačných predpisov, nájdených metodicky a obmedzene, ktoré umožňujú vykonávať výpočty, spracovávať určité informácie, poskytovať riešenia problémov a vykonávať rôzne činnosti. Len čo začnete od počiatočného stavu a zadania, podľa požadovaných postupov sa dosiahne konečný stav a získa sa výsledok. Algoritmy sú predmetom skúmania algoritmov a hoci tomu mnohí neveria, dajú sa použiť aj vo všetkých aspektoch každodenného života.
Čo je to algoritmus
Obsah
Vo výpočtoch sa zvyčajne definuje ako postupnosť postupných pokynov, v ktorých sa vykonávajú niektoré procesy s cieľom odpovedať na určité rozhodnutia alebo potreby. Rovnakým spôsobom sa algoritmy často používajú v logike a matematike a okrem iného sú základom pre vývoj používateľských príručiek, ilustračných brožúr. Jeden z najvýraznejších v matematike je ten, ktorý sa pripisuje geometristovi Euklidesovi, aby sa dosiahol najväčší spoločný deliteľ dvoch celých čísel, ktoré sú kladné, a známa „Gaussova metóda“ na určovanie sústav lineárnych rovníc.
Pokiaľ ide o informatiku, tento výpočet možno označiť ako sled pokynov, ktoré je potrebné dodržať pri určovaní problému pomocou počítača.
Algoritmus sa preto chápe ako disciplína zameraná na analýzu a návrh algoritmov. Ak vezmeme do úvahy prvú, snaží sa preskúmať vlastnosti, ako je jej správnosť a účinnosť s ohľadom na čas a priestor, porozumieť problémom, ktoré je možné vyriešiť algoritmicky. Pokiaľ ide o druhú, snaží sa študovať už zavedené paradigmy a navrhuje nové príklady.
Algoritmus je umiestnený v strede postupu výpočtu a je dôležitý v rôznych jeho oblastiach. Týmto spôsobom by bolo nemožné, aby služby tak úspešné ako Facebook a Google zvládli množstvo informácií, ktoré majú, bez spolupráce algoritmov alebo špecializovaných dátových štruktúr. Avšak v každodennom živote sa používajú aj algoritmy, príkladom toho je zapálenie sporáka, pretože to začína v okamihu, keď osoba ide do kuchyne, pozoruje ju a má koniec, keď ju začne rozsvietiť..
Charakteristika algoritmu
Aj keď je algoritmus známy ako usporiadaná a konečná sada rôznych krokov, ktoré vedú k vyriešeniu problému, hovorí sa, že povaha týchto ťažkostí sa líši v závislosti od kontextu, v ktorom sa nachádzajú, teda existujú problémy. chemické, matematické, filozofické a iné. Dá sa teda povedať, že jeho povaha je rôznorodá a jeho vykonanie počítačom nie je potrebné. Okrem všetkého, čo bolo predtým vysvetlené, majú algoritmy aj charakteristiky, ktoré sú základné pri určovaní toho, o čo sa dnes jedná, a budú spomenuté nižšie.
- Pokyny obsiahnuté v algoritme musia byť konkrétne, aby sa zabránilo ponechaniu priestoru pre akýkoľvek druh zámeny, to znamená, že sa musia zodpovedajúcim spôsobom dodržiavať príslušné pokyny, alebo naopak grafické riešenie toku, v ktorom sa registrujete, riešenie neuľahčí. správne.
- Musí to byť v dokonalej definícii, snažiť sa čo najviac to nasledovať toľkokrát, koľkokrát je to potrebné, aby sa dosiahol rovnaký výsledok a v prípade, že dôjde k opaku, algoritmus nebude spoľahlivý a nebude slúžiť ako pomôcka pri rozhodovaní.
- Sú známi svojou zvláštnosťou, že sú konečné, zvyčajne končia v určitom okamihu a neskôr na konci každého kroku prinesú výsledok. Ak sa algoritmus predlžuje na neurčito a vracia sa do počiatočného bodu, ktorý sa nikdy nedá vyriešiť, je tu paradox alebo známa „slučka“ opakovaní.
- Na záver sa hovorí, že kľúčovým prvkom je čitateľnosť algoritmov, pretože ak je ich argument nezrozumiteľný, príslušné pokyny by nebolo možné dodržať, navyše znamenajú priame, jasné a lakonické znenie textu, ktorý sa nachádza v každom z nich.
Časti algoritmu
Každá algoritmická operácia má tri rôzne časti, ktoré podliehajú základnej štruktúre systému, a to sú:
- Vstup: nazýva sa tiež hlavička alebo východiskový bod, je to počiatočná inštrukcia, ktorá predstavuje genézu algoritmu a ktorá motivuje jeho čítanie.
- Proces: nazýva sa to aj deklarácia, je to presné spracovanie ponúkané algoritmom a je to v podstate kmeň jeho kľúčov na formulovanie pokynov.
- Výstup: v tejto poslednej fáze sú špecifické pokyny určené algoritmom, napríklad jeho príkazy alebo rozlíšenia.
Príklady algoritmov
Bežné príklady matematických výpočtov zahŕňajú 2 + 3 = 5 pre sčítanie a 15-9 = 6 pre odčítanie. Iný spôsob vizualizácie jednoduchých algoritmov je v kuchynských receptoch, pretože popisujú konkrétny a usporiadaný proces, napríklad „najskôr musíte umiestniť pol hrnca vody na zahriatie, potom musíte pridať štipku soli a nakoniec paprika sa rozdelí, aby sa extrahovali semená a nervy. ““ V tomto modeli sú predstavené začiatok, proces a koniec, ktoré v zásade definujú algoritmy.
Typy algoritmov
Spomedzi rôznych typov algoritmov existujúcich na celom svete sa kladie dôraz na tie, ktoré sú klasifikované podľa systému znakov, a iné podľa ich funkcie. Algoritmus je v podstate najznámejším riešením riešenia konkrétneho problému a podľa jeho stratégií a funkcií existuje niekoľko rôznych typov, medzi ktorými vyniká dynamická, reverzná, hrubá sila, oportunistické značenie., nahodne atd. Okrem vyššie spomenutých algoritmov existujú tisíce z nich, ktoré sú vhodné na riešenie problémov v akejkoľvek oblasti.
Podľa vášho znakového systému
Kvalitatívne a kvantitatívne sa nachádzajú v tejto kategórii.
- Kvalitatívne algoritmy sa vyznačujú tým, že majú verbálne prvky, príkladom toho sú pokyny alebo uznávané pokyny „krok za krokom“, ktoré sú poskytované ústne, napríklad recepty na kulinárske umenie alebo postupy na vykonávanie manuálnej práce.
- Kvantitatívne algoritmy sú úplným opakom kvalitatívnych algoritmov, a to vďaka prítomnosti určitých numerických prvkov a použitiu matematiky na vykonávanie výpočtov, napríklad keď sa nájde druhá odmocnina alebo sa vyriešia rovnice.
V rámci tejto klasifikácie existujú aj výpočtové a nevýpočtové algoritmy. Výpočtové sa vykonávajú pomocou počítača a vyznačujú sa tým, že sú také zložité, že si vyžadujú vykonanie stroja, navyše ide o kvantitatívne algoritmy, ktoré je možné optimalizovať. Tie, ktoré nie sú výpočtové, nie sú povinné na vykonanie pomocou stroja alebo počítača; jasným príkladom toho je programovanie televízie.
Podľa jeho funkcie
Nasledujúce sa nachádzajú v tejto klasifikácii.
1. Značkovací algoritmus
Charakteristické je to pomocou automatizácie na dôsledné stanovovanie cien so zameraním na faktory, ako je správanie používateľov, a tiež je známa ako schopnosť automaticky určovať ceny znehodnocujúcich komponentov s cieľom zvýšiť zisky používateľov. predajcovia. Od začiatku 90. rokov zohráva veľmi dôležitú úlohu v bežných postupoch leteckého priemyslu.
Algoritmus označovania sa vyznačuje tým, že je jedným z najbežnejších postupov vo vysoko konkurenčných odvetviach, ktoré sa vzťahujú na cestovné kancelárie alebo on-line zariadenia. Tento druh algoritmu môže byť mimoriadne zložitý alebo relatívne jednoduchý, pretože v mnohých prípadoch sa zistilo, že sú optimalizované alebo samoučiace s kontinuitou určitých testov. Okrem toho všetkého môžu byť algoritmy označovania tiež nepopulárne u klientely, pretože jednotlivci majú tendenciu oceňovať stabilitu aj spravodlivosť.
2. Pravdepodobnostné algoritmy
Sú to tie, v ktorých spôsob získavania výsledkov závisí od pravdepodobností, ktoré sú všeobecne známe ako náhodné algoritmy.
V niektorých aplikáciách je manipulácia s týmto typom operácií bežná, napríklad keď sa v priebehu času simuluje správanie ľubovoľného existujúceho alebo navrhovaného systému, v dôsledku čoho sa získa náhodné riešenie. Za iných okolností je problém, ktorý sa má vyriešiť, obvykle deterministický, ale existuje možnosť jeho transformácie na náhodný problém, ktorý sa dá vyriešiť pomocou pravdepodobnostného algoritmu. Pozitívom náhodného je, že jeho použitie si nevyžaduje vysoko sofistikované matematické štúdie.
Okrem toho v rámci tejto skupiny existujú tri hlavné typy, ktoré sú známe ako číselné, Monte Carlo a Las Vegas.
- Numerické algoritmy môžu poskytnúť približný výsledok problému a všeobecne sa používajú v strojárstve.
- Algoritmy Monte Carlo môžu poskytnúť správne alebo nesprávne riešenie a majú určitú mieru chyby a nakoniec.
- Algoritmy Las Vegas sa vyznačujú tým, že nikdy nenechajú nesprávnu odpoveď, v skutočnosti nájdu správne riešenie alebo vás jednoducho informujú o možnom zlyhaní.
Dynamické programovanie označuje metódu, pri ktorej algoritmus počíta výsledky. Riešenie určitých prvkov, ktoré majú problémy, niekedy závisí od výsledkov ďalších menších problémov. Aby sme ich mohli vyriešiť, musia sa prepočítať rovnaké hodnoty, aby sa vyriešili najmenšie podproblémy, čo však môže spôsobiť plytvanie cyklami. Na vyriešenie tohto problému je možné použiť dynamické programovanie a v takom prípade si pamätáme riešenie každého čiastkového problému, aby bola použitá rovnaká hodnota namiesto opakovania niekoľkokrát.
3. Heuristické algoritmy
Vyznačujú sa hľadaním riešení, a napriek tomu nezaručujú, že bude nájdená najlepšia z odpovedí, preto ich možno považovať za približné algoritmy. Môžu sa použiť, keď sa hľadanie riešenia normálnou cestou považuje za nemožné. Heuristika poskytuje použitie, ktoré bude vysvetlené nižšie. Pri plánovaní sa používajú na plánovanie činností na krátke časové obdobie, v dizajne na vymedzenie elektrických alebo digitálnych systémov a v simulácii na overenie určitých postupov.
4. Algoritmy spätného sledovania
Sú známe ako rekurzívne stratégie, ktoré riešia problémy, ako sú puzzle, bludiská alebo podobné kúsky, v ktorých sa vykonáva dôkladné hľadanie možného riešenia. Jeho názov odkazuje na skutočnosť, že pri vyšetrovaniach zameraných na nájdenie výsledku sa vždy vracia k predchádzajúcemu bodu, aby bolo možné testovať alternatívy. Tieto sa zvyčajne odvolávajú, aby sa zistil ich vplyv na ekonomiku, na trhy, na označovanie cien, na určité operácie a dokonca aj na samotnú spoločnosť.
5. Chamtivý algoritmus
Je známy ako ničiteľ alebo sladký zub a je použiteľný pri optimalizačných problémoch. V každom kroku tohto algoritmu sa urobí logická a optimálna voľba, aby sa dosiahlo najlepšie z globálnych riešení. Je však potrebné vziať do úvahy, že po vynesení rozsudku nemožno v budúcnosti urobiť nič, aby ste ho napravili alebo zmenili. Táto operácia má tento názov, pretože v každom kroku sa vyberie najlepšia frakcia, ktorá je schopná „prehltnúť“ bez obáv z toho, čo sa stane neskôr.
Vlastnosti algoritmu
Rôzni autori sa pokúsili formálne definovať algoritmy pomocou matematických modelov. Tieto vzorky však úzko súvisia so zvláštnym typom informácií, ktoré zahŕňajú čísla, symboly a niektoré grafy, pričom fungujú na obrovskom množstve distribúcie údajov. Spoločná účasť každej z definícií je všeobecne zhrnutá v nasledujúcich troch vlastnostiach:
Vyhlásenie o probléme
Riešenie problémov pomocou počítača môže pozostávať z procesu, v ktorom je problém popísaný a je možné vyvinúť program schopný ich vyriešiť. Tento proces vyžaduje analýzu problému, návrh algoritmu a jeho transformáciu do programu, ako aj jeho implementáciu a validáciu. Prvé dva kroky sú v tomto procese najkomplexnejšie, ale akonáhle problém preskúmate a získate algoritmus, ktorý ho dokáže vyriešiť, bude vašou úlohou predovšetkým previesť ho do požadovaného programovacieho jazyka.
Analýza všeobecného riešenia
Po definovaní problému je čas analyzovať nasledujúce položky:
- Informácie o vstupenkách, ktoré poskytujú nám.
- Požadované výsledky.
- Oblasť práce, vyhlásení alebo iných potrebných prvkov.
Analýza algoritmov je známa ako najdôležitejšia súčasť širšej teórie výpočtovej zložitosti, pretože poskytuje teoretické výpočty zdrojov, ktoré akýkoľvek algoritmus vyžaduje na vyriešenie daného výpočtového problému. Pri vykonávaní teoretického vyšetrenia je bežné vypočítať jeho komplikácie v asymptotickom zmysle, aby sa získala dostatočne veľká vstupná veľkosť. Na tento účel sa používa asymptotická horná väzba spolu s notáciami theta a omega a je potrebné poznamenať, že neasyptotické opatrenie je možné automatizovať.
Presné miery efektívnosti sú skutočne užitočné pre tých, ktorí skutočne používajú algoritmy, pretože majú väčšiu presnosť, čo im umožňuje určiť čas, ktorý bude potrebný na vykonanie. Pre niektorých jednotlivcov, ako sú tvorcovia videohier, môže skrytá konštanta znamenať veľký rozdiel medzi úspechom a neúspechom. Časové hodnotenia môžu závisieť od toho, ako je definovaný určitý krok, a aby mala analýza zmysel, musí byť zaručené, že čas je výrazne obmedzený konštantou.
Vypracovanie algoritmu
Na uskutočnenie vývoja operácie je dôležité, aby sa vykonalo niekoľko postupov, ktoré sú v súlade s riešením samotného problému. Najprv je potrebné vykonať predbežnú analýzu problému, ktorá sa uskutoční pomocou štúdie, ktorá preukáže skutočnú operáciu problému dlho predtým, ako sa vykoná akýkoľvek algoritmus. Preto sa hodnotí definícia požiadaviek, v tomto kroku musíte mať jasnú predstavu o tom, aké sú problémy na riešenie, či už súčet dvoch čísel, usporiadanie zoznamu čísel atď.
Neskôr sa vykoná príslušná identifikácia modulov, pretože od nej závisí správna implementácia algoritmov, aby bolo možné poskytnúť riešenia vyššie uvedených požiadaviek.
Nakoniec je výpočet implementovaný v programovacom jazyku, ktorý je zrozumiteľný počítaču tak, aby bol schopný porozumieť pokynom, ktoré modeluje, a tak ich môže vykonávať, čím sa dosiahne očakávaný výsledok. V tomto poslednom postupe sa už dá hovoriť o programe, ktorý sa skladá zo série pokynov, ktoré sú radené jeden za druhým a dokážu vyriešiť stanovené požiadavky.
Je dôležité spomenúť, že v postupnom čase algoritmy vykonávajú svoju funkciu v diskretizovanom čase a snažia sa definovať postupnosti výpočtových stavov v každom vstupe, ktorý sa považuje za platný. V abstraktnom stave sú tieto operácie nezávislými prvkami a predpokladá sa, že v nich môžu byť štruktúry pravekého poriadku za izomorfizmu invariantné. Pri ohraničenom výskume sú prechody z jedného štátu do druhého úplne stanovené trvalým a konečným vysvetlením, pri ktorom sa medzi jedným stavom a nasledujúcim zohľadňuje iba obmedzený počet pojmov súčasného stavu.
Nemalo by sa zabúdať ani na to, že algoritmy sa zvyčajne vyjadrujú prostredníctvom „pseudokódov“ programovacích jazykov, ktoré sú obvyklým jazykom, a dokonca aj pomocou známych vývojových diagramov. Rovnako je dôležité spomenúť, že algoritmy hrajú pri výpočte zásadnú úlohu vďaka svojej reprezentácii údajov ako sekvencií bitov. Z iného uhla pohľadu je program definovaný ako algoritmus, ktorý počítaču vyjadruje konkrétne kroky, ktoré musí dodržiavať, aby mohol adekvátne plniť určité činnosti. Na druhej strane, učenie sa písania pseudokódu uľahčuje programovanie, a preto bude vysvetlené neskôr.
Programovacie jazyky sú známe ako formálny alebo umelý jazyk, pretože majú presne definované gramatické pravidlá. Má schopnosť poskytnúť programátorovi možnosť textualizovať sériu pokynov alebo postupností predpisov vo forme algoritmov za účelom aby ste si udržali kontrolu nad fyzickým a logickým správaním počítača, týmto spôsobom je možné dosiahnuť rôzne typy informácií. Táto sada príkazov napísaná prostredníctvom programovacieho jazyka sa nazýva program.
Programovacie jazyky sú zvyčajne tvorené súborom symbolov a gramatických a sémantických pravidiel, ktoré definujú súčasné štruktúry jazyka a ich význam. Z iného pohľadu zahŕňajú počítačové jazyky aj programovacie jazyky, jasným príkladom toho je HTML, ktoré spĺňa určité pokyny na vykonávanie obsahu rôznych dokumentov. Programovací jazyk umožňuje presnú špecifikáciu tých údajov, ktoré musia byť prevádzkované konkrétnym softvérom za širokej škály okolností.
Na druhej strane, pseudokód je algoritmický popisný jazyk, ktorý využíva elementárne konvencie skutočného programovacieho jazyka, ale ktorý je určený na čítanie človekom namiesto čítania na stroji, pričom si zachováva nezávislosť od iného typu programovací jazyk. Pseudokód ignoruje podrobnosti, ktoré sa nepovažujú za nevyhnutné pre ľudské pochopenie algoritmu, ako sú systémové kódy, deklarácie premenných a dokonca aj niektoré podprogramy. Týmto spôsobom sa programovací jazyk snaží doplniť presnými popismi v prirodzenom jazyku alebo kompaktnými matematickými zápismi.
