Kaj so računalniški algoritmi in kako delujejo?
Če niste v matematiki ali programiranju, je lahko beseda »algoritem« grška, vendar je to eden od gradnikov vsega, kar uporabljate za branje tega članka. Tukaj je hitra razlaga, kaj so in kako delujejo.
Opozorilo: Nisem učitelj matematike ali računalništva, zato niso vsi izrazi, ki jih uporabljam, tehnični. To je zato, ker poskušam razložiti vse, kar je v preprostem angleškem jeziku, ker ljudje niso dovolj zadovoljni z matematiko. Ob tem se je pojavilo nekaj matematike in to je neizogibno. Matematični geeksi, vas prosimo, da popravite ali bolje razložite v komentarjih, vendar vas prosimo, da je preprosto za matematično nenaklonjenost med nami.
Slika po Ian Ruotsala
Kaj je algoritem?
Beseda "algoritem" ima etimologijo podobno "algebri", razen da se to nanaša na samega arabskega matematika, al-Khwarizmija (samo zanimivo malenkost). Algoritem za nas, ki ni programer, je nabor navodil, ki vzamejo vhod, A, in zagotavljajo izhod, B, ki na nek način spreminja podatke. Algoritmi imajo veliko različnih aplikacij. V matematiki lahko pomagajo izračunati funkcije iz točk v podatkovnem nizu, med veliko naprednejšimi stvarmi. Poleg njihove uporabe pri samem programiranju igrajo pomembno vlogo pri stiskanju datotek in šifriranju podatkov.
Osnovni nabor navodil
Recimo, da se tvoj prijatelj srečuje v trgovini in ga vodiš proti sebi. Govorite stvari, kot je »vstopite skozi vrata na desni strani«, »preidite odsek za ribe na levi,« in »če vidite mleko, ste mi mimo.« Algoritmi delujejo tako. Lahko uporabimo diagram poteka za ponazoritev navodil, ki temeljijo na merilih, ki jih poznamo vnaprej, ali pa ugotovimo med postopkom.
(podoba z naslovom »Icebreaking Routine«) EDIT: zahvaljujoč Trigger in Freewheel)
Iz START-a bi se vrnili po poti in odvisno od tega, kaj se zgodi, sledite “toku” do končnega rezultata. Diagrami poteka so vizualna orodja, ki lahko bolj razumljivo predstavljajo sklop navodil, ki jih uporabljajo računalniki. Podobno pomagajo tudi algoritmi z več matematičnimi modeli.
Grafi
Uporabimo graf za ponazoritev različnih načinov, kako lahko dajemo navodila.
Ta graf lahko izrazimo kot povezavo med vsemi njegovimi točkami. Da bi reproducirali to sliko, lahko nekomu damo niz navodil.
Metoda 1
To lahko predstavimo kot niz točk, informacija pa sledi standardni obliki grafa = (x1, y1), (x2, y2),…, (xn, yn).
graf = (0,0), (3,0), (3,3), (5,5), (7,10), (8,7), (9,4), (10,1)
Zelo enostavno je, da vsako točko narišemo eno za drugo in jo povežemo s prejšnjo točko. Vendar si zamislite graf s tisoč točkami ali več segmenti, ki gredo vse na katero koli smer. Ta seznam bi imel veliko podatkov, kajne? In potem mora biti povezovanje vsakega, enega za drugim, bolečina.
Metoda 2
Še ena stvar, ki jo lahko naredimo, je dati začetno točko, naklon črte med njo in naslednjo točko, in navesti, kje lahko pričakujemo naslednjo točko z uporabo standardne oblike grafa = (začetna točka, [m1, x1, h1] ],…, [Mn, xn, hn] Tukaj, spremenljivka 'm' predstavlja naklon vrstice, 'x' predstavlja smer štetja v (ali x ali y), 'h' pa vam pove, kako Lahko se spomnite tudi, da boste po vsakem premiku narisali točko.
graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 1], [-3, x, 1], [-3, x, 1]
Na koncu boste dobili isti graf. Vidite lahko, da so zadnji trije izrazi v tem izrazu enaki, tako da bomo morda lahko to zmanjšali tako, da bomo na nek način rekli »ponovite to trikrat«. Recimo, da kadarkoli vidite spremenljivko „R“, pomeni, da ponovite zadnjo stvar. To lahko storimo:
graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 1], [R = 2]
Kaj, če posamezne točke dejansko niso pomembne in samo graf je sam? Te zadnje tri razdelke lahko združimo tako:
graf = (0,0), [0, x, 3], [0, y, 3], [1, x, 2], [2,5, x, 2], [-3, x, 3]
Nekoliko se skrajša z mesta, kjer so bili prej.
Metoda 3
Poskusimo to narediti drugače.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤8
y = -3x + 29, 8≤x≤9
y = -3x + 29, 9≤x≤10
Tukaj ga imamo v čistih algebrskih izrazih. Še enkrat, če točke same niso pomembne in samo graf ima, lahko združimo zadnje tri točke.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤10
Katera metoda je odvisna od vaših sposobnosti. Morda ste super z matematiko in grafiko, tako da izberete zadnjo možnost. Morda ste dobri pri navigaciji, tako da izberete drugo možnost. Na področju računalnikov pa opravljate veliko različnih nalog in zmožnost računalnika se dejansko ne spremeni. Zato so algoritmi optimizirani za naloge, ki jih opravijo.
Druga pomembna točka je, da vsaka metoda temelji na ključu. Vsak niz navodil je neuporaben, če ne veste, kaj storiti z njimi. Če ne veste, da bi morali načrtovati vsako točko in povezati pike, prvi niz točk ne pomeni nič. Če ne veste, kaj vsaka spremenljivka pomeni v drugi metodi, ne boste vedeli, kako jih uporabiti, podobno kot ključ do šifre. Ta ključ je tudi sestavni del uporabe algoritmov in pogosto se ta ključ nahaja v skupnosti ali prek »standarda«.
Stiskanje datotek
Ko prenesete datoteko .zip, jo izvlečete, tako da lahko uporabite vse, kar je v njej. Danes lahko večina operacijskih sistemov potopi v .zip datoteke, kot so bile običajne mape, in počne vse v ozadju. Na mojem računalniku z operacijskim sistemom Windows 95 pred desetletjem sem moral vse ročno izločiti, preden sem lahko videl kaj več kot imena datotek znotraj. To je zato, ker je bilo to, kar je bilo shranjeno na disku kot .zip datoteka, v uporabni obliki. Pomislite na raztegljiv kavč. Ko ga želite uporabiti kot posteljo, morate odstraniti blazine in jo raztegniti, kar zavzame več prostora. Ko ga ne potrebujete ali ga želite prevažati, ga lahko zložite nazaj.
Kompresijski algoritmi so prilagojeni in optimizirani posebej za vrste datotek, na katere so usmerjene. Zvočne oblike, na primer, uporabljajo drugačen način za shranjevanje podatkov, ki bodo, ko bodo dekodirani z avdio kodekom, dali zvočno datoteko, podobno originalni valovni obliki. Za več informacij o teh razlikah, si oglejte naš prejšnji članek, Kakšne so razlike med vsemi tistimi avdio formati? Zvočne formate brez datotek z izgubo in datoteke .zip imajo eno skupno lastnost: ob izločitvi dekompresije obe vrnejo izvirne podatke v natančni obliki. Zgoščeni zvočni kodeki uporabljajo druga sredstva, da prihranijo prostor na disku, kot so obrezovanje frekvenc, ki jih človeška ušesa ne morejo slišati, in izravnavanje valovne oblike v odsekih, da se odpravijo nekatere podrobnosti. Na koncu, čeprav morda ne bomo mogli res slišati razlike med MP3 in CD posnetkom, je zagotovo primanjkljaj informacij v prejšnjem.
Šifriranje podatkov
Algoritmi se uporabljajo tudi pri varovanju podatkovnih ali komunikacijskih linij. Namesto shranjevanja podatkov, tako da porabi manj prostora na disku, so shranjeni na način, ki ga drugi programi ne morejo zaznati. Če nekdo ukrade vaš trdi disk in ga začne skenirati, lahko zbirajo podatke tudi, če izbrišete datoteke, ker so podatki še vedno tam, čeprav je lokacija posredovanja vanje izginila. Ko so podatki šifrirani, ne glede na to, kaj je shranjeno, ne izgleda, kot je. Ponavadi je videti naključno, kot da se je drobitev sčasoma povečala. Prav tako lahko shranite podatke in jih prikažete kot drugo vrsto datoteke. Slikovne datoteke in glasbene datoteke so dobre za to, saj so lahko precej velike, ne da bi na primer vzbudile sumnje. Vse to poteka z uporabo matematičnih algoritmov, ki vzamejo nekakšen vhod in ga pretvorijo v drugo, zelo specifično vrsto izhoda. Za več informacij o delovanju šifriranja si oglejte HTG Explains: Kaj je šifriranje in kako deluje?
Algoritmi so matematična orodja, ki omogočajo različne uporabe v računalništvu. Delujejo tako, da na dosleden način zagotovijo pot med začetno in končno točko in zagotovijo navodila za sledenje. Veš več, kot smo poudarili? Delite svoja pojasnila v komentarjih!
