Zvažujú sa teda rôzne varianty počítačov od najjednoduchších Turingových strojov až po homogénne výpočtové prostredie. Všetky sa dajú použiť na riešenie problémov, pre ktoré existuje algoritmus. Na základe týchto modelov sa budujú špecializovanejšie výpočtové modely, a to: nerozvetvené aritmetické programy, bitové výpočty, výpočty s binárnymi vektormi a rozhodovacie stromy.
Algoritmy majú nasledujúce vlastnosti:
a) zložitosť;
b) prácnosť;
c) spoľahlivosť a pod.
Existuje mnoho kritérií na hodnotenie zložitosti algoritmov. Najčastejšie nás bude zaujímať poradie rastu potrebné na vyriešenie problému času a kapacity pamäte s nárastom počtu vstupných údajov. Priraďte ku každej konkrétnej úlohe určité číslo, ktoré sa nazýva veľkosť. Napríklad veľkosť úlohy násobenia matíc môže byť najväčšia veľkosť matíc - faktorov; veľkosťou problému na grafe môže byť počet hrán daného grafu a pod.
Nazýva sa čas, ktorý algoritmu zaberie ako funkcia veľkosti úlohy časová zložitosť tento algoritmus. Správanie sa tejto zložitosti v limite so zväčšovaním veľkosti problému sa nazýva asymptotická časová zložitosť. The kapacitná zložitosť a asymptotická kapacitná zložitosť.
Dôležitým motívom uvažovania o formálnych výpočtových modeloch je túžba odhaliť výpočtovú zložitosť rôznych problémov s cieľom získať spodné hranice výpočtového času. Ukázať, že neexistuje žiadny algoritmus, ktorý vykonáva danú úlohu za menej ako určitý čas, si vyžaduje presnú a niekedy vysoko špecializovanú definíciu toho, čo je algoritmus. Turingove stroje sú jedným z príkladov takejto definície.
4.1.1. Rámové a rámové stroje*
Zvážte dva stroje:
1. Stroje s náhodným prístupom do pamäte (ekvivalentný adresný stroj - RAM) modelujú počítač s jednou sčítačkou, v ktorom sa programové inštrukcie nemôžu samy meniť.
2. Uložený programový model je stroj s náhodným prístupom do pamäte a možnosťou úpravy inštrukcií (PAM*).
Obr.2.9 Štruktúra strojov PAM (PAM *)
Pre RAM sa program nezapisuje do pamäte, takže program sa sám nemení. Program je postupnosť označených príkazov. Existujú aritmetické inštrukcie, I/O inštrukcie, inštrukcie na nepriame adresovanie a inštrukcie na vetvenie. Všetky výpočty sa vykonávajú v registri r 0 (sčítačka), ktorý ako každý iný pamäťový register môže uchovávať ľubovoľné celé číslo. Každý príkaz sa skladá z dvoch častí – operačného kódu a adresy. Inštrukcie PAM sú podmnožinou inštrukcií v jazyku symbolických inštrukcií; túto podmnožinu možno ľubovoľne rozširovať, ale poradie zložitosti problémov sa nezmení.
Operand môže byť jedného z nasledujúcich typov:
1. =i znamená samotné celé číslo i a nazýva sa doslovný;
2. i- obsah registra i (i musí byť nezáporné)
3. *i znamená nepriame adresovanie, to znamená, že hodnota operandu je obsah registra j,kde j- celé číslo, ktoré je v registri ja;ak j<0, auto zastaví.
Dokáže určiť hodnotu programu R pomocou dvoch objektov: mapy c z množiny nezáporných celých čísel do množiny celých čísel a „počítadla príkazov“, ktoré určuje nasledujúci vykonaný príkaz. Funkcia c je mapovanie pamäte, menovite c(i)- celé číslo obsiahnuté v čísle registra ja (obsahu Registrovať ja).
najprv c(i)=0 pre všetkých i 0 , počítadlo programu je nastavené na prvú inštrukciu v P a výstupná páska je prázdna. Po vykonaní k- tím z R počítadlo sa automaticky prepne na (k+1)-tý (teda na ďalší) príkaz, ak k-tý príkaz nebol JUMP, HALT, JGTZ a podobne.
Program RAM* sa nachádza v pamäťových registroch. Každá inštrukcia PAM* zaberá dva po sebe idúce pamäťové registre: prvý register obsahuje operačný kód, druhý - adresu. Sada inštrukcií pre PAM* je rovnaká ako zodpovedajúca sada pre PAM okrem nepriameho adresovania, ktoré je vylúčené: PAM* môže simulovať nepriame adresovanie zmenou inštrukcií počas vykonávania programu.
Algoritmus- súbor pokynov popisujúcich poradie úkonov výkonného umelca na dosiahnutie nejakého výsledku.
Časová efektívnosť je indikátorom rýchlosti algoritmu
odhadnutý počtom základných operácií, ktoré musí algoritmus vykonať pri spracovaní vstupných údajov veľkosti n
Dôležité je poradie rastu času vykonávania algoritmu v závislosti od n
Priestorová efektívnosť ukazuje, koľko dodatočnej pamäte RAM je potrebné na to, aby algoritmus fungoval. Účinnosť sa hodnotí v najhoršom, najlepšom a priemernom prípade.
Typy analýz: matematické a empirické
Meranie času vykonávania algoritmu
1. Priama (empirická analýza)
2. Určenie počtu základných operácií, ktoré musí algoritmus vykonať pri spracovaní vstupných údajov veľkosti n (matematická analýza)
Rastový poriadok
Pri malých veľkostiach vstupov nie je možné zaznamenať rozdiel v čase vykonávania medzi efektívnym a neefektívnym algoritmom. Pre veľké hodnoty n sa vypočíta poradie rastu funkcie.
Účinnosť algoritmu v rôznych prípadoch
Existuje veľké množstvo algoritmov, ktorých čas vykonania závisí nielen od veľkosti vstupných dát, ale aj od špecifických vlastností vstupných dát (príkladom je vyhľadávanie).
Účinnosť sa meria pre:
Príklad: priemerný počet porovnaní vo vyhľadávaní:
Takže:
Pri vývoji algoritmov je veľmi dôležité vedieť odhadnúť zdroje potrebné na vykonávanie výpočtov, výsledok hodnotenia je funkciou zložitosti (práce). Odhadovaným zdrojom je najčastejšie čas CPU (výpočtová zložitosť) a pamäť (pamäťová zložitosť algoritmu). Odhad vám umožňuje predpovedať čas vykonania a porovnávať výkon algoritmov.
Účinnosť algoritmu je vlastnosť algoritmu, ktorá súvisí s výpočtovými zdrojmi používanými algoritmom. Algoritmus musí byť analyzovaný, aby sa určili zdroje potrebné pre algoritmus. Účinnosť algoritmu možno považovať za analogickú s výrobným výkonom opakujúcich sa alebo kontinuálnych procesov.
Aby sme dosiahli maximálnu efektivitu, chceme znížiť spotrebu zdrojov. Rôzne zdroje (napríklad čas a pamäť) však nemožno priamo porovnávať, takže ktorý z týchto dvoch algoritmov sa považuje za efektívnejší, často závisí od toho, ktorý faktor je dôležitejší, ako napríklad požiadavka na vysokú rýchlosť, minimálne využitie pamäte alebo iné opatrenie. efektívnosti.
Všimnite si, že tento článok NIE o optimalizácii algoritmu, o ktorej sa hovorí v článkoch optimalizačné programy, optimalizačný kompilátor, optimalizácia cyklu, optimalizátor objektového kódu, atď. Samotný pojem „optimalizácia“ je zavádzajúci, pretože všetko, čo sa dá urobiť, spadá pod pojem „zlepšenie“.Encyklopedický YouTube
1 / 5
✪CS50. Asymptotická notácia
✪ 1. Algoritmy a dátové štruktúry. Úvod | Technostream
✪ Algoritmická účinnosť
✪ Algoritmus Knuth-Morris-Pratt
✪ 2. Algoritmy a dátové štruktúry. Zoznamy, zásobník, front, dec | Technostream
titulky
Pravdepodobne ste už počuli ľudí hovoriť o rýchlych alebo efektívnych algoritmoch na vykonanie danej úlohy, ale čo presne máte na mysli pod pojmom rýchle a efektívne v prípade algoritmov? V skutočnosti nehovoria o meraní reálneho času v sekundách alebo minútach. Pretože počítačový hardvér a softvér je veľmi rôznorodý. Môj program môže bežať pomalšie ako váš, pretože ho mám spustený na staršom počítači, alebo preto, že súčasne hrám sieťovú hru, ktorá mi zaberá celú pamäť. Alebo som spustil svoj program cez iný softvér, ktorý svojim spôsobom interaguje s hardvérom na nízkej úrovni. Je to ako porovnávať teplé a mäkké. To, že môjmu pomalšiemu počítaču trvá nájdenie odpovede dlhšie, neznamená, že váš algoritmus je efektívnejší. Keďže nemôžeme priamo porovnávať čas vykonávania programov v sekundách alebo minútach, ako môžeme porovnávať dva rôzne algoritmy bez závislosti od hardvéru alebo softvéru? Aby sa zjednotil spôsob merania efektívnosti algoritmu, matematici a počítačoví vedci našli riešenie v meraní asymptotickej zložitosti programu a takzvaného „Big O“ zápisu na jeho opis. Formálna definícia je: Funkcia f(x) je rádu g(x), ak existuje taká hodnota "x", "x₀" a nejaká konštanta "C", pre ktorú je f(x) menšie alebo rovné tejto hodnote. konštanta vynásobená g (x) pre každé "x" väčšie ako "x₀". Nenechajte sa však zastrašiť formálnou definíciou. Čo to v skutočnosti znamená menej teoreticky? Zjednodušene povedané, je to spôsob analýzy toho, ako rýchlo rastie čas asymptotického vykonávania programu. To znamená, že keď sa veľkosť vstupu zväčšuje smerom k nekonečnu. Povedzme, že triedime pole 1000 prvkov a pole 10. Ako sa zvýši čas vykonávania programu? Predstavte si napríklad, že najjednoduchším spôsobom spočítate počet znakov v reťazci, prejdete celý reťazec písmeno po písmene a zakaždým pridáte jeden do počítadla. Hovorí sa, že algoritmus beží v lineárnom čase v počte znakov (n) v reťazci. Alebo krátko, trvá to O(n). prečo je to tak? Pri tomto prístupe je čas potrebný na prejdenie celého reťazca úmerný počtu znakov v ňom. Počítanie počtu znakov v 20-znakovom reťazci bude trvať dvakrát dlhšie ako počítanie v 10-znakovom reťazci, pretože sa musíte pozrieť na všetky znaky a prezeranie každého znaku trvá rovnako dlho. So zvyšujúcim sa počtom znakov sa čas vykonávania predĺži spolu s dĺžkou zdrojových údajov. Povedzme, že ste sa rozhodli, že lineárny čas O(n) nie je dostatočne rýchly. Možno skladujete obrovské reťazce a nemôžete si dovoliť viac času na to, aby ste si prešli všetky postavy a počítal ich jeden po druhom. A vy sa rozhodnete vyskúšať niečo iné. Čo ak počet znakov pre reťazec už bude uložený v premennej, povedzme „len“. Uloží sa v programe skôr, ešte predtým, ako uložíte úplne prvý znak vášho reťazca. Potom všetko, čo musíte urobiť, aby ste našli dĺžku reťazca, je prečítať hodnotu tejto premennej. Na samotný reťazec by ste sa vôbec nemuseli pozerať a načítanie hodnoty „len“ má byť operácia, ktorá trvá asymptoticky konštantný čas, čiže O(1). prečo je to tak? Pripomeňme si, čo znamená asymptotická zložitosť. Ako sa mení čas vykonania s rastúcou veľkosťou vstupu? Povedzme, že získate počet znakov v dlhšom reťazci. Vo všeobecnosti nezáleží na tom, ako dlho to je. Aspoň milión znakov. S týmto prístupom všetko, čo musíte urobiť, aby ste našli dĺžku reťazca, je prečítať hodnotu premennej "len", ktorú už máte. Veľkosť vstupu, v našom prípade reťazca, ktorého dĺžku chceme zistiť, vôbec neovplyvní, ako rýchlo program beží. Táto časť vášho programu pobeží rovnako rýchlo na jednoznakovom riadku ako na tisícznakovom riadku. A to je dôvod, prečo sa program bude považovať za spustený v konštantnom čase vzhľadom na veľkosť vstupných údajov. Samozrejme, existujú aj nevýhody. V počítači strácate dodatočnú pamäť na uloženie premennej, ako aj čas navyše na vyplnenie jej hodnoty. Ale aj tak to dáva zmysel. Čas na získanie počtu znakov v reťazci vôbec nezávisí od dĺžky reťazca. Beží teda v O(1) alebo konštantnom čase. To samozrejme nemusí nutne znamenať, že váš kód zaberie iba jeden krok. Nezáleží však na tom, koľko krokov je, pokiaľ sa ich počet nemení pri zmene veľkosti vstupu. Bude asymptoticky konštantný, čo označíme ako O(1). Ako ste možno uhádli, existuje veľa rôznych „veľkých O“ na meranie času vykonávania algoritmov. Algoritmy O(n²) sú asymptoticky pomalšie ako algoritmy O(n). To znamená, že ako počet prvkov, n, rastie, O(n²) algoritmy budú nakoniec trvať dlhšie ako O(n) algoritmy. To neznamená, že O(n) algoritmy sú vždy rýchlejšie ako O(n²) algoritmy, dokonca aj v rovnakom prostredí na rovnakom hardvéri. Môže sa stať, že pre malé vstupy bude algoritmus O(n²) skutočne bežať rýchlejšie, ale postupom času, ako sa veľkosť vstupných údajov zväčšuje smerom k nekonečnu, čas vykonania algoritmu O(n²) nakoniec zakryje čas vykonania. algoritmu O(n). Rovnako ako každá kvadratická matematická funkcia nakoniec predbehne akúkoľvek lineárnu funkciu. A je úplne jedno, aký veľký handicap má hodnota lineárnej funkcie hneď na začiatku. Ak pracujete s veľkým množstvom údajov, potom algoritmy, ktoré bežia v O(n²), nakoniec spomalia váš program, ale pri malých veľkostiach vstupných údajov si to s najväčšou pravdepodobnosťou ani nevšimnete. Ďalším druhom asymptotickej zložitosti je logaritmický čas, O(log n). Príkladom algoritmu, ktorý beží takto rýchlo, je klasický binárny vyhľadávací algoritmus na nájdenie prvku v predradenej množine. Ak neviete, ako prebieha binárne vyhľadávanie, o chvíľu všetko rýchlo vysvetlím. Povedzme, že hľadáte číslo 3 v poli celých čísel. Vezmeme centrálny prvok poľa a opýtame sa: "Je prvok, ktorý potrebujem, väčší, menší alebo rovný tomuto?" Ak je to rovnaké, skvelé. Našli sme ten správny prvok, to je všetko. Ak viac, potom je jasné, že náš prvok by mal byť v poli niekde vpravo a potom sa môžete pozerať iba na pravú stranu. Ak menej, tak je jasné, že prvok je niekde vľavo. Potom tento proces opakujeme so stále kratšími poľami, kým nenájdeme požadovaný prvok. Tento výkonný algoritmus znižuje veľkosť poľa na polovicu po každej operácii. To znamená, že na nájdenie prvku v zoradenom poli dĺžky 8 nie je potrebných viac ako (log₂8) alebo tri takéto operácie na kontrolu centrálneho prvku a výber požadovanej polovice. Pole dĺžky 16 by zároveň vyžadovalo (log₂16) alebo štyri operácie. A to je len jedna dodatočná operácia pri zdvojnásobení dĺžky poľa. Zdvojnásobenie veľkosti zvyšuje čas vykonania iba o jeden kus kódu. Ešte raz skontrolujeme centrálny prvok a pole rozdelíme. Toto sa nazýva logaritmický čas, O(log n). Ale počkajte, poviete si, nezávisí to od toho, kde v poli sa nachádza hľadaný prvok? Čo ak prvý prvok, ktorý kontrolujeme, je ten? Potom stačí jedna operácia, bez ohľadu na to, aké veľké je pole. Preto v informatike stále existujú ďalšie koncepty asymptotickej zložitosti, ktoré odrážajú výkon v najlepšom a najhoršom prípade. Alebo, presnejšie, horná a dolná hranica času vykonávania algoritmu. V najlepšom prípade pre binárne vyhľadávanie je náš prvok priamo tu v strede. Nájdeme ho v konštantnom čase, bez ohľadu na veľkosť zvyšku poľa. Na tento účel použite symbol Ω. To znamená, že sa hovorí, že algoritmus beží v Ω(1). V najlepšom prípade nájde prvok veľmi rýchlo. Nezáleží na tom, aké veľké je pole. Ale v najhoršom prípade musíte vykonať (log n) kontroly a rozdelenia poľa, aby ste našli požadovaný prvok. Horná hranica pre najhorší prípad je označená ako „veľké O“, ako už viete. Ukazuje sa teda O(log n), ale Ω(1). Pre porovnanie lineárne vyhľadávanie, pri ktorom sa pozrieme cez každý prvok v poli, aby sme našli ten správny, v najlepšom prípade Ω (1). To znamená, že opäť sa ukáže, že prvý prvok je ten, ktorý hľadáme. Preto nezáleží na tom, aké veľké je naše pole. V horšom prípade je prvok, ktorý hľadáte, až na samom konci. A musíte prejsť cez všetkých n prvkov poľa, aby ste ho našli. Takto, ak hľadáme 3. To znamená, že jeho čas vykonania je O(n), pretože je úmerný počtu prvkov poľa. Používa sa aj symbol Θ. Používa sa na opis algoritmov, ktoré majú rovnaké najlepšie a najhoršie časy. Rovnako ako v prípade algoritmu vyhľadávania dĺžky reťazca, o ktorom sme hovorili vyššie. Ten, kde dĺžku vopred uložíme do premennej a neskôr ju len načítame v konštantnom čase. Bez ohľadu na to, aké číslo do tejto premennej uložíme, pozrieme sa naň. V najlepšom prípade sa pozrieme na hodnotu a získame dĺžku reťazca. To je v najlepšom prípade Ω(1) alebo konštantný čas. V najhoršom prípade sa pozrieme na hodnotu a dostaneme dĺžku reťazca. To je O(1) alebo konštantný čas pre najhorší prípad. Najlepší a najhorší prípad sú teda rovnaké. A môžeme povedať, že algoritmus sa vykoná v čase Θ(1). Aby som to zhrnul, máme dobré spôsoby, ako uvažovať o efektívnosti kódu bez toho, aby sme zistili, koľko reálneho času bude trvať spustenie. Tento čas závisí od veľkého množstva vonkajších faktorov, ako je hardvér a softvér, ako aj od špecifík samotného kódu. Môžeme tiež jasne zdôvodniť, čo sa stane, keď sa veľkosť vstupných údajov zvýši. Ak máme algoritmus O(n²), alebo ešte horšie O(2ⁿ), algoritmus, t. j. jeden z najrýchlejšie rastúcich typov, potom je naozaj ťažké prehliadnuť spomalenie pri práci s rastúcim množstvom údajov. Toto je asymptotická zložitosť. Ďakujem za tvoju pozornosť.
Pozadie
Dôležitosť efektívnosti s dôrazom na čas vykonania zdôraznila Ada Lovelace v roku 1843 s ohľadom na mechanický analytický motor Charlesa Babbagea:
„Takmer pri všetkých výpočtoch je na úspešné dokončenie procesu možná široká škála konfigurácií a výber na vykonanie výpočtov by mali ovplyvniť rôzne konvencie. Základom je zvoliť konfiguráciu, ktorá povedie k minimalizácii času potrebného na dokončenie výpočtu.
Prvé elektronické počítače boli veľmi obmedzené v rýchlosti aj pamäti. V niektorých prípadoch sa zistilo, že existuje kompromis medzi časom a pamäťou, v ktorom musí úloha buď použiť veľké množstvo pamäte na dosiahnutie vysokej rýchlosti, alebo použiť pomalší algoritmus, ktorý využíva malé množstvo pracovnej pamäte. V tomto prípade bol použitý najrýchlejší algoritmus, pre ktorý bol dostatok dostupnej pamäte.
Moderné počítače sú oveľa rýchlejšie ako prvé počítače a majú oveľa viac pamäte (gigabajty namiesto kilobajtov). Donald Knuth však zdôrazňuje, že dôležitým faktorom zostáva efektívnosť:
"V zavedených inžinierskych disciplínach je 12% zlepšenie ľahko dosiahnuteľné, nikdy sa nepovažovalo za neobvyklé a verím, že to isté by malo platiť aj v programovaní."
Preskúmanie
Algoritmus sa považuje za efektívny, ak zdroj, ktorý spotrebúva (alebo náklady na zdroj), je na alebo pod prijateľnou úrovňou. Zhruba povedané, „prijateľné“ tu znamená „algoritmus bude bežať primeraný čas na dostupnom počítači“. Keďže od 50. rokov minulého storočia došlo k výraznému nárastu výpočtového výkonu a dostupnej pamäte počítačov, existujúca „prijateľná úroveň“ nebola akceptovateľná ani pred 10 rokmi.
Výrobcovia počítačov pravidelne vydávajú nové modely, často výkonnejšie. Náklady na softvér môžu byť dosť vysoké, takže v niektorých prípadoch je jednoduchšie a lacnejšie dosiahnuť lepší výkon kúpou rýchlejšieho počítača, ktorý je kompatibilný s vaším existujúcim počítačom.
Existuje mnoho spôsobov, ako merať zdroje používané algoritmom. Dve najpoužívanejšie merania sú rýchlosť a využitá pamäť. Ďalšie merania môžu zahŕňať prenosovú rýchlosť, dočasné využitie disku, dlhodobé využitie disku, spotrebu energie, celkové náklady na vlastníctvo, čas odozvy na externé signály atď. Mnohé z týchto meraní závisia od veľkosti vstupu algoritmu (t. j. množstva údajov, ktoré je potrebné spracovať). Merania môžu závisieť aj od spôsobu, akým sú údaje prezentované (napríklad niektoré triediace algoritmy nefungujú dobre na už zoradených údajoch alebo keď sú údaje zoradené v opačnom poradí).
V praxi existujú ďalšie faktory, ktoré ovplyvňujú účinnosť algoritmu, ako je požadovaná presnosť a/alebo robustnosť. Ako je vysvetlené nižšie, spôsob implementácie algoritmu môže mať tiež významný vplyv na skutočný výkon, hoci mnohé aspekty implementácie predstavujú problémy s optimalizáciou.
Teoretická analýza
V teoretickej analýze algoritmov je bežnou praxou odhadnúť zložitosť algoritmu v jeho asymptotickom správaní, to znamená odrážať zložitosť algoritmu ako funkciu veľkosti vstupu. n používa sa označenie „O“ big. Tento odhad je vo všeobecnosti dosť presný pre veľké n, ale pri malých hodnotách môže viesť k nesprávnym záverom n(Takto bublinové triedenie, ktoré sa považuje za pomalé, môže byť rýchlejšie ako „rýchle triedenie“, ak je potrebné triediť len niekoľko prvkov.)
Niekoľko príkladov veľkého zápisu „O“:
| Označenie | názov | Príklady |
|---|---|---|
| O(1) (\displaystyle O(1)\,) | trvalé | Určenie, či je číslo párne alebo nepárne. Použitie vyhľadávacej tabuľky konštantnej veľkosti. Použitie vhodnej hašovacej funkcie na výber prvku. |
| O (log n) (\displaystyle O(\log n)\,) | logaritmický | Nájdenie prvku v triedenom poli pomocou binárneho vyhľadávania alebo vyváženého stromu, rovnako ako operácie na binomickej halde. |
| O(n)(\displaystyle O(n)\,) | lineárne | Nájdenie prvku v netriedenom zozname alebo nevyváženom strome (najhorší prípad). Pridanie dvoch n-bitové čísla pomocou prenosu typu end-to-end. |
| O (n log n) (\displaystyle O(n\log n)\,) | kvázilineárne, logaritmicky lineárne | Výpočet rýchlej Fourierovej transformácie, triedenie haldy, rýchle triedenie (najlepší a priemerný prípad), zlučovacie triedenie |
| O(n 2) (\displaystyle O(n^(2))\,) | námestie | Násobenie dvoma n-ciferné čísla s jednoduchým algoritmom, bublinové triedenie (najhorší prípad), shellové triedenie, rýchle triedenie (najhoršie triedenie), výberové triedenie, vkladanie |
| O (c n), c > 1 (\displaystyle O(c^(n)),\;c>1) | exponenciálny | Nájdenie (presného) riešenia problému obchodného cestujúceho pomocou dynamického programovania. Určenie, či sú dva booleovské príkazy ekvivalentné, pomocou vyčerpávajúcej hrubej sily |
Overovacie testy: Meranie výkonu
Pre nové verzie softvéru alebo na porovnanie s konkurenčnými systémami sa niekedy používajú benchmarky na porovnanie relatívneho výkonu algoritmov. Ak sa napríklad uvoľní nový triediaci algoritmus, možno ho porovnať s predchodcami, aby sa zabezpečilo, že algoritmus bude pri známych údajoch prinajmenšom taký efektívny ako ostatné. Benchmarky môžu používatelia použiť na porovnanie produktov od rôznych výrobcov, aby zhodnotili, ktorý produkt bude najlepšie vyhovovať ich požiadavkám z hľadiska funkčnosti a výkonu.
Niektoré benchmarky poskytujú spôsob, ako porovnať rôzne jazyky kompilátora a tlmočníka, ako napríklad Roy Longbottom's PC Benchmark Collection a Hra na porovnávanie počítačového jazyka porovnáva výkon implementácií typických úloh v niektorých programovacích jazykoch.
Problémy s implementáciou
Problémy s implementáciou môžu tiež ovplyvniť skutočný výkon. To zahŕňa výber programovacieho jazyka a spôsobu skutočného kódovania algoritmu, výber prekladača pre zvolený jazyk alebo použité možnosti kompilátora a dokonca aj použitý operačný systém. V niektorých prípadoch môže byť jazyk implementovaný ako tlmočník výrazne pomalší ako jazyk implementovaný ako kompilátor.
Existujú aj ďalšie faktory, ktoré môžu ovplyvniť využitie času alebo pamäte, ktoré sú mimo kontroly programátora. To zahŕňa zarovnanie údajov, granularita údajov, garbage collection, paralelizmus na úrovni inštrukcií a volania podprogramov.
Niektoré procesory majú schopnosť vykonávať vektorové operácie, čo umožňuje jednej operácii spracovať viacero operandov. Môže alebo nemusí byť jednoduché používať takéto funkcie na úrovni programovania alebo kompilácie. Algoritmy navrhnuté pre sériové výpočty možno bude potrebné úplne prepracovať, aby používali paralelné výpočty.
Ďalší problém môže nastať s kompatibilitou procesorov, v ktorých môžu byť inštrukcie implementované odlišne, takže inštrukcie na niektorých modeloch môžu byť na iných modeloch relatívne pomalšie. To môže byť problém pre optimalizujúci kompilátor.
Meranie spotreby zdrojov
Merania sú zvyčajne vyjadrené ako funkcia vstupnej veľkosti. n.
Dve najdôležitejšie merania sú:
- čas: ako dlho trvá algoritmu CPU.
- Pamäť: koľko pracovnej pamäte (zvyčajne RAM) potrebuje algoritmus. Sú tu dva aspekty: množstvo pamäte pre kód a množstvo pamäte pre údaje, s ktorými kód pracuje.
Pre batériovo napájané počítače (napr. laptopy) alebo pre veľmi dlhé/veľké výpočty (napr. superpočítače) je zaujímavý iný druh merania:
- Priama spotreba energie: Energia potrebná na chod počítača.
- Nepriama spotreba energie: energia potrebná na chladenie, osvetlenie atď.
V niektorých prípadoch sú potrebné iné, menej bežné merania:
- Veľkosť prenosu: Šírka pásma môže byť limitujúcim faktorom. Na zníženie množstva prenášaných dát je možné použiť kompresiu. Zobrazenie obrázka alebo obrázka (napríklad loga Google) môže viesť k prenosu desiatok tisíc bajtov (v tomto prípade 48 kB). Porovnajte to s odoslaním šiestich bajtov v slove „Google“.
- Externá pamäť: Požadovaná pamäť na disku alebo inom externom úložnom zariadení. Táto pamäť môže byť použitá na dočasné uloženie alebo na budúce použitie.
- Doba odozvy: Toto nastavenie je dôležité najmä pre aplikácie v reálnom čase, kde musí počítač rýchlo reagovať na vonkajšie udalosti.
- Celková cena vlastníctva: Parameter je dôležitý, keď je určený na spustenie jedného algoritmu.
čas
teória
Tento typ testov výrazne závisí aj od výberu programovacieho jazyka, kompilátora a jeho možností, takže porovnávané algoritmy musia byť implementované za rovnakých podmienok.
Pamäť
Táto časť sa zaoberá používaním hlavnej pamäte (často RAM), ktorú vyžaduje algoritmus. Pokiaľ ide o časovú analýzu vyššie, na analýzu sa zvyčajne používa analýza algoritmu priestorová zložitosť algoritmu na odhadnutie požadovanej pamäte za chodu ako funkcie veľkosti vstupu. Výsledok sa zvyčajne vyjadruje ako „O“ veľké.
Existujú štyri aspekty využitia pamäte:
- Množstvo pamäte potrebnej na uloženie kódu algoritmu.
- Množstvo pamäte potrebnej pre vstupné dáta.
- Množstvo pamäte potrebnej pre akýkoľvek výstup (niektoré algoritmy, ako napríklad triedenie, často preusporiadajú vstup a nevyžadujú dodatočnú pamäť pre výstup).
- Množstvo pamäte, ktorú potrebuje výpočtový proces počas výpočtu (to zahŕňa pomenované premenné a akýkoľvek zásobníkový priestor potrebný na volanie podprogramov, čo môže byť významné pri použití rekurzie).
Prvé elektronické počítače a domáce počítače mali relatívne málo pracovnej pamäte. Takže v roku 1949 mal EDSAC maximálnu pracovnú pamäť 1024 17-bitových slov a v roku 1980 bol vyrobený Sinclair ZX80 s 1024 bajtmi pracovnej pamäte.
Moderné počítače môžu mať relatívne veľké množstvo pamäte (možno gigabajty), takže kompresia pamäte používanej algoritmom do daného množstva pamäte trvá menej ako predtým. Podstatná je však existencia troch rôznych kategórií pamäte:
- Cache (často statická RAM) – beží rýchlosťou porovnateľnou s CPU
- Hlavná fyzická pamäť (často dynamická RAM) - o niečo pomalšia ako CPU
- Virtuálna pamäť (často na disku) – dáva ilúziu obrovskej pamäte, no je tisíckrát pomalšia ako RAM.
Algoritmus, ktorého požadovaná pamäť sa zmestí do vyrovnávacej pamäte počítača, beží oveľa rýchlejšie ako algoritmus, ktorý sa zmestí do hlavnej pamäte, ktorá bude zase oveľa rýchlejšia ako algoritmus, ktorý využíva virtuálny priestor. Komplikáciou je skutočnosť, že niektoré systémy majú až tri úrovne vyrovnávacej pamäte. Rôzne systémy majú rôzne množstvá týchto typov pamäte, takže pamäťový efekt na algoritmus sa môže medzi jednotlivými systémami značne líšiť.
Ak sa v počiatkoch elektronických výpočtových systémov algoritmus a jeho údaje nezmestili do hlavnej pamäte, nebolo možné ho použiť. V súčasnosti používanie virtuálnej pamäte poskytuje veľkú pamäť, ale za cenu výkonu. Ak sa algoritmus a jeho údaje zmestia do vyrovnávacej pamäte, je možné dosiahnuť veľmi vysokú rýchlosť, takže minimalizácia potrebnej pamäte pomáha minimalizovať čas. Algoritmus, ktorý sa úplne nezmestí do vyrovnávacej pamäte, ale poskytuje lokalita odkazu môže bežať pomerne rýchlo.
AT uväznenie je uvedená konzistentná, logicky súvislá prezentácia získaných výsledkov a ich vzťah k celkovému cieľu (hypotéze) a cieľom výskumu, sú vyvodené zovšeobecnené závery, sú formulované názory a návrhy autora na zlepšenie skúmaného problému. Objem textu záveru v záverečnej kvalifikačnej práci nie je prísne regulovaný – zvyčajne je to 1,5 – 3 strany.
AT zoznam použitých zdrojov tie dokumenty, materiály, periodiká, literatúra, ktoré sa v štúdii používajú, sú bezpodmienečne uvedené. Nerobte zoznam príliš veľký; je tiež neprijateľné zahrnúť texty, ktoré nesúvisia so skúmaným problémom.
Zostavenie zoznamu použitých prameňov a literatúry je jednou z najdôležitejších etáp pri práci na štúdii, pretože odráža samostatný, tvorivý prístup jej autora k výberu vedeckej literatúry a štúdiu zvoleného problému a umožňuje posúdiť stupeň závažnosti a opodstatnenosti štúdie.
V prípade potreby môže bibliografický zoznam obsahovať napríklad časti:
1. Dokumenty štátnych orgánov a verejnoprávnych organizácií;
2. Archívne dokumenty;
3. referenčné a štatistické publikácie;
4. vzdelávacie a vzdelávacie publikácie;
5. vedecké monografie a články;
7. Periodiká;
Zoznam periodík a vzdelávacích publikácií, literatúry, dizertačných prác a abstraktov je tvorený abecedne podľa mien autorov a názvov kníh/článkov.
Počet zdrojov v bibliografickom zozname záverečnej kvalifikačnej práce nemôže byť menej ako 25-30 položiek.
Vydáva sa v súlade s GOST 2003 alebo GOST R 7.0.5-2008 "Bibliografický odkaz".
Príklady bibliografických popisov citovaných zdrojov
1. Turuta E.F. Aktívne SMD súčiastky: označenie, charakteristika, výmena. - Petrohrad: Veda a technika, 2006. - 544 s.
2. Ulrich V.A. Mikrokontroléry PIC16X7XX. - Petrohrad: Veda a technika, 2002. - 320 s.
Kniha má editora
1. Remizevič T.V. Mikrokontroléry pre vstavané aplikácie: od všeobecných prechodov na rodiny HC05 a HC08 od Motoroly. / vyd. Kiryukhina I.S. - M.: DODEKA, 2000. - 272 s.
Určitý typ práce (učebnica, referenčná kniha, encyklopédia atď.)
1. Finkelstein M.I. Základy radaru: Proc. pre univerzity. - M.: Rozhlas a komunikácia, 1983. - 536 s.
2. Guk M. Hardvér IBM PC: Encyklopédia. - Petrohrad: Vydavateľstvo "Peter", 1999. - 816 s.
1. Iglovský I.G. Nízkoprúdové elektrické relé: Príručka / I.G. Iglovský, G.V. Vladimírov. - M.: KUBK-a, 1996. - 560 s.
2. Romanycheva E.T. Inžinierstvo a počítačová grafika / E.T. Romanycheva, T.Yu. Sokolová, G.F. Shandurin. – M.: DMK Press, 2001. – 592 s.
Ak knihu napísali štyria autori a publikácia má editora, potom sú všetci uvedení za lomkou (/). Ak má kniha viac ako štyroch autorov, za názvom sa uvádzajú prví traja, za nimi nasleduje lomka (/) a pridajú sa slová „et al“.
3. Rádiotechnické systémy: Proc. pre vysoké školy na špeciálne "Rádiové inžinierstvo" / Yu.P. Grishin, V.P. Ipatov, Yu.M. Kazarinov a ďalší; Ed. Yu.M. Kazarinov. - M .: Vyššie. škola, 1990. - 496 s.
Ak publikácia nemá editora, potom blok „; Ed. Yu.M. Kazarinova.“, neprítomný.
Kniha je preložená z iného jazyka a nemá autora
1. Zdroje Microsoft Windows Server 4.0. Kniha 1: prekl. z angličtiny. - Petrohrad: BHV - Petrohrad, 1997. - 408 s.
Články z časopisu
1. Odnobokov V.V. Zdôvodnenie hlavnej metódy optimálnej alokácie zdrojov.Nauchno-technicheskie vedomosti. - Petrohrad: Vydavateľstvo Štátnej polytechnickej univerzity St. Petersburg, 2003. - roč. 4. - S.55-62.
Články zo zbierky
1. Glazyrin B. E. Automatizácia jednotlivých operácií vo Worde 2000 // Office 2000: 5 kníh. v 1 - M., 2002. - T. 3, Ch. 14. - S. 281-298.
Popis článku je uvedený v názve, ak knihu píšu štyria a viacerí autori. Ak je článok napísaný štyrmi autormi, potom sú všetci uvedení za lomkou (/).
1. A. N. Bogolyubov, A. L. Delitsyn a M. D. Malykh, „O skutočných rezonanciách vo vlnovode s nehomogénnou náplňou,“ Vestn. Moskva univerzite Ser. 3, Fyzika. Astronómia. - 2001. - č. 5. - S. 23–25.
Normy
1. Schémy algoritmov, programov, dát a systémov. Symboly a implementačné pravidlá: GOST 19.701–90 (ISO 5807–85). – Zavedené 1992–01–01. - M .: Gosstandart ZSSR: Vydavateľstvo noriem, 1991. - 26 s.
2. Elektronické zariadenia pre domácnosť. Vstupné a výstupné parametre a typy pripojenia. Technické požiadavky: GOST R 51771–2001. – Zavedené 2002–01–01. - M.: Gosstandart Ruska: Vydavateľstvo noriem, 2001. - 27 s.
Patentové dokumenty
1. Vysielacie zariadenie: Pat. 2187888 Ros. federácia / Chugaeva V.I.; prihlasovateľ a držiteľ patentu Voronež. vedecký výskum in-t pripojenie. - č. 2000131736/09; dec. 18. 12. 2000; publ. 20.08.02, Bull. č. 23 (II. časť). - 3 s.
Elektronické zdroje so vzdialeným prístupom
1. Yu.A. Kochetov. Teória rozhodovania / Novosibirská štátna univerzita. – Režim prístupu: http://math.nsc.ru/LBRT/k5/or.html
2. M. Perov. Organizácia práce so stromovými zoznamami // Mir PK - Electron. časopis. - Vydavateľstvo "Otvorené systémy", 2008. - č. 1. - Režim prístupu k denníku: http://www.osp.ru
3. Výskum v Rusku: viacpredmetový. vedecký časopis / Moskva. fyziky a techniky in-t. – elektrón. časopis - Dolgoprudny: MIPT, 1998. - Režim prístupu k denníku: http://zhurnal.mipt.rssi.ru. - Nie, štát. registračné číslo 0329900013.
Elektronické zdroje lokálneho prístupu
1. Internet krok za krokom. – elektrón. Dan. a progr. - St. Petersburg. : PiterKom, 1997. - 1 elektrón. opt. disk (CD-ROM) + príd. (127 str.)
2. Veľký výkladový slovník anglického a ruského jazyka: 2 v 1. - Elektrón. Dan. a progr. - Maccelesfield (UK): Europa House, 1999. - 1 elektrón. opt. disk (CD-ROM).
3. Visio Professional: Knižnica dizajnéra 5.0. – elektrón. Dan. a progr. - 1997. - 1 elektrón. opt. disk (CD-ROM).
Zoznam obsahuje 2 články v ruštine (povinné ) + 2 preložené do angličtiny. (nepovinné), napísané za účasti žiadateľa.
Aplikácie
Prílohy sú zahrnuté iba v prípade, ak existujú dodatočné a podporné materiály, ktoré zahlcujú text hlavnej časti WRC a na ktoré sa odkazuje v samotnej práci.
Aplikácie môžu obsahovať nasledujúce materiály:
- akt zavádzania výsledkov výskumu do výroby alebo do vzdelávacieho procesu;
– prihláška patentu alebo úžitkového vzoru;
– správa o výskume zaslanom do súťaže študentských prác;
- layouty zariadení, aplikačné softvérové balíky, informácie o správach na konferenciách na tému WRC a pod.
– výskumné protokoly atď.
3.3 Príprava a realizácia finálnej verzie WRC
Požiadavky na dizajn
Text WRC musí byť vytlačený pomocou počítača a tlačiarne na jednej strane bieleho papiera A4 v súlade s GOST 9327-60.
Hlavný text práce je vytlačený v intervaloch 1,5 (27-30 riadkov na stranu) a v 1 intervale (odkazy a poznámky pod čiarou) v Times New Roman, veľkosť 14 (hlavný text), 12 - text v odkazoch, poznámkach pod čiarou a tabuľkách. Veľkosť ľavého okraja je 30 mm, pravého okraja je 10 mm, horný a spodný okraj je po 20 mm. Text práce je zarovnaný na šírku.
Kvalita tlačeného textu a prevedenie ilustrácií a tabuliek musí spĺňať požiadavku na ich zreteľnú reprodukciu. WRC by malo mať jasné čiary, písmená, čísla a znaky.
Tlačové chyby, tlačové chyby a iné nepresnosti v texte môžu byť opravené vymazaním alebo prefarbením bielou farbou a následným nanesením opraveného textu (grafiky) strojovo alebo ručne. Nálepky, poškodenie WRC listov, fľaky nie sú povolené.
Priezvisko, názvy inštitúcií a iné vlastné mená v texte WRC sú uvedené v pôvodnom jazyku. Je dovolené prepisovať vlastné mená a uvádzať názvy inštitúcií preložené do ruštiny s pridaním (pri prvej zmienke) pôvodného mena. Mená píšte v tomto poradí: priezvisko, krstné meno, priezvisko alebo - priezvisko, iniciály oddelené medzerami, nie je dovolené prenášať iniciály oddelene od priezviska do ďalšieho riadku.
Skratka ruských slov a fráz v texte WRC sa vykonáva v súlade s GOST 7.12-93, skratka slov v cudzích európskych jazykoch - v súlade s GOST 7.11-2004. Skratky nasledujúcich slov a fráz nie sú povolené: „od“, „takzvané“, „tak“, „tak“, „napríklad“. Ak WRC prijalo špeciálny systém skratiek pre slová a mená, potom by mal byť zoznam akceptovaných skratiek uvedený v štruktúrnom prvku WRC „Definície, označenia a skratky“. V texte WRC je okrem všeobecne uznávaných abecedných skratiek povolené používať aj abecedné skratky zavedené ich autormi, ktoré skracovali akékoľvek pojmy z príslušných oblastí poznania. V tomto prípade je prvá zmienka o takýchto skratkách uvedená v zátvorkách za celým menom, v budúcnosti sa v texte používajú bez dekódovania.
Číslovanie oddielov, pododdielov, odsekov, pododsekov
Názvy konštrukčných prvkov "OBSAH", "DEFINÍCIE, SYMBOLY A SKRATKY", "ÚVOD", "ZÁVER", "ZOZNAM POUŽITÝCH ZDROJOV" sú nadpisy konštrukčných prvkov WRC.
Nadpisy konštrukčných prvkov WRC sú napísané v strede riadku veľkými písmenami bez bodky, nepodčiarknuté, napr.
ÚVOD
Každý konštrukčný prvok WRC by mal byť vytlačený z nového listu (stránky), vrátane sekcií hlavnej časti.
Oddiely, pododdiely, odseky a pododseky by mali byť očíslované arabskými číslicami a napísané so zarážkou odseku. Sekcie by mali byť v celom texte očíslované postupne, s výnimkou príloh. Príklad – 1, 2, 3 atď. Napríklad:
3 Štúdia účinnosti získaných riešení
Podsekcie sú v rámci sekcie očíslované. Číslo podsekcie obsahuje čísla sekcií a podsekcií oddelené bodkou. Napríklad 1.1, 1.2, 1.3 atď.
Položky by mali byť v každej podsekcii očíslované postupne. Číslo položky obsahuje číslo sekcie a sériové číslo podsekcie a položky oddelené bodkou. Napríklad 1.1.1, 1.1.2 atď.
Číslo pododseku obsahuje číslo oddielu, pododdielu, odseku a poradové číslo pododseku oddelené bodkou. Napríklad 1.1.1.1, 1.1.1.2 atď. Ak časť pozostáva z jedného pododdielu, pododdiel sa nečísluje. Ak pododdiel pozostáva z jedného odseku, odsek sa nečísluje. Ak sa odsek skladá z jedného pododseku, potom sa tento odsek nečísluje. Za číslom oddielu, pododdielu, odseku a pododstavca v texte nedávajte bodku.
Príklad priamo OBSAHU
ÚVOD5
1 Prehľad úloh a prác k výskumnej téme 7
2 Navrhovanie informačných modelov a vývoj algoritmov10
2.1 Výber metód a nástrojov navrhovania10
2.2 Návrh logického systému11
2.3 Návrh fyzického systému13
2.4 Návrh rozloženia používateľského rozhrania15
2.5 Pracovné algoritmy18
3 Technológia softvérovej implementácie vyvinutých modelov a algoritmov25
4.1 Výber nástrojov implementácie25
4.2 Softvérová implementácia používateľského rozhrania systému29
4.3 Zabezpečenie prevádzkovej a informačnej bezpečnosti vyvíjaného systému33
4.4 Zdôvodnenie a ekonomická kalkulácia nákladov na rozvoj systému39
4 Štúdia účinnosti získaných riešení43
4.1 Štúdia efektívnosti konštrukčných riešení43
4.2 Štúdium efektívnosti technologických riešení48
4.3 Štúdium účinnosti vyvinutých algoritmov51
ZÁVER55
LITERATÚRA57
PRÍLOHY59
P.1 Grafický materiál k vysvetlivke59
A.2 Zoznam podprogramu na filtrovanie a zoskupovanie údajov 61
P.3 Zákon o implementácii rozvoja 65
Sekcie a podsekcie by mali mať nadpisy. Nadpisy by mali jasne a stručne odrážať obsah sekcií, podsekcií.
Nadpisy sekcií, podsekcií by mali byť vytlačené s odsadením odseku od veľkého písmena bez bodky na konci, bez podčiarknutia. Ak nadpis pozostáva z dvoch viet, sú oddelené bodkou. Delenie slov v nadpisoch nie je povolené. Názov podsekcie by nemal byť posledný riadok na stránke.
Pred každou položkou v zozname musí byť pomlčka. Ak je to potrebné, odkaz v texte WRC na jeden z prvkov enumerácie, namiesto spojovníka, malých písmen sa umiestnia v poradí ruskej abecedy, počnúc písmenom a (s výnimkou ё, з , й, o, h, ъ, ы, ь). Na ďalšie spresnenie vyčíslení je potrebné použiť arabské číslice, za ktorými sa umiestni zátvorka a zápis sa vykoná z odrážky odseku.
Napríklad,
Stránkovanie
Stránky WRC by mali byť očíslované arabskými číslicami podľa priebežného číslovania v celom texte. Číslo strany je umiestnené v strede spodnej časti listu bez bodky.
Titulná strana, zadanie pre WRC a obsah sú zahrnuté vo všeobecnom číslovaní strán WRC, čísla strán sa na ne neuvádzajú.
Ilustrácie a tabuľky umiestnené v texte WRC na samostatných listoch sú zahrnuté do všeobecného číslovania strán. Ilustrácie a tabuľky na hárku A3 (297×420) sa počítajú ako jedna strana.
Číslovanie strán WRC a príloh zahrnutých do WRC by malo byť nepretržité.
Vzorce
Vzorce sa zadávajú pomocou editora vzorcov Microsoft Equation (súčasť MS Office). V tomto prípade „vzorec“ znamená akúkoľvek sekvenciu najmenej dvoch znakov, ktorá nie je slovom (meno, skratka) v ruštine alebo inom jazyku.
Vzorce sú číslované striktne sekvenčne (v poradí podľa vysvetlivky v texte), v zátvorkách, arabskými číslicami, počnúc od 1. Čísla vzorcov sú uvedené presne na pravom okraji. V tomto prípade sú očíslované len tie vzorce, na ktoré sa v texte odkazuje. Vzorce, ktoré nie sú uvedené v texte článku, nie sú očíslované.
Text vzorca je zarovnaný na ľavú stranu vo vzdialenosti 1,25 centimetra od ľavého okraja textu (od červenej čiary), bez ohľadu na to, či je tento vzorec očíslovaný alebo nie:
Ak sa vzorec nezmestí na riadok, prenesie sa na ďalší riadok za znakom "=" alebo za matematickými znakmi "+", "-" atď. V tomto prípade sa zarovnanie druhého riadku vzorec zostáva rovnaký – 1,25 centimetra od ľavého okraja textového článku, ako je znázornené v príklade so vzorcom (2):
| (2) |
Medzi textom a nasledujúcim vzorcom, vo viacriadkových vzorcoch a medzi vzorcom a nasledujúcim textom sú ponechané prázdne riadky.
Vysvetlenie významov symbolov a číselných koeficientov by malo byť uvedené priamo pod vzorcom v rovnakom poradí, v akom sú uvedené vo vzorci. Hodnota každého symbolu a číselný koeficient by mali byť uvedené na novom riadku. Prvý riadok vysvetlenia začína slovom „kde“ bez dvojbodky za ním. Napríklad:
Absolútne zníženie nákladov práce (DT):
DT \u003d T0 - T1,
kde T0 – mzdové náklady na spracovanie informácií podľa základného prípadu;
T1 - mzdové náklady na spracovanie informácií o navrhovanom variante.
Na písanie premenných (písmen) by ste mali použiť písmo Times, kurzívu, nie tučné (nastavené v nastaveniach Microsoft Equation): napríklad t, V, s, U. Na písanie čísel použite písmo Times, nie kurzívu ( !), nie tučné (nastavené v nastaveniach Microsoft Equation): napríklad 1, 2, 15. Veľkosť písma pre premenné a čísla je 14 bodov. Veľkosti ostatných prvkov vzorca (nastavené v nastaveniach MicrosoftEquation):
Veľký index - 8 bodov;
Malý index - 6 bodov;
Veľký symbol (znaky súčtu, integrál) - 18 bodov;
Malý symbol - 12 bodov.
Na označenie vektorov, matíc je prijateľné použiť iné prvky štylistického dizajnu písiem, napríklad nekurzíva, tučné písmená, písmo Arial atď.
Pre štandardné funkcie (trigonometrické, logaritmické atď.), ako aj pre špeciálne znaky (sup, inf atď.), by ste mali používať písmo Times, nie tučné, nie kurzívu (čo zodpovedá štandardným nastaveniam Microsoft Equation), napríklad,
Ilustrácie
Ilustrácie (výkresy, grafy, schémy, schémy) umiestnené vo WRC musia spĺňať požiadavky štátnych noriem Jednotného systému projektovej dokumentácie. 9.9.2 Všetky ilustrácie v texte WRC (grafy, nákresy, schémy, schémy atď.) sú umiestnené hneď za prvým odkazom na ne (alebo na nasledujúcej strane) a sú označené slovom „Obrázok“.
Text vysvetlivky môže obsahovať množstvo ilustrácií, ktorými môžu byť schémy algoritmov, štruktúry výpočtových stredísk, rozvrhnutie výrobných podkladov spracovaných programom, grafika a pod. Všetky výkresy sú kreslené na výkresovom papieri (formát A4). na samostatných listoch. Popisky obrázkov musia byť tiež v štandardnom písme.
Ilustrácie, s výnimkou ilustrácií príloh, by mali byť očíslované arabskými číslicami prostredníctvom číslovania. V rámci sekcie je povolené číslovanie obrázkov. V tomto prípade sa číslo ilustrácie skladá z čísla sekcie a čísla ilustrácie oddelených bodkou. Napríklad - obrázok 1.1. Pri odkazoch na obrázky by ste mali napísať „... v súlade s obrázkom 2“ pre priebežné číslovanie a „... v súlade s obrázkom 1.2“ pre číslovanie v rámci sekcie.
Ilustrácie, ak je to potrebné, môžu mať názov a vysvetľujúce údaje (obrázkový text). Slovo "Obrázok" a názov sú umiestnené za vysvetľujúcimi údajmi a sú usporiadané nasledovne: Obrázok 1 - Podrobnosti o zariadení.
Obrázok 1 - Popis k obrázku je vycentrovaný, vytlačený netučným písmom veľkosti 12 bodov a v prípade potreby je možné
pokračovanie v ďalšom riadku
Po popise obrázku zostane jeden prázdny riadok a text článku sa naďalej tlačí.
tabuľky
Každá tabuľka by mala mať očíslovaný a tematický (najlepšie) nadpis.
Nadpis číslovania je potrebný pre zjednodušenie spojenia tabuľky s textom; pri odkaze na test stačí uviesť: tab. 1. Tabuľky sú číslované postupne v poradí usporiadania v texte vysvetlivky arabskými číslicami. Slovo "Tabuľka" (s veľkým písmenom) a jeho číslo sú vytlačené kurzívou a zarovnané doprava. Medzi slovom "Tabuľka" a predchádzajúcim odsekom je ponechaný jeden prázdny riadok. Za číslom stola nie je bodka.
Nie je to tak dávno, čo som dostal ponuku vyučovať kurz základov teórie algoritmov na moskovskom lýceu. Samozrejme, rád som súhlasil. V pondelok bola prvá prednáška, na ktorej som sa snažil chalanom vysvetliť metódy na odhadovanie zložitosti algoritmov. Myslím si, že aj niektorým čitateľom Habra môžu byť tieto informácie užitočné, alebo aspoň zaujímavé.
Existuje niekoľko spôsobov, ako merať zložitosť algoritmu. Programátori sa zvyčajne zameriavajú na rýchlosť algoritmu, ale nemenej dôležité sú aj ďalšie ukazovatele - požiadavky na pamäť, voľné miesto na disku. Použitie rýchleho algoritmu nepovedie k očakávaným výsledkom, ak vyžaduje viac pamäte, ako má počítač.
pamäť alebo čas
Mnoho algoritmov ponúka výber medzi veľkosťou pamäte a rýchlosťou. Problém je možné vyriešiť rýchlo s použitím veľkého množstva pamäte alebo pomalšie s použitím menšieho priestoru.Typickým príkladom je v tomto prípade algoritmus na nájdenie najkratšej cesty. Predstavujúc mapu mesta ako sieť, môžete napísať algoritmus na určenie najkratšej vzdialenosti medzi akýmikoľvek dvoma bodmi v tejto sieti. Namiesto toho, aby sme museli počítať tieto vzdialenosti vždy, keď ich potrebujeme, môžeme vypísať najkratšie vzdialenosti medzi všetkými bodmi a uložiť výsledky do tabuľky. Keď potrebujeme zistiť najkratšiu vzdialenosť medzi dvoma danými bodmi, môžeme jednoducho zobrať hotovú vzdialenosť z tabuľky.
Výsledok sa získa okamžite, ale bude vyžadovať obrovské množstvo pamäte. Mapa veľkého mesta môže obsahovať desiatky tisíc bodov. Potom by vyššie opísaná tabuľka mala obsahovať viac ako 10 miliárd buniek. Tie. na zvýšenie rýchlosti algoritmu je potrebné použiť ďalších 10 GB pamäte.
Z tejto závislosti pochádza myšlienka časopriestorovej zložitosti. Pri tomto prístupe je algoritmus hodnotený ako z hľadiska rýchlosti vykonávania, tak aj z hľadiska spotrebovanej pamäte.
Zameriame sa na časovú náročnosť, no aj tak si určite určíme množstvo spotrebovanej pamäte.
Skóre objednávky
Pri porovnávaní rôznych algoritmov je dôležité vedieť, ako závisí ich zložitosť od množstva vstupných údajov. Napríklad pri triedení jednou metódou trvá spracovanie tisíc čísel 1 s a spracovanie milióna čísel 10 s, pri použití iného algoritmu to môže trvať 2 s. a 5 s. resp. V takýchto podmienkach nie je možné jednoznačne povedať, ktorý algoritmus je lepší.Vo všeobecnosti možno zložitosť algoritmu odhadnúť rádovo. Algoritmus má zložitosť O(f(n)), ak so zväčšujúcim sa rozmerom vstupných dát N rastie čas vykonávania algoritmu rovnakou rýchlosťou ako funkcia f(N). Zvážte kód, ktorý pri danej matici A nájde maximálny prvok v každom riadku.
pre i:=1 až N do
začať
max:=A;
pre j:=1 až N do
začať
ak A>max tak
max:=A
koniec;
writeln(max);
koniec;
V tomto algoritme sa premenná i zmení z 1 na N. Pri každej zmene i sa zmení aj premenná j z 1 na N. Počas každej z N iterácií vonkajšej slučky sa N-krát vykoná aj vnútorná slučka. Celkový počet iterácií vnútornej slučky je N*N. To určuje zložitosť algoritmu O(N^2).
Pri odhadovaní poradia zložitosti algoritmu je potrebné použiť len tú časť, ktorá rastie najrýchlejšie. Predpokladajme, že pracovný cyklus je opísaný výrazom N^3+N. V tomto prípade bude jeho zložitosť rovná O(N^3). Zohľadnenie rýchlo rastúcej časti funkcie nám umožňuje vyhodnotiť správanie algoritmu pri zvyšovaní N. Napríklad pre N=100 je rozdiel medzi N^3+N=1000100 a N=1000000 iba 100, čo je 0,01 %.
Pri výpočte O môžete ignorovať konštantné faktory vo výrazoch. Algoritmus s pracovným krokom 3N^3 sa považuje za O(N^3). Vďaka tomu je závislosť vzťahu O(N) na zmene veľkosti úlohy zreteľnejšia.
Definícia obtiažnosti
Najzložitejšie časti programu sú zvyčajne slučky a volania procedúr. V predchádzajúcom príklade sa celý algoritmus vykonáva pomocou dvoch slučiek.Ak jeden postup vyžaduje iný, potom je potrebné dôkladnejšie posúdiť zložitosť toho druhého. Ak sa v ňom vykoná určitý počet inštrukcií (napríklad tlač), potom to nemá na odhad zložitosti prakticky žiadny vplyv. Ak volaná procedúra má O(N) krokov, funkcia môže výrazne skomplikovať algoritmus. Ak sa procedúra volá vnútri slučky, potom môže byť dopad oveľa väčší.
Ako príklad uvažujme dva postupy: Pomalý so zložitosťou O(N^3) a Rýchly so zložitosťou O(N^2).
postup Pomaly;
var
i,j,k: celé číslo;
začať
pre i:=1 až N do
pre j:=1 až N do
pre k:=1 až N do
(nejaká akcia)
koniec;
postup Rýchly;
var
i,j: celé číslo;
začať
pre i:=1 až N do
pre j:=1 až N do
pomalý;
koniec;
postup Oba;
začať
rýchly;
koniec;
Ak sa vo vnútorných slučkách rýchlej procedúry volá procedúra Slow, potom sa zložitosť procedúr znásobí. V tomto prípade je zložitosť algoritmu O(N^2)*O(N^3)=O(N^5).
Ak hlavný program volá procedúry postupne, ich zložitosť sa sčítava: O(N^2)+O(N^3)=O(N^3). Nasledujúci úryvok má presne túto zložitosť:
postup Pomaly;
var
i,j,k: celé číslo;
začať
pre i:=1 až N do
pre j:=1 až N do
pre k:=1 až N do
(nejaká akcia)
koniec;
postup Rýchly;
var
i,j: celé číslo;
začať
pre i:=1 až N do
pre j:=1 až N do
(nejaká akcia)
koniec;
postup Oba;
začať
rýchly;
pomalý;
koniec;
Zložitosť rekurzívnych algoritmov
jednoduchá rekurzia
Pripomeňme, že rekurzívne procedúry sú procedúry, ktoré volajú samy seba. Ich zložitosť je ťažké určiť. Zložitosť týchto algoritmov závisí nielen od zložitosti vnútorných slučiek, ale aj od počtu opakovaní rekurzie. Rekurzívna procedúra môže vyzerať dosť jednoducho, ale môže vážne skomplikovať program tým, že sa viackrát zavolá.Zvážte rekurzívnu implementáciu faktoriálneho výpočtu:
function Factorial(n: Word): integer;
začať
ak n > 1, potom
Faktor:=n*Faktoriál(n-1)
inak
faktoriál:=1;
koniec;
Tento postup sa vykoná N-krát, takže výpočtová zložitosť tohto algoritmu je O(N).
Viacnásobná rekurzia
Rekurzívny algoritmus, ktorý sa volá viackrát, sa nazýva viacnásobná rekurzia. Takéto postupy sa analyzujú oveľa ťažšie a môžu tiež výrazne skomplikovať algoritmus.Zvážte tento postup:
procedure DoubleRecursive(N: integer);
začať
ak N>0 potom
začať
DoubleRecursive(N-1);
DoubleRecursive(N-1);
koniec;
koniec;
Keďže procedúra sa volá dvakrát, dalo by sa predpokladať, že jej čas behu bude O(2N)=O(N). V skutočnosti je však situácia oveľa komplikovanejšia. Ak pozorne preskúmate tento algoritmus, bude zrejmé, že jeho zložitosť je O(2^(N+1)-1)=O(2^N). Vždy treba pamätať na to, že analýza zložitosti rekurzívnych algoritmov je veľmi netriviálna úloha.
Objemová zložitosť rekurzívnych algoritmov
Pre všetky rekurzívne algoritmy je koncept objemovej zložitosti veľmi dôležitý. Každé volanie procedúry vyžaduje malé množstvo pamäte, ale toto množstvo sa môže výrazne zvýšiť počas rekurzívnych volaní. Z tohto dôvodu je vždy potrebné vykonať aspoň povrchovú analýzu objemovej zložitosti rekurzívnych procedúr.Priemerný a najhorší prípad
Odhad zložitosti algoritmu až do poradia je hornou hranicou zložitosti algoritmov. Ak má program veľkú zložitosť, vôbec to neznamená, že algoritmus bude bežať naozaj dlho. Na niektorých súboroch údajov trvá dokončenie algoritmu oveľa menej času, než by naznačovala ich zložitosť. Zvážte napríklad kód, ktorý hľadá daný prvok vo vektore A.function Locate(data: integer): integer;
var
i: celé číslo;
fl: boolean;
začať
fl:=false; i:=1;
zatiaľ čo (nie fl) a (i<=N) do
začať
ak A[i]=údaje potom
fl:=pravda
inak
i:=i+1;
koniec;
ak nie fl tak
i:=0;
Miesto:=I;
koniec;
Ak je požadovaný prvok na konci zoznamu, program bude musieť vykonať N krokov. V tomto prípade bude zložitosť algoritmu O(N). V tomto najhoršom prípade bude čas chodu algoritmu maximálny.
Na druhej strane, prvok, ktorý hľadáte, môže byť na prvej pozícii v zozname. Algoritmus musí urobiť iba jeden krok. Takýto prípad sa nazýva najlepší a jeho zložitosť možno odhadnúť ako O(1).
Oba tieto prípady sú nepravdepodobné. Nás najviac zaujíma očakávaný variant. Ak sú prvky zoznamu na začiatku náhodne zmiešané, požadovaný prvok sa môže objaviť kdekoľvek v zozname. Na nájdenie požadovaného prvku bude v priemere potrebné N/2 porovnaní. Takže zložitosť tohto algoritmu je v priemere O(N/2)=O(N).
V tomto prípade je priemerná a očakávaná zložitosť rovnaká, ale pre mnohé algoritmy je najhorší prípad veľmi odlišný od toho, čo sa očakáva. Napríklad algoritmus rýchleho triedenia v najhoršom prípade má zložitosť O(N^2), zatiaľ čo očakávané správanie je O(N*log(N)), ktoré je oveľa rýchlejšie.
Bežné funkcie odhadu zložitosti
Teraz uvedieme niektoré funkcie, ktoré sa najčastejšie používajú na výpočet zložitosti. Funkcie sú uvedené v poradí podľa narastajúcej zložitosti. Čím vyššie je funkcia v tomto zozname, tým rýchlejšie pobeží algoritmus s týmto odhadom.1. C je konštanta
2.log(log(N))
3 denník (N)
4, N^C, 0
6.N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Ak chceme odhadnúť zložitosť algoritmu, ktorého rovnica zložitosti obsahuje niekoľko týchto funkcií, potom rovnicu môžeme zredukovať na funkciu nižšie v tabuľke. Napríklad O(log(N)+N!)=O(N!).
Ak sa algoritmus volá zriedkavo a pre malé množstvo údajov, zložitosť O (N ^ 2) možno považovať za prijateľnú, ale ak algoritmus funguje v reálnom čase, výkon O (N) nie je vždy dostatočný.
Algoritmy so zložitosťou N*log(N) zvyčajne pracujú s dobrou rýchlosťou. Algoritmy so zložitosťou N^C je možné použiť len pre malé hodnoty C. Výpočtová zložitosť algoritmov, ktorých poradie je určené funkciami C^N a N! je veľmi veľký, takže takéto algoritmy možno použiť len na spracovanie malého množstva údajov.
Na záver uvádzame tabuľku, ktorá ukazuje, ako dlho počítač vykonávajúci milión operácií za sekundu vykoná niektoré pomalé algoritmy.
