Čo sú počítačové algoritmy a ako fungujú?

Pokiaľ sa nenachádzate v matematike alebo programovaní, slovo "algoritmus" môže byť pre vás gréčtina, ale je to jeden zo stavebných kameňov všetkého, čo používate na prečítanie tohto článku. Tu je rýchle vysvetlenie toho, akí sú a ako fungujú.

Odmietnutie zodpovednosti: Nie som učiteľ matematiky alebo informatiky, takže nie všetky termíny, ktoré používam, sú technické. Je to preto, že sa snažím vysvetliť všetko v jednoduchej angličtine, lebo ľudia nie sú úplne spokojní s matematikou. Hovorí sa, že je tu nejaká matematika, a to je nevyhnutné. Math geeks, neváhajte opraviť alebo lepšie vysvetliť v komentároch, ale prosím, držať to jednoduché pre matematicky neospravedlnený medzi nami.

Obrázok podľa Ian Ruotsala

Čo je to algoritmus?

Slovo "algoritmus" má etymológiu podobnú "algebru", s výnimkou toho, že sa to týka arabského matematika sám al-Khwarizmi (len zaujímavý tidbit). Algoritmus pre neprogramovateľov medzi nami je súbor pokynov, ktoré majú vstup A, a poskytujú výstup, B, ktorý nejakým spôsobom mení niektoré údaje. Algoritmy majú širokú škálu aplikácií. V matematike môžu pomôcť vypočítať funkcie z bodov v súbore údajov, medzi oveľa pokročilejšie veci. Okrem ich použitia v samotnom programovaní hrajú dôležité úlohy v oblasti kompresie súborov a šifrovania dát.

Základná sada pokynov

Povedzme, že váš priateľ sa s vami stretne v obchode s potravinami a budete ho sprevádzať. Hovoríte veci ako "príjdite cez pravej strane dverí", "prejdite ryteckú sekciu vľavo" a "ak vidíte mliečne výrobky, prechádzate mi." Algoritmy fungujú takto. Môžeme použiť vývojový diagram, aby sme ilustrovali pokyny na základe kritérií, o ktorých vieme predčasne alebo ktoré sme zistili počas procesu.

(obrázok s názvom "Spustenie ľadu" EDIT: zdvorilosť Trigger a Freewheel)

Zo štartu by ste šli po ceste a podľa toho, čo sa deje, postupujte podľa "toku" na konečný výsledok. Vývojové diagramy sú vizuálne nástroje, ktoré môžu pochopiteľne predstavovať súbor pokynov používaných počítačmi. Podobne algoritmy pomáhajú robiť to isté s viacerými matematickými modelmi.

grafy

Použite graf na ilustráciu rôznych spôsobov, ako môžeme dať smer.

Tento graf môžeme vyjadriť ako spojenie medzi všetkými jeho bodmi. Aby sme mohli reprodukovať tento obrázok, môžeme dať súbor inštrukcií niekomu inému.

Metóda 1

Môžeme to reprezentovať ako sériu bodov a informácie by sa mali riadiť štandardnou formou grafu = (x1, y1), (x2, y2), ..., (xn, yn).

graf = (0,0), (3,0), (3,3), (5,5), (7,10), (8,7), (9,4)

Je veľmi ľahké vykresliť každý bod jeden po druhom a pripojiť ho k predchádzajúcemu bodu. Predstavte si však graf s tisíckami bodov alebo viacerými segmentmi, ktoré všetko ide. Tento zoznam by mal veľa údajov, nie? A potom sa musieť spojiť každý jeden, jeden po druhom, môže byť bolesťou.

Metóda 2

Ďalšia vec, ktorú môžeme urobiť, je dať začiatočný bod, sklon línie medzi ním a ďalším bodom a naznačiť, kde môžete očakávať ďalší bod použitím štandardnej formy grafu = (štartovací bod), [m1, x1, h1 ], ..., [mn, xn, hn], kde premenná "m" predstavuje sklon riadku, "x" predstavuje smer na započítanie (či x alebo y) a "h" veľa sa počíta do uvedeného smeru. Môžete si tiež zapamätať, že vykresliť bod po každom pohybe.

graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [ [-3, x, 1], [-3, x, 1]

Budete mať rovnaký graf. Môžete vidieť, že posledné tri výrazy v tomto vyjadrení sú rovnaké, takže môžeme byť schopní to znížiť len tým, že hovorí "opakovať, že trikrát" nejakým spôsobom. Povedzme, že kedykoľvek uvidíte premennú 'R', znamená to opakovať poslednú vec. Zvládneme to:

graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [ [R = 2]

Čo ak jednotlivé body naozaj nezáleží, a len vlastný graf? Tieto posledné tri časti môžeme konsolidovať takto:

graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [

To trochu skracuje veci od miesta, kde boli predtým.

Metóda 3

Skúsme to urobiť iným spôsobom.

y = 0, 0 x = 0, 0≤y≤3
y = x, 3 y = 2,5x-7,5, 5 y = -3x + 29, 7 y = -3x + 29, 8 y = -3x + 29, 9

Tu to máme v čistom algebrickom pojme. Opäť, ak body samy nezáleží a iba graf robí, môžeme konsolidovať posledné tri položky.

y = 0, 0 x = 0, 0≤y≤3
y = x, 3 y = 2,5x-7,5, 5 y = -3x + 29, 7

Teraz, akú metódu si vyberiete, závisí od vašich schopností. Možno ste skvelý s matematikou a grafovaním, takže si vyberiete poslednú možnosť. Možno ste pri navigácii dobré, takže si vyberiete druhú možnosť. V oblasti počítačov však robíte mnoho rôznych druhov úloh a schopnosť počítača sa naozaj nezmení. Preto sú algoritmy optimalizované pre úlohy, ktoré dokončili.

Ďalším dôležitým bodom je, že každá metóda závisí od kľúča. Každá sada pokynov je zbytočná, ak neviete, čo s nimi robiť. Ak neviete, že by ste mali vykreslovať každý bod a pripojiť bodky, prvý súbor bodov neznamená nič. Ak neviete, čo každá premenná znamená v druhej metóde, nebudete vedieť, ako ich aplikovať, rovnako ako kľúč k šifry. Tento kľúč je tiež neoddeliteľnou súčasťou používania algoritmov a často sa tento kľúč nachádza v komunite alebo prostredníctvom "štandardu".

Kompresia súborov

Pri preberaní súboru .zip extrahujete obsah tak, aby ste mohli používať všetko, čo je vnútri. V súčasnosti sa väčšina operačných systémov môže ponoriť do súborov .zip, ako sú normálne priečinky, robia všetko na pozadí. Na mojom systéme Windows 95 pred viac ako desiatimi rokmi musel som všetko vyradiť ručne, než som mohol vidieť niečo viac ako názvy súborov vo vnútri. To preto, že to, čo bolo uložené na disku ako súbor .zip, nebolo v použiteľnej forme. Zamyslite sa nad rozťahovacím gaučom. Keď ju chcete použiť ako posteľ, musíte odstrániť podložky a rozvinúť, čo zaberie viac miesta. Keď ho nepotrebujete alebo ho chcete prepravovať, môžete ho zložiť späť.

Kompresné algoritmy sú upravené a optimalizované špeciálne pre typy súborov, na ktoré sú zacielené. Formáty zvuku napríklad používajú iný spôsob ukladania údajov, ktoré pri dekódovaní zvukovým kodekom poskytujú zvukový súbor podobný pôvodnému tvaru vlny. Viac informácií o týchto rozdieloch nájdete v našom predchádzajúcom článku, Aké sú rozdiely medzi všetkými týmito formátmi zvuku? Lossless audio formáty a súbory .zip majú jednu vec spoločnú: obaja prinášajú pôvodné dáta v presnej podobe po procese dekompresie. Zneužívajúce zvukové kodeky používajú iné prostriedky na šetrenie miesta na disku, ako napríklad orezávanie frekvencií, ktoré ľudské uši nedajú počuť a vyhladenie kriviek v sekciách, aby sa zbavili nejakých detailov. Nakoniec, aj keď pravdepodobne nebudeme môcť naozaj počuť rozdiel medzi skladbou MP3 a CD, je v bývalom.

Šifrovanie údajov

Algoritmy sa používajú aj pri zabezpečovaní dátových alebo komunikačných liniek. Namiesto ukladania dát tak, aby používalo menej miesta na disku, je uložené spôsobom, ktorý nedokáže detekovať iné programy. Ak niekto ukradne pevný disk a začne ho skenovať, môže zobrať dáta aj po odstránení súborov, pretože samotné dáta sú stále tam, hoci miesto preposielania je preč. Keď sú dáta šifrované, čo je uložené, nevyzerá to, čo to je. Zvyčajne to vyzerá náhodne, ako keby sa fragmentácia časom rozvinula. Môžete tiež uložiť údaje a vytvoriť ich ako iný typ súboru. Obrazové súbory a hudobné súbory sú pre to dobré, pretože môžu byť pomerne veľké, bez toho, aby sa napríklad vytvárali podozrenie. To všetko sa vykonáva pomocou matematických algoritmov, ktoré berú nejaký druh vstupu a konvertujú ho na iný, veľmi špecifický typ výstupu. Viac informácií o tom, ako funguje šifrovanie, nájdete na stránke HTG vysvetľuje: Čo je šifrovanie a ako funguje?

Algoritmy sú matematické nástroje, ktoré poskytujú rôzne použitia v informatike. Pracujú tak, aby poskytovali cestu medzi začiatočným bodom a koncovým bodom konzistentným spôsobom a poskytovali pokyny, aby ich nasledovali. Dozvedieť viac, ako sme zdôraznili? Zdieľajte svoje vysvetlenia v komentároch!