Algoritmas – aiškiai aprašytas veiksmų būdas tam tikram uždaviniui išspręsti. Jis nurodo, ką daryti, kokia tvarka, kada pasirinkti vieną iš kelių veiksmų ir kada darbą baigti. Algoritmus vykdo ne tik kompiuteriai: tiksliai aprašyta paieškos ar skaičiavimo tvarka gali vadovautis ir žmogus.
Paprasčiausias supratimo testas toks: ar kitas žmogus, gavęs tuos pačius pradinius duomenis ir taisykles, žinotų, ką atlikti toliau? Nurodymas „sutvarkyk sąrašą“ dar per miglotas. „Surikiuok skaičius nuo mažiausio iki didžiausio“ nusako tikslą, tačiau pačiam algoritmui dar reikia veiksmų.
Iš ko sudarytas algoritmas?
Pradėkite nuo trijų klausimų: kokius duomenis gauname, ką su jais darome ir kokį rezultatą turime pateikti. Pavyzdžiui, ieškant didžiausio skaičiaus, įvestis yra skaičių sąrašas, veiksmai – jų palyginimas, o išvestis – didžiausia reikšmė.
| Dalis | Pavyzdys | Ką būtina susitarti? |
|---|---|---|
| Įvestis | 4, 9, 2, 7 | Ar priimami tik skaičiai? Ką daryti su tuščiu sąrašu? |
| Taisyklės | Palyginti kiekvieną skaičių su iki tol didžiausiu | Kokia tvarka tikrinti ir kada atnaujinti rezultatą? |
| Išvestis | 9 | Ar reikia reikšmės, jos vietos, ar abiejų? |
Šis susitarimas svarbus dar prieš rašant kodą. Jei užduotyje prašoma „rasti geriausią pasiūlymą“, pirmiausia reikia apibrėžti, ką reiškia geriausias: pigiausias, greičiausiai pristatomas ar atitinkantis kitą sąlygą.
Trys pagrindinės idėjos: seka, pasirinkimas ir kartojimas
Seka: veiksmai atliekami nustatyta tvarka. Tarkime, dokumentą reikia išsaugoti prieš uždarant programą. Sukeitus veiksmus vietomis, rezultatas gali pasikeisti.
Pasirinkimas: tolesnis veiksmas priklauso nuo sąlygos. Jei turite pakankamai pinigų pirkiniui, galite tęsti apmokėjimą; jei trūksta, reikia kito sprendimo. Svarbu aprašyti ne tik „taip“, bet ir „ne“ atvejį.
Kartojimas: tą pačią veiksmų grupę atliekate keliems objektams arba tol, kol įvykdoma sąlyga. Tikrindami pirkinių sąrašą pakartojate klausimą „ar šios prekės jau turiu?“ kiekvienai jo eilutei.
Šios idėjos įtrauktos ir į Lietuvos informatikos bendrąją programą. Programavimo kalbose jos turi konkrečias komandas, tačiau jas galima suprasti net nežinant nė vienos kalbos sintaksės.
Pavyzdys: kaip rasti didžiausią skaičių?
Turime keturias reikšmes: 4, 9, 2, 7. Užuot prašę „iškart pamatyti atsakymą“, aprašome procedūrą, tinkamą ir daug ilgesniam sąrašui.
- Patikrinkite, ar sąraše yra bent vienas skaičius ir ar visi įrašai tinkami skaičiai. Jei ne, pateikite aiškų pranešimą.
- Pirmą skaičių laikykite kol kas didžiausiu.
- Eikite per likusius skaičius po vieną. Jei tikrinamas skaičius didesnis už įsimintą, pakeiskite įsimintą reikšmę.
- Pasiekę sąrašo pabaigą pateikite įsimintą reikšmę ir baikite darbą.
| Tikrinamas skaičius | Veiksmas | Kol kas didžiausias |
|---|---|---|
| 4 | Pradinis pasirinkimas | 4 |
| 9 | 9 didesnis už 4 – pakeičiame | 9 |
| 2 | 2 mažesnis už 9 – nekeičiame | 9 |
| 7 | 7 mažesnis už 9 – nekeičiame | 9 |
Tai galima užrašyti pseudokodu – suprantamu, bet prie konkrečios programavimo kalbos nepririštu tekstu: „didžiausias = pirmas skaičius; kiekvienam likusiam skaičiui: jei jis didesnis, atnaujink didžiausią; pateik atsakymą“. Pseudokodas aiškina sprendimą, o veikianti programa turi dar įgyvendinti įvesties tikrinimą ir rezultatų pateikimą.
Kodėl vien gražaus pavyzdžio neužtenka?
Patikrinkite ne tik įprastą sąrašą. Jei pradžioje „didžiausiam“ visada priskirtumėte nulį, sąrašui −8, −3, −12 klaidingai gautumėte 0, nors jo duomenyse nėra. Todėl naudojome pirmą tikrą sąrašo reikšmę.
- Vienas skaičius, pavyzdžiui, 5: rezultatas 5, papildomų palyginimų nereikia.
- Vienodos reikšmės 2, 2: didžiausia reikšmė 2; jei reikia jos vietos, papildomai susitarkite, kurią grąžinti.
- Tuščias sąrašas: nėra skaičiaus, kurį galima paskelbti didžiausiu. Reikia pranešimo, o ne išgalvoto nulio.
- Skaičių ir teksto mišinys: mūsų pavyzdžio taisyklės tokios įvesties nepriima; duomenis reikia pataisyti.
Taip tikrinama ne tik ar gavome atsakymą, bet ir ar užduotis pakankamai tiksliai apibrėžta.
Ar visi algoritmai vienodai greiti?
Ne. Ieškoti pavardės tikrinant kiekvieną įrašą iš eilės galima ir nesurikiuotame sąraše. Tačiau surikiuotame sąraše galima taikyti dvejetainę paiešką: tikrinti vidurį ir po kiekvieno palyginimo atmesti netinkamą pusę. Be rikiavimo šis būdas negarantuotų teisingo rezultato.
Pavyzdžiui, sąraše 2, 4, 6, 8, 10, 12, 14 ieškant 12, pirmiausia tikrinamas 8, tada dešinės dalies vidurys 12. Šiame pavyzdyje pakanka dviejų tikrinimų; einant iš kairės reikėtų šešių. Tai palyginimų pavyzdys, ne pažadas, kad kiekvienoje programoje laikas sutrumpės lygiai tris kartus.
Kuo algoritmas skiriasi nuo programos ir dirbtinio intelekto?
Algoritmas nusako sprendimo būdą, o programa jį įgyvendina kompiuteriui suprantamomis komandomis. Tą pačią idėją galima užrašyti skirtingomis programavimo kalbomis. Programa taip pat tvarko failus, ekranus, ryšį ir kitus darbus, kurių vieno algoritmo paaiškinime gali nebūti.
Dirbtinio intelekto sistemos naudoja algoritmus, tačiau ne kiekvienas algoritmas yra dirbtinis intelektas. Didžiausio skaičiaus paieškai mokyti modelio nereikia. O sakydami „paieškos algoritmas“ dažnai sutrumpiname daug sudėtingesnę sistemą: pati „Google“ aprašo daugybę sistemų ir signalų, o ne vieną viską sprendžiančią taisyklę.
Dažni klausimai
Ar receptas gali būti algoritmas?
Taip, tai patogus kasdienis pavyzdys, kai nurodyti aiškūs produktai, veiksmai ir pabaigos kriterijus. Miglotos frazės, pavyzdžiui, „padarykite gerai“, rodo, kur aprašą dar reikia tikslinti.
Ar algoritmui būtinas kompiuteris?
Ne. Jį galite vykdyti ranka, pavaizduoti schema ar užrašyti žodžiais. Kompiuteris leidžia tiksliai automatizuoti aprašytus veiksmus.
Nuo ko pradėti kuriant savo algoritmą?
Užrašykite tikslą, įvestį ir norimą rezultatą. Tada išskaidykite darbą žingsniais, aprašykite išimtis ir peržaiskite bent įprastą, ribinį bei netinkamos įvesties atvejį.
