Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai

Įvadas

Čia reikia bėgti kiek įkabini, kad išsilaikytum toje pačioje vietoje.
O jei nori patekti kur nors kitur, reikia bėgti dvigubai greičiau.

Luisas Kerolis, „Alisa veidrodžių karalystėje“

Ši knygelė skirta moksleiviams, kurie ruošiasi dalyvauti informatikos olimpiadose. Galima svarstyti ir ginčytis, ką reiškia žodis informatika, tačiau pasaulinių olimpiadų kontekste informatikos olimpiada – tai pirmiausia įdomūs algoritmavimo uždaviniai, kuriems išspręsti reikia ne tik išmanyti įvairius algoritmus, bet ir rasti įdomių, netradicinių sprendimų bei sugebėti per keletą valandų „materializuoti“ savo idėjas veikiančiomis programomis.

Informatikos olimpiados jau beveik dvidešimt metų kasmet rengiamos Lietuvoje ir beveik tiek pat metų geriausi Nacionalinės informatikos olimpiados dalyviai atstovauja Lietuvai Baltijos bei pasaulinėse informatikos olimpiadose. Knygelėje aprašyti svarbūs algoritmai ir metodai, kuriuos turėtų žinoti kiekvienas norintis sėkmingai dalyvauti šiose olimpiadose. Tiesa, čia nėra griežtų algoritmų teisingumo įrodymų, kurie pateikiami aukštųjų mokyklų vadovėliuose. Algoritmų teisingumas dažniausiai grindžiamas intuityviai, o teorija iliustruojama konkrečiais uždaviniais, paimtais iš realių olimpiadų. Leidinyje pateikėme sutrumpintas uždavinių sąlygas, atmetę daug detalių, susijusių su automatiniu programų testavimu. Dauguma sprendimų pateikti kaip Paskalio kalbos [1] procedūros ar funkcijos, stengiantis kuo mažiau prisirišti prie konkrečios programavimo kalbos subtilumų. Tad leidinys puikiausiai tiks ir programuojantiems kitomis programavimo kalbomis.

Tikimės, kad knygelė bus pirmasis rengimosi informatikos olimpiadoms etapas. Jį įveikus dar bus ilgas kelias, kuriame teks spręsti daugybę įdomių uždavinių ir kuriuo reikės bėgti dvigubai greičiau, norint pasiekti daugiau.

Už vertingas pastabas ir pagalbą rengiant šį leidinį nuoširdžiai dėkojame Lietuvos moksleivių informatikos olimpiados vertinimo komisijos nariams Justui Kranauskui, Martynui Kriaučiūnui bei Mindaugui Plukui.

Autoriai

Turinys

Išnašos

[1]Knygelėje pateiktos programos kompiliuotos Free Pascal kompiliatoriumi, kuris naudojamas ir tarptautinėse olimpiadose (www.freepascal.org).