I. Programavimo gebėjimai, sudėtingesni sintaksės dalykai, programavimo metodikos
Gebėjimas naudotis sudėtingomis duomenų struktūromis: abstrakčių duomenų struktūrų suvokimas ir naudojimas, grafo savybių panaudojimas sudėtingesniems uždaviniams spręsti, matematikos panaudojimas programavimo uždaviniams spręsti.
| Mokinių įgyjami gebėjimai: | Mokinių įgyjamos žinios ir supratimas |
| 1. Paaiškinti objekto sąvoką, gebėti kurti objektus, juos kopijuoti bei panaikinti. | 1.1 Paaiškinti, kas yra objektas, pateikti pavyzdžių;
1.2 Paaiškinti, kas yra objekto savybės, kam jos naudojamos, pateikti pavyzdžių. 1.3 Kurti paprasčiausius objektus. 1.4 Kopijuoti objektus. 1.5 Naikinti objektus. 1.6 Naudoti objektus rašant programas. |
| 2. Paaiškinti klasės sąvoką, kurti klasę, reikalingą uždaviniui išspręsti | 2.1 Paaiškinti klasės sąvoką, pateikti pavyzdžių.
2.2 Paaiškinti klasės aprašo dalis. Aprašyti naują klasę. 2.3 Paaiškinti konstruktoriaus sąvoką, pateikti pavyzdžių. 2.4 Paaiškinti destruktoriaus sąvoką, pateikti pavyzdžių. 2.5 Paaiškinti paveldėjimo savybę. Pateikti pavyzdžių. |
| 3. Apibūdinti, aprašyti ir naudoti uždaviniams spręsti abstrakčiąsias duomenų struktūras | 3.1 Apibūdinti abstrakčiąsias duomenų struktūras, apibrėžti galimas operacijas, savybes, pateikti pavyzdžių. Parengti abstrakčios duomenų struktūros specifikaciją.
3.2 Apibūdinti dvejetainį medį, apibūdinti pilną, tobulą bei užbaigtą dvejetainius medžius, naudoti dvejetainį medį paieškoje. Pateikti pavyzdžių. 3.3 Apibūdinti duomenų struktūrą heap (Prioritetinė eilė, krūva). Apibrėžti galimas operacijas. Pateikti pavyzdžių. 3.4 Apibūdinti dėstymo lenteles (hash tables), apibrėžti galimas operacijas. Pateikti naudojimo pavyzdžių. 3.5 Apibūdinti intervalų medžio sąvoką. Apibrėžti galimas operacijas. Pateikti naudojimo pavyzdžių. 3.6 Apibūdinti žodyno medžio (trie) sąvoką. Apibrėžti galimas operacijas. Pateikti naudojimo pavyzdžių. 3.7 Apibūdinti dvejetainio indeksuoto medžio (binary indexed tree) sąvoką. Apibrėžti galimas operacijas. Pateikti naudojimo pavyzdžių. |
| 4. Apibūdinti, aprašyti ir naudoti uždaviniams spręsti sudėtingesnius grafų teorijos algoritmus. | 4.1 Prisiminti pagrindines grafo ir su juo susijusias sąvokas. Prisiminti paieškos platyn algoritmą, bei jo taikymus.Tyrinėti grafo ciklų paieškos algoritmą. Pateikti pritaikymo pavyzdžių. Prisiminti, kas yra jungus grafas ir jungumo komponentės. Apibrėžti stipriai jungias komponentes. Pateikti panaudojimo pavyzdžių. Apibrėžti dvigubai jungias komponentes. Pateikti panaudojimo pavyzdžių (uždaviniai tiltų paieškai). 4.2 Prisiminti Dijkstros trumpiausio kelio algoritmą. Apsirašyti sudėtingesnę jo versiją. Apskaičiuoti jo sudėtingumą. Pateikti taikymo pavyzdžių. 4.3 Aprašyti Bellman-Ford algoritmą. Apskaičiuoti jo sudėtingumą. Pateikti panaudojimo pavyzdžių. 4.4 Aprašyti Floyd-Warshal algoritmą. Apskaičiuoti jo sudėtingumą. Pateikti panaudojimo pavyzdžių. 4.5 Apibrėžti tinklo srauto (network flow) uždavinį. Pateikti algoritmus šiam uždaviniui spręsti: Ford-Fulkerson metodą bei Edmonds-Karp algoritmą. Aprašyti minimalios kainos srautą (min-cost max-flow). 4.6 Apibrėžti dvidalio grafo poravimo (bipartite matching) algoritmą. Pateikti pritaikymo pavyzdžių. |
| 5. Apibūdinti dinaminį programavimą, taikyti uždaviniams spręsti. | 5.1 Taikyti jau žinomus algoritmus optimizavimo uždaviniams spręsti.
5.2 Sprendžiant uždavinius naudoti dinaminį programavimą. 5.3 Gebėti pasirinkti, kada naudinga taikyti dinaminį programavimą. |
| 6. Apibūdinti stalo žaidimų algoritmus, jų ypatybes. | 6.1 Atpažinti ir tyrinėti strateginių stalo žaidimų algoritmus.
6.2 Prisiminti, kas yra euristinis algoritmas. Atpažinti euristinius pozicijų vertinimo algoritmus. 6.3 Apibūdinti iteratyvaus algoritmo sąvoką. Atpažinti iteratyvių paieškos gilinimo algoritmą. 6.4 Apibūdinti Alfa-Beta atkirtimo algoritmą. 6.5 Apibūdinti MiniMax paiešką. |
| 7. Taikyti skaičių teorijos bei geometrijos principus programavimo uždaviniams spręsti. | 7.1 Apibrėžti sąvokas: pirminiai skaičiai, modulio aritmetika, binominiai koeficientai. Pateikti pavyzdžių. Naudoti juos rašant algoritmus.
7.2 Apibrėžti sąvokas: taškai, vektoriai ir jų sandaugos, tiesės, atkarpos, apskritimai ir jų susikirtimai, daugiakampiai ir jų plotai. Pateikti pavyzdžių, kaip šie geometriniai objektai naudojami algoritmo rašyme. 7.3 Aprašyti mažiausio iškilaus dangalo algoritmą (convex hull). |
Turinio apimtis
1. Objektai. Apibrėžiama objekto sąvoka. Pateikiami pavyzdžiai iš realaus pasaulio. Apibrėžiama metodo sąvoka. Paaiškinamas objekto duomenų pasiekiamumas. Objektų ir jų savybių studijavimas: fiziniai objektai, kompiuterio aplinkos objektai, žmogiški objektai, kompiuteriniai žaidimai. Išsiaiškinama, kaip turimą objektą galima nukopijuoti bei pašalinti. Pateikiami pavyzdžiai.
2. Klasės. Apibrėžiamas klasės duomenų tipas. Pristatomos klasės aprašo dalys. Apibūdinami metodai, darbui su tam tikrų pavyzdžiu pateiktų klasių duomenimis. Išsiaiškinamos kintamųjų savybės private, public, protected. Paaiškinami metodų aprašymo principai. Pateikiami paprasčiausių klasių aprašo pavyzdžiai. Išaiškinami konstruktoriaus ir destruktoriaus metodai, jų paskirtys ir naudojimas, savybės. Pateikiami pavyzdžiai. Apibrėžiamas paveldėjimas. Apibūdinamos paveldėjimo galimybės, priklausančios nuo kintamųjų ir metodų atributų (private, public, protected). Aptariamos bazinės ir išvestinės klasės sąvokos. Išaiškinama, kaip jis naudojamas, pateikiami pavyzdžiai.
2.1. Abstraktus duomenų tipas (ADT). Abstraktaus duomenų tipo, duomenų tipo ar duomenų struktūrų sąvokos. Irankiai algoritmų operacijoms išreikšti. Skaičiavimo resursai įdiegiant algoritmus ir išbandant jų funkcionavimą. Algoritmų sudėtingumo įvertinimai. Operacijos, kurios gali būti vykdomos su šiais duomenų tipais. ADT pavyzdžiai: Integer ADT, Matrica ADT, Bazinės struktūros. Dėklas, eilutė, operacijos su šiais duomenų tipais. Panaudojimo pavyzdžiai.
2.2. Dvejetainis medis. Dvejetainio medžio apibrėžimas. Sąvokos (pilnas, tobulas, užbaigtas dvejetainis medis). Dvejetainio medžio žymėjimas. Dvejetainio medžio tipo realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai.
2.3. Prioritetinė eilė, krūva (heap). Duomenų struktūros heap apibrėžimas. Galimos operacijos su heap struktūra. Šios duomenų struktūros naudojimo privalumai ir trūkumai, aptariamos situacijos, kada šią struktūrą naudoti tikslinga. Aptariami galimi šio duomenų tipo realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai.
2.4. Dėstymo lentelės (hash tables). Dėstymo lentelės duomenų struktūros apibrėžimas. Galimos operacijos su dėstymo lentelės duomenimis. Dėstymo lentelės duomenų struktūros realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai.
2.5. Intervalų medžiai. Intervalų medžio duomenų struktūros apibrėžimas. Galimos operacijos su šio duomenų tipo duomenimis. Intervalų medžio realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai..
2.6. Žodyno medis (trie). Žodyno medžio duomenų struktūros apibrėžimas. Galimos operacijos su šio duomenų tipo duomenimis. Žodyno medžio realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai.
2.7. Dvejetainis indeksuotas medis (binary indexed tree). Dvejetainio indeksuoto medžio duomenų struktūros apibrėžimas. Galimos operacijos su šio duomenų tipo duomenimis. Dvejetainio indeksuoto medžio realizacijos būdai C/C++ kalbomis. Pateikiami pavyzdžiai.
3.1. Stipriai jungus grafas. Grafo sąvoka, Grafo jungumas. Jungumo komponentės. Stipriai jungios komponentės. Ciklas grafe.
3.2. Dijkstros trumpiausio kelio algoritmas . Paieška platyn. Dijkstros trumpiausio kelio algoritmas, jo sudėtingesnė versija. Apsirašyti sudėtingesnę jo versiją. Dijkstros trumpiausio kelio algoritmų sudėtingumas. Realizacijos būdai C/C++ kalbomis.
3.3. Bellman-Ford algoritmas. Bellman-Ford algoritmas, jo sudėtingumo skaičiavimas. Taikymo pavyzdžiai.
3.4. Floyd-Warshal algoritmas. Floyd-Warshal algoritmas, jo sudėtingumo skaičiavimas. Taikymo pavyzdžiai.
3.5. Tinklo srauto (network flow) uždavinys. Tinklo srauto uždavinys. Ford-Fulkerson metodas. Edmonds-Karp algoritmas. Minimalios kainos srautas (min-cost max-flow).
3.6. Dvidalio grafo poravimas. Dvidalio grafo poravimo (bipartite matching) algoritmas. Taikymo pavyzdžiai.
4. Dinaminis programavimas. Dinaminio programavimo apibrėžimas. Optimizavimo uždavinys. Sprendinys ir sprendinio vertė. Godžiojo algoritmo sąvoka. Dinaminio programavimo principai.
5. Stalo žaidimai. Kelių strateginių stalo žaidimų algoritmai. Euristinis pozicijų vertinimas bei iteratyvus paieškos gilinimas. Alfa-Beta atkirtimas. MiniMax paieška.
6.1. Skaičių teorija programavime. Skaičių teorijos pagrindų sąvokos: pirminiai skaičiai, modulio aritmetika, binominiai koeficientai. Su sąvokomis susijusios teoremos. Taikymo pavyzdžiai.
6.2. Geometrija programavime. Geometrijos pagrindų sąvokos: taškai, vektoriai ir jų sandaugos, tiesės, atkarpos, apskritimai ir jų susikirtimai, daugiakampiai ir jų plotai. Taikymo pavyzdžiai. Mažiausio iškilaus dangalo algoritmas (convex hull).
II. Sudėtingų uždavinių sprendimo metodai
Ruošiant mokinius olimpiadoms, sprendžiant sudėtingesnius uždavinius paprastai standartinės mokymo metodikos – bazinės žinios, pavyzdžių nagrinėjimas, užduočių sprendimas – neužtenka. Reikia ugdyti papildomus gebėjimus, tokius, kurie ne tik pagelbėtų rasti tinkamą sprendimą, optimizuoti sprendimo algoritmą, bet ir taupytų sprendimo laiką. Šiame skyriuje dėmesys kreipiamas į tris pagrindinius gebėjimus: 1) uždavinio suvokimą ir formulavimą atmetant perteklinę informaciją taip, kad būtų aišku kas duota ir ką reikia rasti; 2) uždavinio paprastinimą, mažinant jo dimensijas, galimų reikšmių diapazoną; 3) išskaidyti uždavinį į smulkesnes, išsprendžiamas užduotis, o paskui jas tinkamai sujungti taip gaunant pilną uždavinio sprendimą; 4) sprendžiant uždavinius išmokti naudotis vizualinėmis priemonėmis, grafiniais pavaizdavimais, kad nereiktų atmintyje laikyti visos informacijos. Šie gebėjimai, ugdomi specialiai atrinktais ir paruoštais uždaviniais.
Išmokti metodikos, kuri padėtų išspręsti iš pirmo žvilgsnio neišsprendžiamus uždavinius.
| Mokinių įgyjami gebėjimai: | Mokinių įgyjamos žinios ir supratimas |
| 1. Performuluoti uždavinį taip, kad neliktų nereikalingos informacijos. | 1.1 Pastebėti ir atmesti perteklinę informaciją.
1.2 Išgryninti uždavinio idėją, suformuluoti problemą. |
| 2. Sudėtingą uždavinį paprastinti pažingsniui tol, kol gaunamas išsprendžiamas uždavinys. | 2.1 Paprastinti uždavinį mažinant jo dimensiją.
2.2 Paprastinti uždavinį kintamus duomenis pakeičiant konstantomis 2.3 Paprastinti uždavinį sumažinant galimų reikšmių diapazoną. 2.4 Atmesti supaprastintas užduotis, kurios nepadės rasti galutinio uždavinio sprendimo. 2.5 Surūšiuoti gautas supaprastintas užduotis taip, kad uždavinio sprendimas būtų rastas efektyviau. 2.6 Sujungti supaprastintas užduotis taip, kad būtų gautas viso uždavinio sprendimas. |
| 3. Atvaizduoti uždavinį (jo sprendimą) grafiškai. | 3.1 Rasti ir pateikti keletą pradinių duomenų grafinio atvaizdavimo būdų.
3.2 Pasirinkti pakankamą pradinių duomenų kiekį atvaizdavimui, kad nesunkiai būtų galima palyginti su kitu pradinių duomenų rinkiniu. 3.3 Rasti ir pateikti kelis uždavinio sprendimo algoritmo grafinius atvaizdavimus. 3.4 Išrinkti tinkamiausius ir vaizdžiausius grafinius atvaizdavimus, kurie realiai padeda spręsti uždavinį.. |
Turinio apimtis
1. Uždavinio formuluotė. Perteklinės informacijos apibūdinimas. Perteklinės informacijos radimas konkrečiame uždavinyje. Užduoties performulavimas išgryninant uždavinio idėją ir suformuluojant problemą dviems sakiniais: pirmame aprašomi turimi duomenys, antrame suformuluojama užduotis, ką reikia apskaičiuoti iš turimų duomenų. Sprendžiami specialiai šiems įgūdžiams lavinti parinkti uždaviniai.
2. Uždavinio skaidymas į paprastesnes, išsprendžiamas užduotis. Uždavinys paprastinamas mažinant jo dimensiją, kintamus duomenis pakeičiant konstantomis, sumažinant galimų reikšmių diapazoną. Užduotis paprastinamos tol, kol kiekviena iš jį bus išsprendžiama. Aptinkamos ir atmetamos supaprastintos užduotys, kurios nepadės rasti galutinio uždavinio sprendimo. Gautos supaprastintos užduotys surūšiuojamos taip, kad uždavinio sprendimas būtų rastas efektyviau. Surūšiuotos užduotys sujungiamos taip, kad būtų gautas viso uždavinio sprendimas. Taip skaidant uždavinį smulkiomis užduotimis galima gauti net keletą skirtingų uždavinio sprendimo idėjų. Sprendžiami ir analizuojami specialiai šiems įgūdžiams parinkti uždaviniai.
3. Uždavinio grafinis vaizdavimas. Grafinio atvaizdavimo būdai konkretaus uždavinio pradiniams duomenims atvaizduoti. Vaizdingiausio ir labiausiai padedančio uždavinį spręst būto atrinkimas. Uždavinio sprendimo algoritmo grafiniai atvaizdavimai. Vaizdingiausio atvaizdavimo pasirinkimas. Sprendžiami ir analizuojami specialiai šiems įgūdžiams ugdyti parinkti uždaviniai.