9-10 programavimo modulis praplečiamas dviem aspektais. Pirmiausiai siūloma plačiau ir giliau tyrinėti C/C++ programavimo kalbos sintaksę, spręsti sudėtingesnius uždavinius, naudoti sudėtingesnes duomenų struktūras. Neišvengiamai taip paliečiama ir 11-12 kl. programavimo modulio programa, tai reiškia, kad dalis 11-12 kl. programavimo modulio temų turi būti perkelta į 9-10 kl. praplėsto programavimo modulio gairių turinį. Pirmame skyriuje „Programavimo kalba ir jos sintaksė. Uždavinių sprendimas ir sprendimo algoritmo užrašymas“ rasite dalį temų, tik labiau praplėstas ir pagilintas.
Vis tik praplėstame programavimo modulyje pagrindinis dėmesys skiriamas algoritmams bei jų tyrinėjimams, sudėtingumo bei efektyvumo nustatymui. Taip pat įdomiems algoritmavimo uždaviniams, kuriems išspręsti reikia ne tik išmanyti įvairius algoritmus, bet ir rasti įdomių, netradicinių sprendimų. Programavimo kalba ir jos sintaksė mokomasi tik tam, kad ją panaudoti kaip įrankį.
I. Programavimo kalba ir jos sintaksė. Uždavinių sprendimas ir sprendimo algoritmo užrašymas
Gebėjimas išspręsti uždavinį ir užrašyti sprendimą veikiančia programa.
| Mokinių įgyjami gebėjimai: | Mokinių įgyjamos žinios ir supratimas | Ugdymo gairės |
| 1. Atlikti veiksmus su įvairių paprastųjų tipų duomenimis. | 1.1 Užrašyti veiksmus su įvairių paprastųjų tipų duomenimis, naudoti juos programose. | Mokiniui pateikiama paprastųjų duomenų tipų klasifikacija: diskretusis ir realusis. Pristatomi dar nežinomi duomenų tipai, jų galimos reikšmės bei operacijos su jais. |
| 2. Suformuoti įvairius struktūrinius duomenų tipus, atlikti veiksmus su šiais duomenų tipais, naudoti juos savo programoje. | 2.1 Apibūdinti simbolių eilutės sąvoką, aprašyti šio duomenų tipo kintamuosius, atlikti veiksmus su simbolių eilučių kintamųjų reikšmėmis.
2.2 Apibūdinti masyvo sąvoką, gebėti skirti masyvo elemento indeksą ir masyvo elemento reikšmę, aprašyti įvairių paprastųjų duomenų masyvo tipą, naudoti masyvo duomenų tipo kintamuosius, suteikti masyvo elementams reikšmes, atlikti veiksmus su masyvo elementų reikšmėmis. 2.3 Apibūdinti vienmačio be dvimačio masyvo sąvoką, gebėti skirti masyvo elemento indeksus; suteikti masyvo elementams reikšmes, atlikti veiksmus su masyvo elementų reikšmėmis. 2.4 Apibūdinti įrašo (struktūros) sąvoką, nusakyti paskirtį. 2.5 Aprašyti įrašo (struktūros) duomenų tipą, aprašyti šio tipo kintamuosius, suteikti kintamiesiems reikšmes atlikti veiksmus su įrašo (struktūros) tipo kintamųjų reikšmėmis. 2.6 Atlikti veiksmus su įrašo (struktūros) tipo masyvo elementų reikšmėmis. 2.7 Sudaryti duomenų struktūras, panaudoti įrašo (struktūros) ir masyvo duomenų tipus. |
Apibrėžiamas struktūrinis duomenų tipas. Pristatomi paprasčiausi struktūriniai tipai, tokie kaip simbolių eilutė bei vienmatis masyvas. Pateikiamos galimos operacijos su kiekvieno tipo duomenimis. Pademonstruojamas dvimatis masyvas. Parenkama konkretaus duomenų tipo panaudojimo pavyzdžių. tipai palyginami tarpusavyje, palyginamos galimos operacijos su šio tipo duomenimis.Pademonstruojama mokiniui, kaip aprašomas naujas duomenų tipas. Išsiaiškinama kada tai naudinga, kaip panaudoti atskiriems uždaviniams spręsti. Analizuojami pavyzdžiai.Nagrinėjami uždaviniai, kurių duomenims saugoti ir apdoroti patogiausiai naudoti įrašo tipą. Pademonstruojama, kaip aprašomas įrašas, kaip tokio tipo kintamieji gali įgyti reikšmes, aptariama, kaip operuoti su šio tipo kintamaisiais.Daromos naujos struktūros iš struktūrinio tipo duomenų. Nagrinėjami šitokių struktūrų panaudojimo pavyzdžiai. Nagrinėjami gali veiksmai su šių struktūrų atskirais elementais. Tyrinėjamas įvairių tipų suderinamumas bei tapatumas. |
| 3. Paaiškinti algoritmo sampratą, gebėti užrašyti algoritmą struktūrogramomis, pseudokodu. | 3.1 Paaiškinti, kas yra algoritmas, pateikti pavyzdžių.3.2 Paaiškinti, kas yra struktūrogramos, kam jos reikalingos, pateikti pavyzdžių.
3.3 Paaiškinti, kas yra pseudokodas, pateikti pseudo kodo pavyzdžių, paaiškinti, kam jis reikalingas. |
Pademonstruojama mokiniams keletas algoritmo užrašymo būdų: schema, struktūrograma, aptariamos pseudo kodo taisyklės, kad mokinys galėtų uždavinio sprendimą aprašyti keliais lietuviškais sakiniais. |
| 4. Taikyti pagrindinius algoritmų veiksmus ir užrašyti juos programavimo kalbos žymenimis. | 4.1 Parinkti uždaviniui spręsti tinkamas duomenų struktūras ir algoritmus.4.2 Programose naudoti algoritmus: sumos, sandaugos, kiekio, aritmetinio vidurkio skaičiavimo; rikiavimo; didžiausios (mažiausios) reikšmės radimo, paieškos surikiuotame ir nerikiuotame masyve, masyvo papildymo naujomis reikšmėmis, reikšmių pašalinimo iš masyvo.
4.3 Parinktą, modifikuotą ar sudarytą algoritmą užrašyti programavimo kalba. 4.4 Kurti programas įvairiems taikomiesiems uždaviniams spręsti. |
Tyrinėjami sudėtingesni šakojimo algoritmai, ciklai, ciklai cikle.Mokiniui pateikiami uždaviniai, kur reikia skaičiuoti sumą, vidurkį, sandaugą.Pateikiami tiek vienmačio, tiek dvimačio masyvų rikiavimo uždaviniai, aptariami algoritmai.Aptartus uždavinio sprendimo algoritmus mokinys bando užrašyti programavimo kalba. |
| 5. Analizuoti užduotį: įvertinti jos sudėtingumo lygį, skaidyti į dalis, nustatyti ryšius tarp šių dalių, parengti sprendimo eskizą (schemą). | 5.1 Analizuoti užduotį, skaidyti ją į struktūrines dalis.5.2 Apibūdinti užduoties skaidymo dalimis pranašumus.
5.3 Aprašyti sprendimą kuriuo nors formaliu būdu (schemomis, programavimo kalbos žymenimis). 5.4 Parinkti sprendžiamam uždaviniui tinkamas duomenų struktūras, sprendimo metodus ir algoritmus. |
Mokiniui pateikiami vis sudėtingesni uždaviniai, kuriuos galima išskaidyti į jau pažįstamus spręstus uždavinius.Mokinys bando spręsti uždavinį analizuodamas jį ir aprašydamas sprendimą lietuviškais sakiniais.Mokiniui pateikiami uždaviniai, kurių duomenims įsiminti reikalingos įvairios duomenų struktūros, aiškinamasi kada kokiu pavidalu įsiminti duomenis yra patogiausia. |
| 6. Aprašyti veiksmus funkcijomis, taikyti jas sudarant programas. | 6.1 Paaiškinti funkcijos sąvoką, paskirtį.6.2 Išskirti uždavinio dalis, kurias galima užrašyti funkcijomis.
6.3 Apibūdinti parametrus, naudoti juos rašant funkcijas. 6.4 Rašant programas naudoti funkcijas. 6.5 Nusakyti programos, funkcijų vardų, parametrų ir kintamųjų galiojimo sritis. 6.6 Paaiškinti funkcijų parametrų ir kreipinių argumentų ryšį. |
Aiškinama, kad kai kuriuos uždavinius sprendžiant galima juos suskaidyti į mažesnius uždavinius ir skaičiavimus, kuriems būtų galima aprašyti funkcijas. Funkcijos, kurios negrąžina rezultato(void). Aptariama funkcijos sintaksė.Išaiškinti funkcijų parametrų reikšmę, jų vartojimo tikslingumą.Išbandyti rašyti funkcijas atitinkamiems uždaviniams spręsti. |
| 7. Įvaldyti programavimo technologijos (metodikos) elementus | 7.1 Įvardyti programos sudarymo etapus, laikytis jų rašant programas.7.2 Parengti kontrolinius duomenis programos darbo teisingumui patikrinti.
7.3 Skirti programos darbo patikrinimą ir programos testavimą. 7.4 Komentuoti programos dalis |
Mokiniai raginami laikytis programos sudarymo etapų, paaiškinti šių etapų privalumus.Aptariama kartu su mokiniu kas yra kontroliniai duomenys ir kaip juos tinkamai parinkti.Aptariamos programos komentavimo galimybės ir poreikis. |
Turinio apimtis
1. Paprastieji duomenų tipai. Išsiaiškinama, kad yra diskretieji ir tolydieji duomenys. Susipažįstama su tokio tipo duomenimis, galimų reikšmių rėžiais, galimomis operacijomis. Paminimi bent keli sveikojo bei realiojo duomenų tipai, supažindinama su simboliniu, loginiu tipais.
2. Simbolių eilutės. Apibrėžiamos simbolių eilutės duomenų tipo sąvokos. Paaiškinama, kaip aprašomi eilutės duomenų tipo kintamieji, kokios galimos reikšmės. Apibrėžiamos galimos operacijos su šiuo duomenų tipu. Mokoma atlikti veiksmus su simbolių eilutėmis: įvesti, išvesti, palyginti, sujungti.
3. Vienmačiai ir dvimačiai masyvai. Paaiškinamos masyvo, masyvo elemento indekso ir reikšmės sąvokos. Mokoma aprašyti masyvo duomenų tipą, jį naudoti kuriant masyvo tipo kintamuosius. Mokoma priskirti reikšmes masyvo elementams, įrašyti duomenis į masyvą bei juos išvesti, atlikti veiksmus su masyvo reikšmėmis. Pristatomas lentelės duomenų tipas – dvimatis masyvas. Išsiaiškinama, kaip naudoti dvimačio masyvo duomenis, kaip suteikti reikšmes ir kaip jas panaudoti. Mokiniai skatinami taikyti žinomus algoritmus atliekant veiksmus su simbolių eilučių tipo masyvo elementų reikšmėmis.
4. Įrašai (struktūros). Paaiškinama įrašo (struktūros) prasmė ir taikymas. Mokoma sukurti įrašo (struktūros) duomenų tipą ir jį aprašyti. Mokoma sukurti masyvo tipą su įrašo (struktūros) elementais, aprašyti įrašo (masyvo) tipo kintamuosius, masyvus su įrašo tipo reikšmėmis, atlikti veiksmus su įrašo tipo duomenimis. Paaiškinama, kaip įrašo (struktūros) tipo kintamieji perduodami procedūros (funkcijos) parametrais. Mokoma, kaip įraše (struktūroje) panaudoti jau sukurtus kitus įrašus (struktūras) bei masyvus. Mokiniai skatinami taikyti žinomus ir kurti nesudėtingus algoritmus darbui su įrašo (masyvo) elementų reikšmėmis.
5. Algoritmas, algoritmo užrašymas struktūrogramomis, pseudokodu. Primenamas algoritmo apibrėžimas, nagrinėjamos jo savybės, stengiamasi išsiaiškinti, kas yra geras algoritmas. Mokiniai skatinami algoritmus pirmiausiai užrašyti iš anksto aptartu pseudokodu – kad ir lietuviškais sakiniais – suvokti tokio užrašymo prasmę. Taip pat pademonstruojamos struktūrogramos ir kitokie grafiniai algoritmo užrašymo būdai.
6. Pagrindiniai algoritmų veiksmai ir jų užrašymas programavimo kalbos žymenimis. Primenami sumos, sandaugos, kiekio, aritmetinio vidurkio skaičiavimo, didžiausios (mažiausios) reikšmės paieškos algoritmai. Supažindinama su rikiavimo, paieškos surikiuotame ir nerikiuotame masyve, masyvo reikšmių šalinimo iš masyvo, masyvo papildymo naujomis reikšmėmis algoritmais. Mokoma užrašyti loginius reiškinius ir juos panaudoti masyvo rikiavimo, paieškos, reikšmių šalinimo ir papildymo veiksmuose, kai duomenų tipas yra masyvas ir / ar įrašas (struktūra). Mokoma užrašyti algoritmus programavimo kalbos žymenimis ir taikyti darbui su duomenimis, saugomais skirtingo tipo duomenų kintamuosiuose.
7. Procedūros bei funkcijos. Apibūdinama funkcijų ir/ar procedūrų paskirtis programoje. Paaiškinama, kaip jos aprašomos. Mokoma tinkamai užrašyti struktūrą, parametrus. Paaiškinama, kaip užrašomas kreipinys, kaip duomenys perduodami funkcijai ir/ar procedūrai, kaip grąžinami skaičiavimo rezultatai. Mokoma apibrėžti vardų galiojimo sritis. Mokoma užrašyti šias konstrukcijas programavimo kalbos žymenimis. Mokiniai skatinami skaidyti programą dalimis, kurios apiforminamos funkcijomis ir/ar procedūromis.
8. Programavimo technologija. Pabrėžiami programos sudarymo etapai: rašymas, derinimas, patikrinimas, testavimas, tobulinimas. Mokiniai skatinami sudarant programas laikytis šių etapų. Paaiškinama kontrolinių duomenų sąvoka ir svarba programos teisingumui užtikrinti. Mokytojas atkreipia dėmesį į programos stilių ir kalbos kultūrą. Nagrinėjami konkretūs pačių mokinių sudarytų programų pavyzdžiai. Mokytojas paaiškina, kur ir kokius komentarus rašyti, kaip geriau išdėstyti vieną ar kitą sakinį, kokius vardus geriau parinkti programoje, ir pan. Mokiniai mokomi rašyti programas tvarkingai, skatinami laikytis programavimo kultūros.
II. Algoritmo tyrinėjimai
Gebėjimas skaityti algoritmą, įvertinti jo teisingumą, sudėtingumą, efektyvumą.
| Mokinių įgyjami gebėjimai: | Mokinių įgyjamos žinios ir supratimas | Ugdymo gairės |
| 1. Paaiškinti algoritmo teisingumo, sudėtingumo sąvokas. | 1.1 Paaiškinti algoritmo idėjos ir realizacijos teisingumą, pateikti pavyzdžių.1.2 Paaiškinti algoritmo sudėtingumo sąvoką.
1.3 Sugebėti įvertinti algoritmo sudėtingumą laiko atžvilgiu. 1.4 Sugebėti įvertinti algoritmo sudėtingumą atminties atžvilgiu. |
Išsiaiškinama, pagal kokius kriterijus galima tyrinėti algoritmą. Apibrėžiamos algoritmo teisingumo, sudėtingumo sąvokos. Tyrinėjamas algoritmo sudėtingumas laiko bei atminties atžvilgiu. |
| 2. Matematiškai apskaičiuoti algoritmo sudėtingumą laiko atžvilgiu (O didžiosios žymėjimas) | 2.1 Funkcija aprašyti algoritmo sudėtingumą laiko ir atminties atžvilgiu taikant O didžiosios žymėjimą.2.2 .
2.3 Nustatyti blogiausius atvejus algoritmo skaičiavime. 2.4 Atpažinti polinominio sudėtingumo algoritmus. 2.5 Atpažinti NP (nondeterministic polynomial) sudėtingumo klasės algoritmus, paaiškinti NP pilnumo sąvoką. 2.6 Atpažinti efektyvius algoritmus bei įrodyti jų efektyvumą. 2.7 Paaiškinti, kas tai yra euristiniai algoritmai (euristikos), juos atpažinti.. |
Pradžioje mokiniai tyrinėja rikiavimo algoritmus. Aiškinasi, kurie iš jų sudėtingesni, kurie paprastesni, kurie efektyvesni, kurie visai neefektyvūs.Bandoma apskaičiuoti bent keleto algoritmų sudėtingumą, taikant O didžiosios funkciją. Palyginami rezultatai.Nagrinėjami NP pilnų uždavinio pavyzdžiai. Analizuojama kiek laiko užimtų tokių uždavinių tikslus išsprendimas didėjant duomenų kiekiui, kokia įtaką tokių uždavinių sprendimui turi spartėjantys kompiuteriai. |
| 3. Paaiškinti ir užrašyti Euklido algoritmą bendram didžiausiam dalikliui rasti. | 3.1 Užrašyti algoritmą skaičių bendram didžiausiam dalikliui bei mažiausiam kartotiniui rasti.3.2 BDD algoritmą pritaikyti pirminiam skaičiui rasti.
3.3 Paaiškinti Eratosteno rėčio algoritmą. 3.4 Paaiškinti Merseno pirminių skaičių sąvoką. |
Mokiniai prisimena kaip randamas skaičiaus bendras didžiausias daliklis. Aptaria algoritmą ir parašo jį programavimo kalbos žymenimis.Patikrina algoritmo teisingumą, nustato sudėtingumą laiko bei atminties atžvilgiu. Bando sumažinti sudėtingumąNagrinėjami pirminių skaičių uždaviniai. |
| 4. Skaityti ir užrašyti rekursinį algoritmą. | 4.1 Apibūdinti rekursyvų algoritmą, pateikti pavyzdžių iš įvairių sričių.4.2 Užrašyti rekursyvią funkciją.
4.3 Panaudoti rekursyvius algoritmus uždaviniams spręsti. 4.4 Tinkamai ir laiku nutraukti rekursinį algoritmą. |
Mokiniui pateikiami rekursyvumo pavyzdžiai gamtoje, mene ir pan. Išsiaiškinama, koks yra rekursinis algoritmas.Pabandoma aprašyti algoritmus konkretiems uždaviniams, tokiems kaip faktorialas, Fibonačio skaičiaus radimas, Hanojaus bokštai, išsiaiškinama, kad šiuos uždavinius patogiau / įmanoma spręsti tik naudojant rekursinius algoritmus. |
| 5. Skaityti bei užrašyti perrinkimo algoritmus, taikyti grįžimo metodą. | 5.1 Atpažinti bei užrašyti perrikiavimo algoritmą, pateikia pavyzdžių.5.2 Apibūdinti grįžimo atgal metodo idėją, pateikti pavyzdžių.
5.3 Apskaičiuoti perrinkimo algoritmo sudėtingumą, apibūdina galimus optimizavimus. |
Mokiniui kelių skirtingų uždavinių pavyzdžiais (žemėlapio spalvinimo uždavinys) pademonstruojamas perrikiavimo metodas. Užrašomi perrikiavimo algoritmai, apskaičiuojamas jų efektyvumas.Kelių skirtingų uždavinių pavyzdžiais (keliaujančio pirklio uždavinys) išsiaiškinamas grįžimo atgal metodas. Užrašomi grįžimo atgal algoritmai, apskaičiuojamas jų efektyvumas. |
| 6. Apibūdinti grafus, taikyti juos uždaviniams spręsti. | 6.1 Apibūdinti grafo ir su juo susijusias sąvokas: viršūnė, briaunos, gretimos briaunos, kaimynės, kilpa, kelias, tiltas, ciklas grafe, grafo viršūnių laipsnis ir pan.; pateikia pavyzdžių.6.2 Braižyti grafą pagal pateiktą užduotį.
6.3 Apibūdinti grafo jungumą: jungus grafas, nejungus grafas, jungumo komponentai; pateikti pavyzdžių. 6.4 Suformuluoti Oilerio teoremą, pritaikyti ją uždaviniams spręsti. 6.5 Skirti ir tikslingai naudoti orientuotuosius bei svorinius grafus. 6.6 Kurti algoritmus trumpiausio kelio paieškai grafe. 6.7 Apibūdinti medžio sąvoką, medžio savybes, pateikti pavyzdžių. 6.8 Apibūdinti grafo pografį, pateikti pavyzdžių. 6.9 Apibūdinti minimalų jungiamąjį medį grafe, pateikti pavyzdžių. |
Mokiniui pristatomas Karaliaučiaus tiltų uždavinys. Tyrinėjant jį išsiaiškinamos grafo ir su juo susijusios sąvokos. Braižomas grafas, užrašomas sprendimo algoritmas.Mokiniui apibrėžiama Oilerio kelio/ciklo sąvoka, pateikiama pavyzdžių. Suformuluojama Oilerio teorema, tyrinėjamas įrodymas. Pateikiami pavyzdiniai uždaviniai, tokie, kaip keliaujančio pirklio uždavinys. Kartu tyrinėjamas Flerio algoritmas bei Dijkstros algoritmas.Tyrinėjami paieškos gilyn platyn algoritmai, jų sudėtingumas, pavyzdžiai.Tyrinėjami uždaviniai, kuriems spręsti reikia pasitelkti medžio sąvoką. Pateikiami minimalus jungiamojo medžio (MJM) paieškos uždaviniai bei sprendimui naudojamas Kruskalo algoritmas. |
Turinio apimtis
1. Algoritmas. Algoritmo bei algoritmo sudėtingumo sąvokos. Algoritmo sąvokos atsiradimas. Algoritmo teisingumas ir efektyvumas. Euristiniai algoritmai, jų sąvokos atsiradimas. Euristinių algoritmų naudojimas. Algoritmo sudėtingumas laiko ir atminties atžvilgiu.
2. Algoritmo sudėtingumo funkcija. Algoritmo sudėtingumo įvertinimas. Atliekamų veiksmų skaičiavimas blogiausiam atvejui. Algoritmo sudėtingumo apibrėžimas ir skaičiavimo funkcija. Didžiosios O žymėjimas. Algoritmo sudėtingumo skaičiavimų realus panaudojimas uždaviniams spręsti. Polinominio sudėtingumo algoritmai. NP (nondeterministic polynomial time) sudėtingumo klasės uždaviniai.
3. Euklido algoritmas. Algoritmas didžiausiam bendrajam dalikliui bei mažiausiam bendrajam kartotiniui rasti. Euklido algoritmo taikymas įvairiems uždaviniams spręsti. Pirminių skaičių paieškos, radimo algoritmai. Eratosteno rėtis.
4. Rekursija. Rekursijos apibrėžimas. Fraktalo sąvoka. Rekursyvios funkcijos. Hanojaus bokštų uždavinys. Rekursijos užbaigimas.
5. Perrinkimas ir grįžimo metodas. Perrinkimo metodo sąvoka. Grįžimo metodo sąvoka. Metodų taikymas konkretiems uždaviniams spręsti. Perrinkimo algoritmo optimizavimas. Rikiavimo algoritmai: rikiavimas įterpimu, greitas rikiavimas, rikiavimas skaičiavimu. Paieškos algoritmai: tiesinė paieška, dvejetainė paieška. Rikiavimo ir paieškos algoritmų taikymas uždaviniams spręsti.
6. Grafas. Grafo sąvoka. Grafo viršūnės ir briaunos. Gretimos ir kaimyninės viršūnės. Kilpa grafe. Kelias grafe. Tiltas grafe. Ciklas grafe. Grafų vaizdavimas. Tankus ir retas grafas. Jungus ir nejungus grafas. Jungumo komponentai. Garfo viršūnės laipsnis. Trumpiausio kelio grafe radimas. Paieška gilyn. Paieška platyn. Oilerio kelias ir ciklas. Flerio algoritmas. Hamiltono kelias ir ciklas. Orientuotieji grafai: išėjimo laipsnis, įėjimo laipsnis. Vienakryptiškai jungus grafas. Silpnai ar stipriai jungus grafas. Topologinis rikiavimas. Svoriniai grafai. Trumpiausio kelio paieška. Dijkstros algoritmas.
7. Medis. Medžio sąvoka. Medžio savybės. Medžio šaknis, šakninis medis. Medžio vaizdavimas. Minimalus jungiamasis medis. Algoritmai minimaliam jungiamajam medžiui rasti. Primo algoritmas. Boruvkos algoritmas. Kruskalo algoritmas.