Përgatitja e studentëve për Olimpiadën e Informatikës. Programi i përgatitjes individuale për fazën komunale të Olimpiadës Gjith-Ruse për nxënësit e shkollës në lëndën "Informatikë dhe Plani TIK për përgatitjen për Olimpiadën në Informatikë"

02.07.2020 Windows 8

Analiza e problemeve me karakter olimpiadë.

Metodat e përgatitjes për fazën rajonale të Olimpiadës Gjith-Ruse për nxënësit e shkollave në informatikë.

Materialet e klasës master (prezantim)

në RMO mësues të shkencave kompjuterike.

mësuesit e shkencave kompjuterike dhe TIK-ut

MM "Liceumi №23"

Shuvalova Svetlana Yurievna.

Ky punim përmbledh materialet e paraqitura nga unë në RMS të Mësuesve të Informatikës në 2011, 2012 pas rezultateve të fazave shkollore të Olimpiadës Gjith-Ruse për Nxënësit në Informatikë.

Numri i pjesëmarrësve në Olimpiadën për nxënës të shkollave në programim po zvogëlohet çdo vit, kjo për shkak të uljes së pjesës së orëve në linjën e përmbajtjes "Algoritmizim dhe programim" në kurrikulën e lëndës shkollore të shkencave kompjuterike. Olimpiadat janë krijuar për të identifikuar nxënësit më të talentuar në fushën e shkencave kompjuterike, për të zhvilluar aftësitë e tyre dhe për të rritur interesin për këtë temë. Ato u mundësojnë nxënësve të marrin udhëzime të hershme në karrierë, gjë që kontribuon në formimin e ardhshëm të specialistëve rusë në fushën e shkencës kompjuterike, teknologjisë kompjuterike dhe programimit. Por njohja e mirë e kursit shkollor të informatikës nuk garanton performancë të suksesshme në olimpiada, është e nevojshme të merreni me studentët pas orarit të mësimit.

rrëshqitje 1.

Qëllimi i Olimpiadës në Informatikë ështënxisin kërkimin e studentëve më të talentuar.

Një tipar i rëndësishëm i detyrave të përdorura gjatë fazës shkollore dhe komunale është orientimi i tyre për të testuar zhvillimin e të menduarit teorik, logjikën, si dhe kreativitetin dhe intuitën e nxënësve.

Detyrat e fazës shkollore të Olimpiadës duhet të jenë të një kompleksiteti të tillë që të mos trembin studentët, por t'u japin atyre mundësinë për të demonstruar cilësitë e tyre më të mira.

Rrëshqitja 2.

Kriteret kryesore për zgjedhjen e problemeve të Olimpiadës për fazat shkollore dhe komunale të Olimpiadës Gjith-Ruse për Nxënësit në Informatikë:

formulimi origjinal i problemit (ose ideja e zgjidhjes së tij);
në tekstin e kushteve të detyrës nuk duhet të ketë terma dhe koncepte që shkojnë përtej lëndëve të studiuara në kuadrin e kurrikulës bazë;
detyra duhet të përcaktohet pa mëdyshje;
detyra nuk duhet të kërkojë njohuri të veçanta për zgjidhjen e saj;
formulimi i problemit duhet të nënkuptojë praninë e një faze formalizimi në zgjidhjen e tij;
Detyra duhet të jetë me kompleksitet dhe intensitet të arsyeshëm pune.

Rrëshqitja 3.

Detyrat olimpike për fazat shkollore dhe komunale të Olimpiadës në Informatikë dallohen nga diversiteti tematik.

Nga përvoja e olimpiadave, është e mundur të veçohen më të zakonshmetseksionet e shkencave kompjuterike,të cilave mund t'i atribuohet lënda e detyrave:

kombinatorika;
renditja dhe kërkimi;
përpunimi i sekuencës;
algoritme grafike;
elementet e gjeometrisë llogaritëse.
numërimi i opsioneve dhe metodave për zvogëlimin e tij;
programim dinamik.

rrëshqitje 4.

Fazat e zgjidhjes së problemeve të Olimpiadës:

Analiza e kushteve të problemit.
Formalizimi i gjendjes së problemit.
Zhvillimi i një algoritmi për zgjidhjen e problemit.
Zbatimi i softuerit të algoritmit.
Korrigjimi dhe testimi i programit.
Dorëzimi i një zgjidhjeje për shqyrtim.

Rrëshqitja 5.

Është e rëndësishme të theksohet seteksti i detyrës duhet lexuar gjithmonë me kujdesnga fillimi në fund, pasi kushti kryesor mund të fshihet, për shembull, në formatin e të dhënave hyrëse ose dalëse, si dhe në shembujt e skedarëve të të dhënave hyrëse dhe dalëse.

Gjatë zhvillimit të një programi, vëmendje e veçantë duhet t'i kushtohet edhe përshkrimitformati i të dhënave hyrëse dhe dalësedhënë në gjendjen e problemit. Emrat e skedarëve hyrës dhe dalës përshkruhen gjithashtu në deklaratën e problemit, dhe drejtshkrimi i gabuar i tyre në program konsiderohet si gabim.

Duhet mbajtur mend kur shkruani një program qëduke ruajtur skedarët e redaktuar gjatë turneut.

Programi që rezulton duhet të përputhet me atë të dhënëdimensionet e të dhënave hyrësedhe plotësoni kufizimet nëmemoria dhe koha e funksionimitspecifikuar në gjendjen e problemit.

rrëshqitje 6.

Gabimet e zakonshme:

Formati i hyrjes/daljes së të dhënave nuk përputhet me kushtin e detyrës

Nuk merren parasysh të gjitha rastet e mundshme

Lloji i pavlefshëm i të dhënave (dimensioni)

Humbja e skedarëve të redaktuar gjatë turneut

Rrëshqitja 7.

Baza minimale e njohurive për Olimpiadën në Informatikë.

Gjuha e programimit:

strukturat bazë algoritmike,
funksionet standarde të matematikës,
procedurat dhe funksionet për trajtimin e variablave të vargut,
procedurat dhe funksionet për punën me vargje.

Algoritme tipike.

rrëshqitje 8.

Detyrat në Olimpiadat në Informatikë nuk korrespondojnë gjithmonë me "Standardin e Arsimit të Përgjithshëm Bazë dhe të Mesëm (të plotë) në Informatikë dhe TIK". Për më tepër, si zgjidhje për këto probleme në Olimpiadë, kërkohet që të paraqiten programe të debuguara të shkruara në një gjuhë programimi të nivelit të lartë, dhe jo përshkrime të algoritmeve.

Prandaj, sipas rezultateve të olimpiadave, nuk është e saktë të vlerësohet puna e një mësuesi të caktuar të shkencave kompjuterike, pasi programi i një kursi shkollor në shkencën kompjuterike nuk mund të mbulojë të gjitha temat, studimi i të cilave mund të përmirësojë rezultatet e performanca e nxënësve të shkollës në olimpiada.

rrëshqitje 9.

Burimet e internetit për përgatitjen për Olimpiadat në Informatikë:

http://algolist.manual.ru/

Analiza e problemeve të raundit shkollor të Olimpiadës 2011.

Detyra nr. 1 "Regjistrimi i muzikës" (15 pikë)

Kontrolloni nëse një kompozim muzikor që zgjat m minuta dhe n sekonda do të përshtatet në diskun e kompjuterit, nëse hapësira e lirë e diskut është 6 megabajt dhe nevojiten 16 kilobajt për të regjistruar një sekondë zëri.

Algoritmi i zgjidhjes:

Përdorimi i Formulës së Llogaritjes dhe Operatorit të Kushtëzuar

Detyra numër 2 "Bllokimi i sigurt i kombinuar"(20 pikë)

Nga 10 shkronja, duhet të thirrni 3. Përsëritja e shkronjave është e pranueshme. Numëroni numrin e kombinimeve të mundshme të kodeve.

Algoritmi i zgjidhjes:

Problemi i kombinatorikës. Për ta zgjidhur atë, është e nevojshme të zbatohet një algoritëm tipik për formimin e grupeve të vendosjes me përsëritje. Përdoren sythe të mbivendosur.

Detyra numër 3 "Drejtkëndësh"(30 pikë)

Në aeroplan ka N drejtkëndësha. Çdo drejtkëndësh jepet nga koordinatat e kulmeve të majta të poshtme dhe të sipërme djathtas. Përcaktoni nëse drejtkëndëshat kanë një zonë të përbashkët

Algoritmi i zgjidhjes:

Nëse koordinata maksimale X e kulmeve të poshtme majtas të drejtkëndëshave është më e vogël se koordinata minimale e kulmeve të sipërme djathtas dhe koordinata maksimale Y e kulmeve të poshtme majtas të drejtkëndëshave është më e vogël se koordinata minimale e kulmeve të sipërme djathtas , atëherë sipërfaqja totale është.

Përdoret një algoritëm tipik për gjetjen e elementit të grupit maksimal (minimal).

Detyra numër 4 "Sheshi Magjik"(35 pikë)

Në një katror me qeliza 3x3, vendosni numrat 1, 2, ..., 9 në mënyrë që shumat e numrave në çdo rresht, kolonë, në secilën diagonale të jenë të barabarta.

Algoritmi i zgjidhjes.Problemi është se si të mbushni një grup dy-dimensional.

(mënyrë indiane):

Në mes të vijës së sipërme vendosim 1 , në rreshtin e fundit të kolonës ngjitur në të djathtë 2 .
Numrat e ardhshëm vendosen në drejtimin diagonal.
Pasi kanë arritur skajin e djathtë të sheshit, ata lëvizin në qelizën më të majtë të vijës më të afërt mbivendosje.
Pasi kanë arritur skajin e sipërm të sheshit, ata shkojnë në qelizën më të ulët të kolonës ngjitur në të djathtë. Shënim. Pasi të keni arritur në qelizën e këndit të sipërm të djathtë, shkoni në pjesën e poshtme të majtë.
Pasi kanë arritur në një qeli tashmë të zënë, ata kalojnë në qelinë e shtrirë direkt nën qelizën e fundit të mbushur.
Nëse qeliza e fundit e përfunduar është në rreshtin e poshtëm të katrorit, shkoni në qelizën më të lartë në të njëjtën kolonë.

Analiza e problemeve të raundit shkollor të Olimpiadës 2012.

Detyra 1.

Shtypni të gjithë numrat dhjetorë treshifrorë, shuma e shifrave të të cilëve është e barabartë me numrin e dhënë.

Algoritmi i zgjidhjes:

Një nga zgjidhjet e forcës brutale:

var a,b,c,n,k:numër i plotë;

fillojnë

shkruani ("n="); readln(n);

për një:=1 deri në 9 do

Për b:=0 deri në 9 bëni

Për c:=0 deri në 9 bëni

Nëse a+b+c=n atëherë

fillojnë

shkrimln(a,b,c," ");

k:=k+1;

fundi;

Shkruar;

WriteIn("k=",k) ;

Shkruar;

fund.

Zgjidhja e dytë e forcës brutale:

Var a,b,c,n,k,m: numër i plotë;

fillojnë

shkruani ("n="); readln(n);

për m:=100 deri në 999 do

fillojnë

c:=m mod 10;

b:= m div 10 mod 10;

a:= mdiv 100;

nëse a+b+c=n atëherë

fillojnë

shkruani(m:5);

k:=k+1;

fundi;

writeln("k=",k)

fund.

Detyra 2. "Kid dhe Carlson".

Fëmija dhe Carlson jetojnë në një dhomë drejtkëndëshe të madhësisë A x B . Si mund të llogarisin sa qilima katrorë me një anë NGA për të mbuluar plotësisht dyshemenë e një dhome? (Kid dhe Carlson nuk mund të pjestojnë e as të shumëzojnë.) Shkruani një program për të zgjidhur këtë problem.

Algoritmi i zgjidhjes:

Në lakin e jashtëm në njërën anë të dhomës (ndërsa p ) rezervo hapësirë për serinë ( p:=p+s ), pastaj në lakin e brendshëm në anën tjetër (ndërsa m ) kontrollojmë se sa qilima mund të mbyllin rreshtin, operatori m:=m+s rezervon hapësirë për tapetin dhe operatorin kovrik:=kovrik+1 numëron numrin total të dyshekëve të shtruar.

var a, b, c, kovrik, m, p: numër i plotë;

fillojnë

readln(a, b, c);

kovrik:= 0;

p:= 0;

ndërsa p

fillojnë

p:= p + c;

m:= 0;

ndërsa m

fillojnë

m:= m + c;

kovrik:= kovrik + 1

fundi;

shkrim (kovrik)

fund.

Detyra 3. “Bakteret”.

Kolonia përbëhej nga n bakteret (jo më shumë se 30,000). Në të hyri një virus, i cili në minutën e parë shkatërroi një bakter dhe më pas u nda në dy viruse të rinj. Në të njëjtën kohë, secila nga bakteret e mbetura gjithashtu ndahet në dy të reja. Në minutën tjetër, dolën dy viruse që shkatërruan dy baktere, dhe më pas të gjitha viruset dhe bakteret u ndanë përsëri, e kështu me radhë. A do të jetojë kjo koloni pafundësisht apo do të shuhet?

Programi juaj duhet:

Kërkoni numërimin e baktereve n
Zbuloni dhe raportoni: pas sa ditësh, orësh dhe minutash kolonia e baktereve do të pushojë së ekzistuari ose do të lëshojë një mesazh se kolonia është e përjetshme.

Shembull përgjigjeje: Për n=A. Përgjigja është B ditë C orë D minuta (ku A, B, C, D janë vlera numerike).

Algoritmi i zgjidhjes:

Programoni në gjuhën e programimit Pascal.

Var a, b, c: shkurtore;

t, n, v: longint;

fillojnë

Write('Madhësia e kolonisë fillestare -"); readln(n);

v:=1;

ndërsa n>0 bëj

Filloni

t:= t + 1; (minuta)

n:= (n - v) * 2; (bakteret)

v:= v * 2; (viruset)

fundi;

a:=tdiv 1440;

b:= (t - a * 1440) div 60;

c:= t - a - b;

Shkruani ("Kolonia do të pushojë së ekzistuari në ",a, "ditë", b, "orë", c, "minuta");

fund.

Detyra 4.

Jepet një drejtkëndësh me brinjë A dhe B, ku A, B janë numra natyrorë. Ne fillojmë të presim katrorë prej saj (Fig. 1). Sa katrorë të tillë mund të priten nëse katrori më i madh pritet çdo herë?

Algoritmi i zgjidhjes:

1 mënyrë.

Për të zgjidhur këtë problem, na duhen funksione MAX dhe MIN , ne përdorim nënprograme-funksione për t'i përcaktuar ato.

Le të prezantojmë:

variabla ndihmëse X dhe Y (Y>=X) , që korrespondon me brinjët në rënie të drejtkëndëshit;
variabël ndihmëse D , i cili përcakton zvogëlimin e madhësisë së drejtkëndëshit pas prerjes së radhës të katrorit më të madh, brinja e të cilit është si X:=MIN(D,X).

Ne organizojmë një cikël në të cilin ana Y zvogëlohet çdo herë MIN(D, X) derisa të mbetet katrori i fundit, ose Y nuk do të bëhet më e vogël x. Në rastin e fundit, riemërtoni anët e drejtkëndëshit të mbetur si Y:=MAX(D,X) dhe X:=MIN(D,X) dhe vazhdoni ciklin.

Programoni në gjuhën e programimit Pascal.

var a, b, d, k, x, y: numër i plotë;

funksioni min(i, j: numër i plotë): numër i plotë;

fillojnë

nese une

min:=j

fundi;

funksioni max(i, j: numër i plotë): numër i plotë;

fillojnë

nese une

tjetër max:=i

fundi;

fillojnë

përsëritni

Writeln ("vvedite dva naturalnix chisla");

readln(a,b);

deri në (a>0) dhe (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

ndërsa x y bëjnë

fillojnë

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

fundi;

Writeln("iskomoe chislo kvadratov:", k)

fund.

2 mënyra.

Problemi mund të zgjidhet duke përdorur funksione standarde PASCAL: Y DIV X dhe Y MOD X, duke përdorur algoritmin e Euklidit.

Algoritmi i zgjidhjes:

Ne organizojmë një cikël në të cilin formojmë mbetjet nga ndarja r 0 , r 1 , r 2 ,..., r n , r n+1 derisa njëra nga këto mbetje të jetë e barabartë me zero rn+i =0 . Kështu, ne ndërtojmë një funksion për të gjeneruar pjesën e mbetur të ndarjes r n+i = r n mod r n-i , ku r 0 = A dhe r i =B . Për të njëjtin sistem mbetjesh, mund të numërojmë sa herë pjesa e mbetur përshtatet në mënyrë të përsosur r n-i në r n .

(Algoritmi i Euklidit)

var A, B, R0, R, R1, K: numër i plotë;

fillojnë

përsëritni

Shkruani ("FUT NUMRIN NATYROR A = ");

readln (A);

Shkruani ("FUT NJË NUMRI NATYROR NË

readln(B);

deri në (B > 0) dhe (A > 0) dhe (A >= B);

R0:= A;

R1:= B;

K:= R0 div R1;

ndërsa R0 mod R1 0 bëjnë

fillojnë

R:= R0 mod R1;

R0:=R1;

R1:=R;

K:= K + R0 div R1

fundi;

Shkruani ("NUMRI I DËSHIRË TË KATRIT K = ", K);

Një shkrim nga mësuesja e Liceut nr.8 të OEIT Pangina N.N. nga revista "Mjetet Kompjuterike në Arsim", N1, 2000

Përgatitja e nxënësve për olimpiada në Informatikë.

Olimpiadat në Informatikë janë në thelb olimpiada programuese. Zgjidhja e problemeve të Olimpiadës është një seksion arsimor plotësisht i pavarur me pjesë të gjera teorike dhe praktike.

Për gjashtë vjet në bazë të shkollës-liceut nr. 8 në Sosnovy Bor, nxënësit e shkollës janë përgatitur për olimpiada në nivele të ndryshme. Për pesë vjet, studentët e liceut kanë qenë fitues të garave rajonale të programimit, pjesëmarrës dhe fitues të çmimeve të Olimpiadave Gjith-Ruse.

Zgjidhjet e problemeve të olimpiadave të pothuajse të gjitha fazave të olimpiadave, nga niveli rajonal në atë ndërkombëtar, bazohen në algoritme të mirëpërcaktuara, të njohura gjerësisht në matematikë dhe shkenca kompjuterike. Dhe për të zgjidhur me sukses problemet e Olimpiadës, para së gjithash duhet t'i zotëroni këto algoritme, t'i shihni dhe t'i zbatoni me mjeshtëri në detyrat e propozuara, dhe nëse nuk e dini, atëherë të jeni në gjendje t'i mendoni, t'i shpikni ato. Por njohja me këto algoritme më së shpeshti ndodh vetëm në një universitet, dhe kjo është mjaft e kuptueshme, pasi zhvillimi i këtyre algoritmeve kërkon njohuri për disa seksione të matematikës më të lartë.

pyetja 1. Pra, a është e mundur të përgatiten nxënës për olimpiada?

Është e mundur, por jo në kuadër të programit bazë.

Për më tepër, është pothuajse një kusht i domosdoshëm që këta nxënës të studiojnë në mënyrë plotësuese matematikën (është më mirë nëse këto janë klasa me studim të thelluar të matematikës). Nuk është rastësi që nxënësit tanë të shquar rusë në fushën e shkencës kompjuterike ishin po aq të suksesshëm në matematikë:

Victor Bargachev, 2 herë kampion absolut botëror në shkencat kompjuterike në mesin e nxënësve të shkollës, është fitues i Olimpiadës Ndërkombëtare të Matematikës (medalje argjendi);

Nikolai Durov, fitues 4 herë i Olimpiadave Ndërkombëtare në Informatikë (3 medalje argjendi dhe një ari), është pronar i dy medaljeve të arta të Olimpiadave Ndërkombëtare në Matematikë;

Vladimir Martyanov nga Nizhny Novgorod (dy herë kampion absolut botëror në shkencat kompjuterike) ishte fituesi i olimpiadave zonale ruse në matematikë dhe fizikë.

Në rajonin e Leningradit, mund të përmendet si shembull Stratonnikov Alexey, Potapov Alexey, Ananiev Artem, Pangin Andrey.

Pyetja 2 . Në cilën moshë nxënësit duhet të fillojnë përgatitjen?

Sa më shpejt aq më mirë, por brenda arsyes.

Për nivelin

mjafton të fillojë olimpiada rajonale nga klasa 7 - 8;

Këshillohet që të filloni olimpiadat ruse nga klasa e 5-të - e 6-të.

Shembull: kampioni i Moskës në programim midis nxënësve në 1998, Petr Mitrichev, student i klasës 7, ai ishte gjithashtu pjesëmarrësi më i ri në Olimpiadën e 9-të Gjith-Ruse për nxënësit e shkollave në shkenca kompjuterike dhe pjesëmarrës në kampet e trajnimit për të përgatitur gjuhën ruse ekipi për Olimpiadën Ndërkombëtare.

Pyetja 3 . Në çfarë forme duhet të mbahen mësimet në përgatitje për Olimpiadat?

Në formën e lëndëve me zgjedhje ose të lëndëve të veçanta.

Për ta përgatitur mirë një student, për ta thënë me një frazë të njohur, është e rëndësishme, para së gjithash, “jo vetëm të mbushësh kupën e dijes, por edhe të ndezësh pishtarin”. Me fjalë të tjera - të ngjall interes!

Sipas përvojës së liceut tonë, kjo kontribuon në këtë:

Lidhjet ndërdisiplinore luajnë një rol të rëndësishëm.

Liceu prej pesë vitesh zhvillon kursin e veçantë “Matematika në kompjuter” për klasat 5-6. Nxënësit njihen në formë vizuale me konceptet matematikore (për shembull, një skanim i animuar i kubit, një plan koordinativ me një rrjet të plotë), mësojnë t'i qasen në mënyrë krijuese zgjidhjes së problemeve standarde (për shembull, duke përdorur një paraqitje grafike të problemeve të transfuzionit dhe peshimit në një kompjuter).

Zhvillimi i interesit lehtësohet nga mësimet me temën "Modelimi i lëvizjes" nga lëvizja më e thjeshtë e një topi të bilardos në një model kompleks të linjave të fuqisë së fushës elektrike me dy ngarkesa. Veçanërisht mbresëlënës është simulimi në kompjuter i "fluturimit të një aeroplani letre" dhe demonstrimi i këtij fluturimi në realitet. Gjithashtu interesante është detyra e modelimit të lëvizjes së satelitit dhe përcaktimi i shpejtësisë së parë, të dytë hapësinore, koha e fluturimit të raketës Vostok me Yuri Gagarin rreth Tokës (të gjithë duhet ta dinë këtë ngjarje!).

Mësime të tilla zhvillohen të diferencuara sipas shkallës së gatishmërisë së nxënësve.

Për klasat 7-8 organizohet kampi shkollor “Intelekti” gjatë dy-tre javëve të para të pushimeve verore, ku fëmijët studiojnë informatikë sipas një programi të veçantë.

Për shembull, programi "Labyrinth" përfshin tema:

ndërtimi i një labirinti (një algoritëm interesant për gjenerimin e një labirinti të rastësishëm me kompleksitet të ndryshëm);

duke lëvizur nëpër labirint duke përdorur çelësat e kontrollit;

kërkoni për një rrugëdalje nga labirinti, duke filluar nga më e thjeshta sipas rregullit të dorës së majtë (duke mbajtur në njërën anë të labirintit);

kërkoni për rrugën më të shkurtër në labirint.

Ky program inkurajon studentët të zhvillojnë lojërat e tyre të ecjes dhe të shtënave. Gjëja kryesore është të kuptuarit se ata vetë mund ta krijojnë atë!

Për klasat 10, organizohet një praktikë verore në ndërmarrje të ndryshme në Sosnovy Bor për një muaj. Studentët fitojnë aftësi për të zgjidhur problemet praktike, konsolidojnë njohuritë e tyre për të punuar me bazat e të dhënave, aplikacionet e zyrës së kontabilitetit, krijojnë në mënyrë të pavarur programe sipas udhëzimeve të kuratorëve, fitojnë njohuri shtesë (për shembull, kur punojnë me rrjetet kompjuterike, sistemin operativ Unix). Një vlerësim nga ndërmarrja është rezultat i zakonshëm i një pune të tillë.

Djemtë demonstrojnë programet e tyre në konferencën tradicionale të shkollës për informatikë "Ne dhe kompjuteri", këtë vit ishte tashmë konferenca e gjashtë. Zhvillimet më të mira të softuerit prezantohen çdo vit nga fëmijët në Konferencën Ndërkombëtare “Informatika e Shkollës dhe Problemet e Zhvillimit të Qëndrueshëm”, që mbahet në Shën Petersburg, ku puna e fëmijëve vlerësohet me diploma të shkallës I dhe II.

Programe të veçanta përdoren si material edukativ.

Për një grup "dashamirës të kompjuterit" në një kuptim të mirë, dhe jo në kuptimin, për shembull, të lojërave kompjuterike, zhvillohen lëndë zgjedhore të drejtuara posaçërisht dhe kurse speciale me tema: mësimi i një gjuhe programimi shtesë, algoritmi i problemeve jo standarde, problemet e olimpiadës, teoria e grafikëve etj.

Pyetja 4 . Sa njerëz duhet të jenë në klasat e lëndëve zgjedhore të orientuara posaçërisht?

Grupe prej 6 – 12 personash.

Kur punoni për një rezultat specifik (d.m.th., duke u përgatitur për një olimpiadë qytetore, rajonale ose ruse), duhet të ketë një grup prej 3 deri në 6 persona. Këto klasa tashmë janë duke u trajnuar dhe këtu mësuesi vepron më shumë si trajner, sesa mësues. Si po shkon mësimi?

Ajo quhet një temë.

Janë renditur detyrat për këtë temë.

Përzgjidhet një nga detyrat më të njohura ose më interesante.

Me gojë, së bashku me djemtë, diskutohet algoritmi i zgjidhjes.

Djemtë shkruajnë një program, mësuesi rregullon kohën, vlerëson zbatimin e zgjidhjeve, ndihmon në gjetjen e gabimeve, vë në dukje mangësitë në efikasitet (numri i operacioneve, përdorimi i RAM-it, koha e zgjidhjes).

Pyetja 5 . Cilat tema duhet të studiohen në orët e përgatitjes për Olimpiadën?

Është e pamundur të parashikohet gjithçka, por mund të dallohen grupet e mëposhtme të algoritmeve:

Algoritme mbi numra të plotë.

Rekursioni.

Renditja.

Detyrat e numërimit.

Probleme gjeometrike.

Metodat numerike.

Modelimi statistikor.

Grafikët dhe pemët.

Transformimet e tekstit.

Le të shqyrtojmë më në detaje temat e nevojshme për të studiuar në përgatitje për Olimpiadat. Klasat teorike duhet të përfshijnë përkufizime, deklarata (në disa raste, domosdoshmërisht me prova).

Algoritme mbi numra të plotë

Pjesëtueshmëria

Gjatë studimit të kësaj teme, është e nevojshme të jepen përkufizime të pjesëtuesit, numrave të shumëfishtë, të thjeshtë dhe të dyfishtë, të jepen pohime me prova për pjesëtueshmërinë e shumës dhe ndryshimit të dy numrave, për pjesëtueshmërinë e prodhimit.

Modifikimi i parë i algoritmit të Euklidit (me zbritje)

Duke i ulur në mënyrë sekuenciale numrat (duke zëvendësuar më të madhin me diferencën e numrave) derisa të bëhen të barabartë, arrijmë në pjesëtuesin më të madh të përbashkët të këtyre numrave.

Detyrat që duhen analizuar gjatë studimit të kësaj teme:

Përcaktoni nëse numrat e shumtë janë të dyfishtë

Zvogëloni thyesën (shënohen numëruesi dhe emëruesi i thyesës)

Shkruani një program "Llogaritësi" në thyesa të thjeshta

Modifikimi i dytë i algoritmit të Euklidit, duke përdorur ndarjen me një mbetje

ku r – pjesa e mbetur e pjesëtimit të numrit më të madh me numrin më të vogël.

Kështu, duke ulur numrat, marrim pjesëtuesin më të madh të përbashkët si mbetjen e fundit jozero.

Problem për të zgjidhur: një drejtkëndësh me gjatësi të brinjëve a dhe b, ku a dhe b janë numra natyrorë, të prerë në katrorë të sipërfaqes maksimale. Përcaktoni madhësinë e katrorëve dhe numrin e përgjithshëm të tyre.

Ekuacionet diofantine

Duke përdorur pohimin për paraqitjen e pjesëtuesit më të madh të përbashkët të dy numrave si një kombinim linear i këtyre numrave, arrijmë në pohimin për zgjidhshmërinë në numra të plotë të një ekuacioni të formës. sëpatë + nga = c(ekuacioni diofantin).

Detyrat që duhen analizuar gjatë studimit të kësaj teme:

Detyrat për shkëmbimin e parave me monedha të një emërtimi të caktuar.

Detyrat e transfuzionit.

Gjatë studimit të algoritmit për zgjidhjen e problemit të transfuzionit, duket e dobishme të përdoret programi ndihmës demonstrues dhe trajnimi "Transfuzioni", me ndihmën e të cilit studentët mund të vënë në praktikë algoritmin e studiuar. Është e nevojshme të rregullohet ky algoritëm për të gjetur të paktën një zgjidhje të ekuacionit të Diofantinës. Më pas jepet një algoritëm i përgjithshëm për zgjidhjen e ekuacionit të Diofantinës me formula për gjetjen e të gjithë grupit të zgjidhjeve.

numrat e thjeshtë

Shumë probleme të olimpiadave të niveleve të ndryshme lidhen me numrat e thjeshtë. Metoda klasike për gjetjen e numrave të thjeshtë është sita e Eratosthenes. Të lidhura me këtë algoritëm janë zgjidhjet e mëposhtme detyrat:

Numrat binjakë;

Numrat perfekt;

mbulesë tavoline ulema;

Numrat miqësorë, etj.

Aritmetikë "e gjatë".

Detyrat për aritmetikën "të gjatë" lindin kur nuk është e mundur të ruhet rezultati në lloje standarde të të dhënave (numra të plotë ose të gjatë), sepse është shumë i madh. Në këtë rast përdoret metoda e ruajtjes së numrave të gjatë si një grup shifrash dhe për të kryer veprime aritmetike me numra të tillë është e nevojshme të shkruhet procedura speciale për mbledhjen, shumëzimin dhe pjesëtimin e numrave të gjatë.

Detyrat tipike: gjeni numrin N! (N-faktorial), përcaktoni periudhën e thyesës.

rekursion

Pothuajse çdo libër mbi programimin merret me procedura dhe funksione rekursive dhe rekursive. Por ka shumë pak libra ku tema e rekursionit do të trajtohej në detaje. Tradicionalisht, shqyrtimi i një funksioni rekurziv fillon me gjetjen e faktorialit të një numri. Një funksion i shkurtër në një rresht, por nuk është e qartë pse faktoriali llogaritet në mënyrë rekursive, nëse tashmë konsiderohet thjesht në një cikël me parametrin.

Sa më të rinj të jenë studentët, aq më të rëndësishme janë për ta parimet e qartësisë dhe thjeshtësisë. Një hyrje në rekursion mund të fillojë me rimën e njohur për "10 indianët e vegjël".

Hapi tjetër është vizatimet rekursive. Ne fillojmë me vizatimet më të thjeshta, për shembull, duke vizatuar një "matryoshka" të thjeshtuar.

fjokat e borës që bien në të gjithë ekranin;

degë me ngjyra të ndryshme, gëzof të ndryshëm dhe madhësi të ndryshme (një përbërës i rastësishëm futet në gjatësinë e degës).

Kompletet fraktale janë me interes të madh për fëmijët: peceta dhe mbulesa tavoline e Sierpinskit, modeli i mushkërive të njeriut nga Mandelbrot, fraktali Harter-Hateway (i njohur tek ne si vija e thyer e Dragoit), kthesat e Hilbertit, fjolla e borës së Koch. Rekursioni është kaq i natyrshëm këtu sa askush nuk pyet nëse është e mundur të bëhet pa të. Dhe vetëm tani, kur sharmi dhe bukuria e rekursionit nuk shkakton asnjë dyshim, mund të kalojmë në detyra që, sipas përcaktimit të tyre, janë rekursive. Këto janë detyrat e mëposhtme: faktoriali i një numri, fuqia e N-të e një numri, gcd( a, b), Funksioni Ackerman, numrat e Fibonaçit, shndërrimi i numrave nga sistemi i numrave të 10-të në të 2-të, duke gjetur maksimumin dhe minimumin në grup. Shumë detyra, rezulton, mund të bëhen duke përdorur rekursion. Gjëja kryesore është që një vizion i rekursionit shfaqet në detyra që më parë nuk ishin zgjidhur në mënyrë rekursive. Për qëllime të reja, për shembull, në problemin e prerjes së një drejtkëndëshi në katrorë të sipërfaqes maksimale, propozohet të bëhet mbështetje grafike vizuale duke përdorur rekursion. Dhe është absolutisht "keq" pa rekursion kur zgjidh probleme të tilla si "Kulla e Hanoi". Në këtë rast, programi i demonstrimit dhe trajnimit "Kulla e Hanoi" ndihmon për të realizuar këtë dhe në praktikë zotërimin e algoritmit rekurziv për zgjidhjen e këtij problemi.

Renditja

Pa njohuri për algoritmet e renditjes, nuk mund të ndihet i qetë në olimpiada të niveleve të ndryshme. Problemet mund të formulohen si në mënyrë eksplicite duke përmendur algoritmin e renditjes, ashtu edhe duke nënkuptuar përdorimin e algoritmit të renditjes brenda zgjidhjes. Dy algoritmet më të thjeshta për t'u njohur janë renditja me flluska dhe renditja e shkëmbimit (duke kërkuar për minimumet e njëpasnjëshme). Me sasi të vogla të dhënash, këto dy metoda janë mjaft të mjaftueshme, por kur punoni me të dhëna të matura në dhjetëra e qindra KB, duhet të dini një nga llojet e shpejta. Renditja e shpejtë e Hoare, e cila zbatohet në mënyrë rekursive, mund të preferohet. Ju gjithashtu duhet të dini disa truke kur organizoni të dhëna në skedarë të mëdhenj. I gjithë skedari ndahet në një numër pjesësh që mund të renditen duke përdorur QSORT, dhe më pas skedarët e renditur mund të bashkohen pa një program klasifikimi (nga rruga, kjo është një detyrë shumë e dobishme nga pikëpamja teknike që kërkon saktësi dhe saktësi dhe teknikë e mirë programimi).

Duke kërkuar për opsione

Problemet e kërkimit përbëjnë një klasë të madhe problemesh olimpiade. Numërimi fillon me kërkimin më të thjeshtë për minimumin dhe maksimumin në një grup njëdimensional ose kërkimin e një elementi me vetitë e dhëna. Më pas, përsëritet mbi çifte elementësh duke përdorur një lak të mbivendosur, më pas përsëritet mbi trefish elementësh duke përdorur një lak të trefishtë (si, për shembull, në problemin e gjetjes së tre pikave në një plan midis N pikave të dhëna që formojnë një trekëndësh me sipërfaqen maksimale ). Dhe nëse renditni kombinimet e 4, 5, 6, etj. elementet? Sa cikle nevojiten? Rezulton se ka algoritme që reduktojnë ndjeshëm numërimin.

Mjaft e gjatë për sa i përket kohës së ekzekutimit, por një nga algoritmet më të gjithanshme të përsëritjes është backtracking ose backtracking. Programuar në mënyrë rekursive. Më së miri shpjegohet në detyrat e mëposhtme:

Lëviz kalorësi rreth tabelës së shahut N*M;

Organizoni 8 mbretëresha në një tabelë shahu me madhësi 8 * 8 në mënyrë që të mos kërcënojnë njëra-tjetrën;

Gjeni një rrugëdalje nga labirinti, etj.

Është gjithashtu e nevojshme t'u shpjegohet studentëve se në rast të kohës shumë të gjatë të ekzekutimit të programit, është e nevojshme të kufizohet "backtracking". Për shembull, në një problem shahu me një madhësi dërrase 8 * 8, programi ka funksionuar për një kohë mjaft të gjatë. Është e mundur dhe madje e nevojshme të aplikohet simetria, pasqyrimi, kryerja e një detyre për gjysmën ose një të katërtën e tabelës së shahut.

Problemi klasik i "kthimit prapa" është problemi i "çantës së shpinës", atëherë mund të konsiderojmë derivatet e këtij problemi:

Ndani N numra në dy nëngrupe që janë më të afërt në shumë;

Nga një grup i caktuar fjalësh, zgjidhni nënrendin maksimal të fjalëve sipas rendit të fjalorit.

Problemet kombinuese lidhen edhe me numërimin. Ju duhet të zotëroni algoritmet për krijimin e renditjes leksikografike.

Detyrat e gjeometrisë

Minimumi i detyrueshëm që duhet të dini kur zgjidhni problemet e gjeometrisë përfshin sa vijon:

Të jetë në gjendje të sjellë në formë ekuacionin e një drejtëze që kalon nga dy pika

Ax + By + C = 0;

Të jetë në gjendje të përcaktojë nëse një pikë i përket një drejtëze apo një segmenti;

Të jetë në gjendje të përcaktojë nëse dy drejtëza kryqëzohen, dhe nëse kryqëzohen, atëherë përcaktoni pikën e tyre të kryqëzimit (për ta bërë këtë, llogaritni përcaktuesin e rendit të dytë);

Të jetë në gjendje të shkruajë ekuacionin e një drejtëze pingule ose të përcaktojë nëse një drejtëz është pingul me një tjetër (duke përdorur vetinë që prodhimi skalar i vektorëve pingul është i barabartë me zero);

Të jetë në gjendje të llogarisë distancën nga një pikë në një vijë.

Përveç kësaj, për të zgjidhur problemet e nivelit rajonal dhe gjithë-rus, kërkohet njohja e kursit fillestar të gjeometrisë analitike: produkti skalar dhe vektor i vektorëve, shprehja e tyre në terma të koordinatave. Produkti skalar përdoret për të gjetur këndin (ose kosinusin e këndit) kur ndërtohet, për shembull, trupi konveks i pikave të dhëna. Produkti kryq i dy vektorëve përdoret, së pari, për të llogaritur sipërfaqet e shumëkëndëshave dhe së dyti, për të përcaktuar drejtimin në problemet përkatëse. Kjo njohuri është gjithashtu e nevojshme për të zgjidhur një problem të tillë klasik të Olimpiadës, siç është nëse një pikë gjendet brenda një shumëkëndëshi arbitrar.

Është e nevojshme të tërhiqet vëmendja e nxënësve për paqartësitë e koncepteve që mund të përdoren në detyra të ndryshme. Për shembull, për konceptin e produktit vektor

moduli i vlerës numerike përcakton zonën e paralelogramit të ndërtuar mbi vektorët e dhënë;

vlerë zero - vektorë paralelë;

shenja do të thotë që një vektor ndodhet "në të majtë" ose "në të djathtë" të tjetrit;

vektori që rezulton përcakton normalen në rrafshin e vektorëve të dhënë.

Metodat numerike

metoda e dikotomisë

Për të kërkuar të dhëna në një grup të renditur, përdoret metoda e dikotomisë (ose përgjysmimit), e ndjekur nga kontrollimi i vetive të dëshiruara. Kjo metodë, e cila është më e njohur për gjetjen e përafrimeve të rrënjëve të ekuacioneve jolineare, mund të përdoret për të kërkuar një sasi "të madhe" të dhënash. Në këtë rast, ne do të përdorim më shumë termin "kërkim binar". Një detyrë tipike është gjetja e një fjale të caktuar në një fjalor.

Në përgjithësi, kjo metodë është optimale.

Zgjidhja e sistemeve të ekuacioneve lineare: Metoda e Kramerit, metoda e Gausit.

metodat klasike. Zakonisht në problema numri i ekuacioneve nuk është më shumë se tre. Por njohja e rastit të përgjithshëm ndoshta do të jetë e dobishme.

Problem nga olimpiada rajonale 94 vjeç.

Ekuacioni i një reaksioni kimik futet si vijë: është e nevojshme të barazohet, d.m.th. rregulloni koeficientët.

Modelimi statistikor (metoda Monte Carlo).

Është shumë e dobishme të njohësh këtë metodë:

për modelimin e situatave probabilistike të lojës (hedhja e një monedhe, zari, bredhja). Është formulimi “lozonjar” ose i lidhur me diçka të njohur (të njohur, “të përditshme”) të problemit që ndihmon për të kuptuar metodën, konceptin e probabilitetit. Ju mund t'u ofroni studentëve detyra interesante:

Cila është më shumë, thyesat e reduktueshme apo të pareduktueshme? (Formulimi matematik: vlerësoni probabilitetin që një thyesë e zgjedhur rastësisht të jetë e pakalueshme);

basti më i mirë për të thjeshtët ("Quantum" nr. 5, 1987);

detyra kombinuese.

Për të përcaktuar sipërfaqet e figurave, kur zgjidhjet analitike janë të vështira.

Pra, në problemin (olimpiadën rajonale të vitit 1999) për gjetjen e zonës së kryqëzimit të tre rrathëve, metoda Monte Carlo mund të përdoret si një alternativë ndaj metodës analitike të drejtpërdrejtë, pasi është shumë e vështirë të nxirret një zgjidhje duke përdorur trigonometrike. marrëdhëniet. Mënyra më e mirë është të "përdorni gjeometrinë" për të analizuar raste të veçanta (kur nuk ka kryqëzim, kur kryqëzimi është në një pikë, një rreth brenda tjetrit), dhe metoda Monte Carlo për rastin e përgjithshëm.

Programim dinamik.

Ka raste kur është e pamundur të zgjidhet problemi me një numërim të plotë të opsioneve për shkak të numrit të tyre të madh. Por nëse në çdo hap problemi mund të ndahet në më të thjeshta dhe zgjidhja optimale për to mund të gjendet pa marrë parasysh të gjitha zgjidhjet e problemit të përgjithshëm, dhe më pas zgjidhjet e gjetura mund të aplikohen në hapat e ardhshëm, atëherë kjo do të thotë se në këtë rasti është i zbatueshëm parimi i programimit dinamik.

Ky parim perceptohet më lehtë në detyra specifike. Por shpjegimi i tij mund të fillohet me një histori argëtuese për shkallën e artë të Faraonit (të paraqitur në revistën "Kvant" nr. 10, 1991), dhe më pas të kalohet në detyrat e mëposhtme:

Problemi klasik i gjetjes së një rruge kaq të shkurtër në matricën numerike NxN A nga A(1,1) në A(n,n) në të cilën shuma e shifrave në qeliza ishte minimale ose maksimale.

Gjetja e një nënvargu të përbashkët të gjatësisë maksimale (një problem që lindi nga problemi real modern i biologjisë molekulare rreth informacionit të përbashkët gjenetik në molekulat e ADN-së).

Grafikët dhe pemët.

Një temë shumë e rëndësishme. Pothuajse asnjë nga olimpiadat e nivelit rus nuk mund të bëjë pa përdorimin e disa algoritmeve në grafikë. Është e nevojshme të prezantohet koncepti i një grafiku përmes kulmeve dhe skajeve, koncepti i grafikëve të drejtuar ose të padrejtuar, të analizohen metodat për paraqitjen e grafikëve në formën e një matrice, afërsi, matricë incidence, listë lidhjesh.

Për të çmontuar algoritmet kryesore në grafikë:

kërkimi i parë në thellësi (me fjalë të tjera, "kthim prapa" ose kërkim prapa);

kërkimi i parë në gjerësi (ose metoda e mbushjes);

Algoritmi i Dijkstra për gjetjen e shtigjeve më të shkurtra në një grafik nga një kulm i caktuar në të gjitha të tjerat;

Algoritmi i Floydit për gjetjen e shtigjeve më të shkurtra në një grafik midis të gjitha çifteve të kulmeve.

Transformimet e tekstit

Detyrat në të cilat është e nevojshme të analizohet një varg nganjëherë përfshijnë gjithashtu punën me skedarë, konstruksione grafike (të ngjashme me komandat e një teksti ose redaktuesi grafik) ose përdorimin e ndonjë teknike programimi (për shembull, përfaqësimi i një "stivo" si një varg karakteresh në problemi i shprehjes së saktë të kllapave për disa lloje kllapash).

Është paraqitur një grup i gjerë, por jo i plotë temash të mbuluara nga problemet e Olimpiadës. Në shumë aspekte, kjo varet nga preferencat e organizatorëve të olimpiadave të niveleve të ndryshme (raundet teorike, detyrat që përdorin strategjitë e lojës, natyra e aplikuar "zyre").

Pyetja 6 . Çfarë mund të këshilloni kur zgjidhni problemet në olimpiadë?

Duke supozuar se teoria e algoritmeve është "studuar" dhe bazat e programimit janë zotëruar, pjesëmarrësit në konkurs mund t'i këshillohen sa vijon:

Jepni "në rezervë" një rezultat të caktuar "të garantuar" (sipas mendimit tuaj) për detyra të thjeshta. Kjo nuk do të thotë që detyrat e vështira duhet të lihen në minutën e fundit. Kur mendoni për zgjidhjen e tyre, mund të gjendet një algoritëm "i mirë" dhe një përqindje përkatësisht e madhe pikësh do të shërbejnë si sukses.

Nëse problemi është i vështirë për ju ose nuk ka kohë të mjaftueshme për ta zgjidhur atë, programoni raste të thjeshta të veçanta ( ndoshta disa teste do të kalojnë), ose përdorni një algoritëm nën-optimal, siç është një algoritëm i forcës brutale.

Nëse një detyrë ka një kufi kohor për zgjidhjen dhe algoritmi juaj i numërimit nuk përshtatet në këtë kohë, atëherë futni një kohëmatës në algoritëm që, kur i afrohet kohës kritike, përfundon detyrën dhe shfaq opsionin më të mirë të numërimit të gjetur (ndoshta do të jetë i saktë).

Zgjedhja e një gjuhe algoritmike është gjithashtu e rëndësishme, për shembull, në një program Basic është më e lehtë të punohet me grafikë, ndërsa një program Pascal ka një avantazh shpejtësie.

Vëzhgoni rreptësisht formatet hyrëse-dalëse të specifikuara në kushtin e detyrës: "autotestuesi" mund të perceptojë gabimisht një hapësirë shtesë, ose testet e burimit përmbajnë një presje ku keni dhënë një hapësirë në hyrjen e detyrës tuaj (veçoritë e operatorëve të hyrjes Pascal dhe Basic ).

Në thelb, çdo program ka një strukturë:

Futja e të dhënave

Blloku i vendbanimeve

Prodhimi i rezultatit

Vërtetoni dhe verifikoni që I/O është i saktë (me analiza të mundshme të të dhënave të gabuara) përpara se të programoni bllokun e llogaritjes.

Vendosni opsionet e përpiluesit për të trajtuar të gjitha llojet e gabimeve (të dobishme për korrigjimin e gabimeve) dhe çaktivizoni këto opsione përpara se të paraqisni detyrën (për të injoruar gabimet e mundshme të testimit që nuk ndikojnë në zgjidhje).

Kontrolloni problemin për kufizimet maksimale të dhëna (për shembull, nëse jepet n  1000, kontrolloni për n = 1000). Shikoni llojin e variablave të deklaruar (preferohet të përdorni llojin "long integer" për deklarimin e variablave integer).

Përdorni apelin me mençuri. Kuptimi i paqartë i problemit është i mundur. Juria është gjithashtu njerëz, dhe ju mund të mbroni pozicionin tuaj, t'i bindni që t'ju japin pikët e dëshiruara.

Si mjet i fundit, nëse jeni një "haker i lezetshëm" (një specialist i lezetshëm në pjesën e sistemit), ekzekutoni programin "fqinj" si tuajin (supozoj se askush nuk do ta vërejë).

Lejohet të keni fletët tuaja të mashtrimit (jo në formë elektronike) ose të përdorni kohën tuaj "të lirë" për të studiuar libra referencë.

Disa nga këto këshilla janë "të dëmshme", në përputhje me parimet e "ndoshta, mendoj, dhe disi". Ju lutemi merrni ato në mënyrë kritike, por ato janë jetike.

Pyetja 7 . Çfarë literaturë duhet përdorur në përgatitjen për Olimpiadat?

Ky artikull, si dhe burimet e mëposhtme.

A. Shen. Programimi: teorema dhe probleme, M. MTsNMO, 1995.

A.L. Brudno, L.I. Kaplan. Olimpiadat e Programimit në Moskë, M: Nauka, 1990.

V.A.Dagene, G.K.Grigas. 100 detyra programimi, M: Iluminizmi, 1993.

V.M. Bondarev, V.I. Rublinetsky, E.G. Kachko. Bazat e programimit, Kharkov: Folio, 1997.

V.M. Kiryukhin, A.V. Lapunov, S.M. Okulov. Detyrat në informatikë. Olimpiadat Ndërkombëtare. M: ABF, 1996.

N.M.Badin, S.G.Volchenkov, N.L.Dashnits. Olimpiadat e Yaroslavl në Informatikë. Yaroslavl, 1995.

S.M. Okulov. Abstrakte të klasave në informatikë (algoritme në grafikë). Kirov, 1996.

A.V. Alekseev. Olimpiadat shkollore në Informatikë. Shtëpia botuese e librit Krasnoyarsk, 1995.

A.S. Sipin, A.I. Dunaev. Olimpiada Rajonale në Informatikë. Vologda, 1994.

V.Pinaev. Olimpiada e qytetit në programim. Rybinsk, 1998.

S.A. Abramov. Ndërtime matematikore dhe programim. 1987.

Pyetja 1. Si të mësojmë të zgjidhim problemet e Olimpiadës në shkencat kompjuterike?

Për të mësuar se si të zgjidhni problemet e olimpiadës në informatikë, ju duhet të zgjidhni problemet në informatikë ... Natyrisht, në të njëjtën kohë duke kërkuar në literaturën përkatëse.

Pyetja 2. Sa probleme duhet të zgjidhni për të performuar në mënyrë adekuate në Olimpiadat në Informatikë?

Pyetja është bërë, natyrisht, jo saktë dhe ndoshta vështirë se është e mundur t'i përgjigjemi, por ia vlen të thuash disa fjalë për këtë. Siç më tha Mikhail Medvedev, një specialist në fushën e përgatitjes për Olimpiadat ACM, krijimi i një problemi thelbësisht të ri olimpiadë nuk është aq i lehtë sa mund të duket në shikim të parë. Për këtë arsye personat përgjegjës për zhvillimin e olimpiadave thjesht marrin problemet e viteve të shkuara dhe i servirin me një “salcë të re”. Ndodh shpesh që problemet për olimpiadat rajonale dhe zonale në Informatikë të “këputen” pa asnjë ndryshim nga faqet e dedikuara për programimin e Olimpiadës.

Pra, meqenëse shumë probleme janë shumë, shumë të ngjashme, është e nevojshme të mësoni se si të zgjidhni problemet nga i gjithë diapazoni: renditja, programimi dinamik, aritmetika e gjatë, etj.

Pyetja 3. A është e mundur përgatitja e nxënësve për Olimpiadat në Informatikë si pjesë e kurrikulës shkollore?

Mendoj se është joreale. Të gjithë e dinë prej kohësh se një kurs shkollor në shkencat kompjuterike është një gjë dhe olimpiadat e shkencave kompjuterike janë një tjetër. Po, në programin mostër në shkencat kompjuterike, në klasën 9, një numër mjaft i madh orësh i kushtohen mësimit të programimit. Në tekstin shkollor të Semakin për klasën 9, programimi bazohet në gjuhën Pascal, shembujt e Ugrinovich janë dhënë në lidhje me Visual Basic. Por, edhe nëse zbatojmë një qasje të diferencuar për mësimin e nxënësve të shkollave, këto orë nuk ka gjasa të jenë të mjaftueshme për të përgatitur nxënës individualë për olimpiadat nga e para.

Pyetja 4. Nëse në program nuk ka orë të mjaftueshme për përgatitjen e nxënësve për Olimpiada, atëherë si të përgatitemi?

Sipas dy opsioneve të para, gjithçka është e qartë, por duhet të ketë mirëkuptim nga drejtuesit e shkollës. Shpesh, mes mësuesve zhvillohet një "betejë për orën" dhe mund të mos bjerë në një rreth ose në një program me zgjedhje në programimin e orës.

Entuziazmi personal i arritur në një masë ekstreme është një fenomen shumë i dëmshëm, për mendimin tim. Arsimi rus nuk duhet të mbështetet në entuziazëm. Përndryshe, rezulton se për sa kohë ka entuziazëm, gjërat po shkojnë, fitili ka marrë fund dhe gjithçka është shembur. Entuziazmi nuk do të zgjasë shumë, por ndonjëherë ia vlen ta shfaqni me shpresën se gjërat do të zbresin.

Pyetja 5. Kam 25 (26, 30...) orë ngarkesë kryesore, a është ende e mundur të studioj me studentët në klubin e programimit?

Më duket se me një ngarkesë të tillë është më realiste të çmendesh sesa të përgatitësh nxënës për olimpiada. Unë sinqerisht simpatizoj të gjithë mësuesit me një ngarkesë të madhe pune. E kuptoj që nuk është e nevojshme të marrësh një numër të madh orësh nga një jetë e mirë, por nuk e kuptoj se si mund të punohet në kushte të tilla.

Pyetja 6. A mund të përgatiten nxënësit e shkollës për Olimpiadën jashtë orarit të mësimit dhe nëse po, si të organizohet më mirë përgatitja?

Ata munden, por të paktën duhet të kenë një kompjuter në shtëpi. Idealisht, duhet të ketë edhe internet. Nëse keni një PC dhe internet, mund të zgjidhni problemet në një nga faqet e specializuara me verifikim të automatizuar të zgjidhjeve, për shembull, në sitin Shkolla e Programuesit.

Pyetja 7. Çfarë kërkohet nga një mësues për përgatitjen cilësore të nxënësve për Olimpiadë?

Aftësia për të mësuar. Në fund të fundit, siç ndodh, një person është diplomuar në një institucion arsimor dhe këtu përfundon ndonjëherë zhvillimi i tij në drejtim të marrjes së informacionit. Duket se mjafton të punosh në shkollë, kështu që pse të shqetësohesh...
Jini gjithmonë në kontakt. Studenti juaj mund të ketë një pyetje në çdo kohë, në fund të fundit, ka nga ata që zgjidhin problemet natën. Nëse nuk mund të flini, atëherë pse jo, nëse është e mundur, t'i përgjigjeni atij duke përdorur të njëjtin "ICQ" ose programin Skype.

Metodat e përgatitjes për Olimpiadat në Informatikë

Rëndësia e temës

Në lidhje me aktualizimin dhe aktivizimin e lëvizjes olimpiada, problemi i përgatitjes së studentëve për pjesëmarrje në olimpiada po bëhet gjithnjë e më i mprehtë. Përgatitja e një “nxënësi-nxënës olimpiadë” fillon me përgatitjen e një mësuesi.

Problemet me të cilat përballet mësuesi:

1. Studimi i formave të reja të zhvillimit të olimpiadave.

2. Njohuri të algoritmeve për zgjidhjen e problemave të olimpiadës.

3. Prania e vetë detyrave.

4. Njohuri të gjuhëve programuese.

5. Koha për të studiuar, korrigjuar dhe testuar detyrat.

6. Mësimi i nxënësve për organizimin korrekt të aktiviteteve në Olimpiadë.

Pavarësisht se diapazoni i problemeve të shqyrtuara në Olimpiadën e Programimit është i kufizuar, zgjidhja e problemit mund të jetë e vështirë jo vetëm për studentin, por edhe për mësuesin, pasi disa detyra kërkojnë njohuri të matematikës së lartë. Vërtetimi i zgjidhjeve dhe përgatitja e testeve zakonisht kërkon shumë kohë.

Këtu janë disa veçoritë e përgatitjes së nxënësve për programimin e Olimpiadës :

· Në kurrikulën shkollore nuk ka një lëndë të tillë "programim" dhe madje një seksion të tillë. Kjo do të thotë, praktikanti duhet të ketë motivimin e tij, mjaft të fortë.

· Ekziston një kufizim që gjatë zgjidhjes së problemeve është e dëshirueshme të përdoret vetëm një nga gjuhët e programimit (SI ose PASCAL).

· Stërvitjet e vazhdueshme shkojnë pothuajse në nivel sportiv.

· Shpenzim i madh kohe, kohëzgjatja e Olimpiadës me analiza shpesh i kalon 6 orë.

· Algoritmet dhe formulat e përdorura në zgjidhjen e shumicës së problemeve studiohen vetëm në universitete.

Sigurisht Nevojiten edhe trajnime të nivelit më të lartë për mësuesit për të punuar me studentë të talentuar që marrin pjesë në konkurse programimi:

· Mundësisht një arsim i dytë, universitet i specializuar në programim.

· Mësimdhënësit e IPK-së, kurse për studimin e gjuhëve programuese, për programimin e Olimpiadës.

· Vetë-përgatitje duke përdorur materiale nga burime shtesë.

Por edhe njohja e mirë e një gjuhe programimi nuk jep një garanci 100% që një nxënës do të fitojë edhe në një olimpiadë shkolle apo rrethi.

Ide pedagogjike

Motivimi është stimuli kryesor për pjesëmarrjen në olimpiada për një nxënës. Kjo nuk është vetëm një mundësi për të përmirësuar notën tuaj, por edhe një mundësi për të treguar njohuri dhe erudicion mbi problemin që zgjidhet, aftësitë tuaja organizative, për t'u dhënë mundësinë për të "fituar notë" studentëve të tjerë (edhe atyre që nuk marrin pjesë në Olimpiadë).

Dëshira e studentit për udhëheqje, demonstrimi i arritjeve të veta është një nga kushtet themelore për pjesëmarrjen në lëvizjen olimpike. Sigurisht, me një motivim të tillë, ka mjaft njerëz që duan të punojnë, por në rrjedhën e punës ka një rotacion të pjesshëm dhe kjo është e pashmangshme me ngarkesën moderne të nxënësve të shkollës. Mbeten kryesisht fëmijë punëtorë, ata studentë që nuk kanë frikë nga disfata dhe i vendosin vetes synime specifike.

Një nga forcat drejtuese kryesore për pjesëmarrjen e nxënësve në garat e programimit është dëshira dhe interesimi i mësuesit, si dhe ndihma, durimi dhe besimi i prindërve.

Në vitin 1964, V. Vroom propozoi "teorinë e pritshmërisë". Ai besonte se nxitje për punë efikase dhe cilësore varet nga një kombinim i tre faktorëve - pritjet njerëzore:

1. Pritshmëria se përpjekjet do të çojnë në rezultatin e dëshiruar.

2. Pritshmëria se rezultatet do të çojnë në shpërblime.

3. Pritja se shpërblimi do të jetë me vlerë të mjaftueshme.

Sa më i madh të jetë besimi i personit se të gjitha këto pritshmëri do të realizohen, aq më i fortë do të jetë nxitja për të punuar. Nëse ndryshojmë pak formulimin e V. Vroom në një kontekst edukativ, atëherë kjo është ajo që ndodh:

Teoria e pritshmërisë tregon se çfarë duhet të bëjnë mësuesit për t'i bërë të forta stimujt e të nxënit të studentëve:

o Mësojini studentët të marrin rezultatet e kërkuara dhe të krijojnë të gjitha kushtet e nevojshme për këtë;

o Të vendosë një lidhje të drejtpërdrejtë ndërmjet rezultateve të punës dhe vlerësimit të nxënësve;

o Hulumtoni nevojat e studentëve për të ditur se cilat shpërblime kanë vlerë për ta.

Nisur nga kjo, mekanizmat e motivimit dhe faktorët kryesorë të efektivitetit të stimujve mund të shprehen si:

o Njohuritë e mësuesve për nevojat, interesat, nevojat e nxënësve.

o Krijimi i një lidhjeje të drejtë të drejtpërdrejtë midis rezultateve dhe shpërblimeve.

o Shpërblimi i menjëhershëm.

o Shkalla e kënaqësisë së pritshmërive.

Për t'u përgatitur për olimpiadat e programimit, mund të aplikoni një metodologji duke përdorur një sistem testimi "NSUTS" , i zhvilluar në bazë të NSU, i cili ju lejon të zgjidhni shpejt shumë nga këto çështje.

Teknologjia e përdorimit të sistemitNSUTS »

Sistemi ndodhet në https://olimpiadë. *****/nsuts-test/nsuts_new_login. cgi. Kur klikoni në këtë lidhje, arrijmë në faqen e autorizimit, ku duke futur emrin e përdoruesit dhe fjalëkalimin, mund të futeni në sistem.

https://pandia.ru/text/78/392/images/image002_97.jpg" width="623" height="258 src=">

Në këtë rast, ne zgjedhim, për shembull, stërvitjet në shkollë, pas së cilës do të çoheni në faqen " Faqja e regjistrimit për trajnimin shkollor ku regjistrimi është i thjeshtë dhe i drejtpërdrejtë. Vetëm mbani në mend se të dhënat që futni duhet të jenë të besueshme.

https://pandia.ru/text/78/392/images/image004_80.jpg" width="623" height="306">

në skedën " Ndihmë» mund të lexoni një udhëzim të shkurtër se si të punoni në sistem. Merrni parasysh përmbajtjen e kësaj faqeje.

Sistemi i testimit NSUTS. Përshkrim shumë i shkurtër.

Ju jeni në sistemin e testimit automatik NSUTS për zhvillimin dhe kontrollin e olimpiadave të programimit. Seksioni aktual shfaqet në krye të ekranit. Në këndin e sipërm të djathtë - emri i Olimpiadës aktuale, emri i ekipit tuaj dhe butoni për të dalë nga sistemi - " Dilni jashtë».

Në seksionin " Turne» ju mund të zgjidhni raundin aktual të Olimpiadës.

Në seksionin " Lajme» mund të lexoni njoftimet dhe komentet nga juria dhe komiteti organizativ i Olimpiadës. Dhe gjithashtu zbuloni oraret e fillimit dhe përfundimit të Olimpiadës. Pas fillimit të Olimpiadës, në këtë faqe shfaqen lidhjet me kushtet e problemeve.

Në seksionin " Kaloni» detyrat dërgohen për testim. Për të paraqitur një problem për testim, specifikoni gjuhën në të cilën është shkruar zgjidhja dhe numrin e problemit. Ngjitni tekstin e vendimit në fushën e hyrjes dhe klikoni " dërgoni". Ose zgjidhni një skedar duke përdorur shiritin e përzgjedhjes së skedarit dhe më pas klikoni " dërgoni". Zgjidhja juaj do të shfaqet në listën e detyrave të paraqitura në " rezultatet».

Zgjidhjet tuaja duhet të lexojnë hyrjen nga një skedar hyrje. tekst dhe nxirrni rezultatin në një skedar prodhimit. tekst . Ndalohet leximi nga rrjedha standarde e hyrjes, shkrimi në rrjedhën standarde të daljes, rrjedha standarde e gabimit. Programi pjesëmarrës nuk duhet të hapë, lexojë ose modifikojë skedarë përveç hyrjes. txt dhe dalje. txt ose të tjera të specifikuara në deklaratën e problemit. Qasja në sistemin e skedarëve dhe burime të tjera përveç atyre të listuara në deklaratën e detyrës është e ndaluar. Shkelja e kësaj kërkese mund të jetë arsye për skualifikimin e ekipit. Kufiri në madhësinë e kodit burimor është 100 kilobajt. Formati i daljes duhet të përputhet saktësisht me kërkesat e përshkruara në deklaratën e problemit.

Pjesëmarrësi mund të përdorë cilindo nga përpiluesit e listuar në " Kaloni».

Opsionet e përpilimit:

Visual C++ 6.0
Visual C++ 2005	kl. detyrë exe /EHsc /Ox. cpp /lidhja /STACK:
MinGW 5.1.4 (GCC 3.4.5)	c++.exe - Mur - Wl,--stack= - Detyrë O2. cpp
Freepascal 2.2.0	ppc386.exe - O2 - Detyra Cs. pas
Java 1.6.0_07	javac. detyrë exe. java
NisjaJava	java - Xmx480m - Xss32m - Djava. sigurinë. menaxher - Duser. language=en_US Detyrë
Borland Delphi 2006

Në seksionin " rezultatet» Mund të shikoni statusin e testimit dhe rezultatet e testimit të detyrave që keni dorëzuar. Ne rresht " Koha» tregon kohën në momentin e paraqitjes së zgjidhjes, gjuhën e programimit që keni treguar gjatë dorëzimit të kësaj zgjidhjeje. lidhje " View burimi» do të tregohet teksti i vendimit të paraqitur.

Ne rresht " Rezultati» Rezultati i testit shfaqet:

Në radhë - zgjidhja është në radhë për testim.

Testimi... - po testohet tani.

Është tejkaluar kufiri i kodit burimor - është tejkaluar kufiri i kodit burimor të programit.

Gabim përpilimi - Kompilimi dështoi (arsyeja e dhënë).

Kur një zgjidhje testohet, statusi merr një nga vlerat e mëposhtme:

PRANOHET! - vendimi llogaritet i saktë.

Përgjigje e gabuar - Përgjigje e gabuar në test.

Afati kohor është tejkaluar - zgjidhja nuk plotësoi kohën e caktuar të procesorit.

Kohëzgjatja - zgjidhja nuk e plotësoi kohën e caktuar.

Gabim në kohën e ekzekutimit - zgjidhja ktheu një kod gabimi jo zero.

Kufiri i memories u tejkalua - zgjidhja nuk e përmbushi kufirin e caktuar të memories.

Nuk ka skedar dalës - nuk ka skedar dalës. tekst.

Shkelja e sigurisë - zgjidhja ka kryer një veprim të ndaluar nga rregullat.

Në këtë rast, tregohet numri i testit në të cilin ndodhi gabimi (për Olimpiadat ACM).

Një rregull i shkurtër për ndërtimin e një vlerësimi për Olimpiadat ACM është si vijon: nga dy ekipe, ai me numrin më të madh të problemeve të zgjidhura do të jetë më i lartë në vlerësim; nëse numri i detyrave është i njëjtë, atëherë skuadra me kohën më të ulët të penalltisë është më e lartë. Nëse numri i detyrave dhe koha e penalltisë janë të njëjta për disa ekipe, atëherë këto ekipe zënë disa vende radhazi.

Koha e penalltisë është shuma e kohës së penalltisë për të gjitha detyrat. Koha e ndëshkimit për një detyrë është 0 nëse detyra nuk dorëzohet. Nëse detyra kalohet, atëherë koha e dënimit të saj llogaritet sipas formulës:

koha_e_zgjidhjes_korrekte + (numri_përpjekjeve_të_pasuksesshme * 20).

seksioni « Pyetje dhe pergjigje» është menduar për komunikim me Jurinë e Olimpiadës. Ju mund t'i bëni pyetje jurisë për kushtet e problemeve ose të vini në dukje pasaktësinë e formulimit të problemeve.

Gjithashtu, nëse juria e konsideron të nevojshme të bëjë ndonjë ndryshim në kushtet e problemeve, ndryshimet do të publikohen në këtë seksion ose në lajme.

Tani që kemi mbuluar bazat e punës me sistemin, le t'i hedhim një vështrim Si mund të marr një detyrë për Olimpiadën.

Në skedën "Tour", zgjidhni turneun e Olimpiadës që na nevojitet, për shembull, " Përgatitja për Olimpiadën Gjith-Ruse 21.03.2010 (Gjeometri) ». Pas kësaj, shkoni te skeda "Lajmet" dhe ndiqni lidhjen "Kushtet e turneut" për të shkarkuar skedarin e formatit MS Office Word, i cili përmban detyrat e paraqitura për zgjidhje në këtë turne.

Pasi të kemi zgjidhur problemin, në skedën "Dorëzo" ne e dërgojmë atë për verifikim, duke vendosur të gjithë parametrat e nevojshëm (gjuhën, tekstin e programit ose një skedar me programin). Rezultatet e testit mund të gjenden në skedën "Rezultatet".

Klasat kryesore të problemeve të paraqitura për Olimpiadat në Informatikë

Për përfundimin me sukses jo vetëm të Olimpiadës, por edhe të detyrave brenda klasës, kërkohet:

1. Për të zotëruar rrjedhshëm gjuhën dhe mjedisin e programimit (në rastin tonë është Free Pascal), të jeni në gjendje të ndërtoni dhe zbatoni algoritme të ndryshme duke përdorur këtë gjuhë.

2. Zotërojnë aparatet e nevojshme matematikore.

3. Të njohë algoritmet për zgjidhjen e klasave kryesore të problemeve, optimizimin e tyre.

Detyrat e programimit të Olimpiadës mbulojnë një gamë shumë të gjerë njohurish, por ato që hasen më shpesh dhe që shkaktojnë vështirësitë më të mëdha janë këto:

1. Detyrat që përdorin struktura komplekse të dhënash si vargje, radhë, rafte, lista të lidhura dhe pemë.

2. Grafikët si bashkësi objektesh me shumë lidhje.

3. Problema me përdorimin e gjeometrisë analitike dhe bazuar në konceptin “vektor”.

4. Probleme të programimit dinamik.

Le t'i shqyrtojmë këto klasa problemesh në më shumë detaje.

Detyrat që përdorin struktura komplekse të të dhënave si vargje, radhë, rafte, lista të lidhura dhe pemë.

Programet përbëhen nga algoritme dhe struktura të dhënash. Programet e mira përfitojnë nga të dyja. Zgjedhja dhe dizajni i strukturës së të dhënave është po aq i rëndësishëm sa edhe dizajni i procedurës që i manipulon ato. Organizimi i informacionit dhe metodat e aksesit në të zakonisht përcaktohen nga natyra e detyrës me të cilën përballet programuesi. Prandaj, çdo programues duhet të ketë në “bagazhin” e tij metodat e duhura për paraqitjen dhe kërkimin e të dhënave që mund të aplikohen në çdo situatë specifike.

Në fakt, strukturat e të dhënave në një kompjuter ndërtohen në bazë të llojeve bazë të të dhënave si "char", "integer", "real". Në nivelin tjetër janë vargjet, të cilat janë koleksione të llojeve bazë të të dhënave. Pastaj ka regjistrime, të cilat janë grupe të llojeve të të dhënave që aksesohen nga një prej të dhënave, dhe në nivelin e fundit, kur aspektet fizike të përfaqësimit të të dhënave nuk merren më në konsideratë, i kushtohet vëmendje renditjes në të cilën ruhen të dhënat dhe në të cilën kërkohet. Në thelb, të dhënat fizike shoqërohen me një "motor të dhënash" që kontrollon se si aksesohet informacioni në programin tuaj. Ekzistojnë katër "makina" të tilla:

1. kthesë;

3. lista e lidhur;

4. pemë binare.

1) http://ru. wikipedia. org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0 %BD%D0%BD%D1%8B%D1%85.

2) http://valera. *****/delphi/struct/okër. html.

3) http://www. *****/informatika/pascal/struktury_dannyh.

4) T. Kormen. Algoritmet. Ndërtimi dhe analiza. 2nd ed. Faqe 255

5) Detyrat dhe zgjidhjet http://*****/olimp/str_prb. php.

Grafikët janë si një grup objektesh me shumë lidhje.

Grafiku është një objekt matematikor abstrakt. Ai përbëhet nga kulme dhe skaje. Çdo skaj lidh një palë kulme. Nëse disa skaje lidhin të njëjtin çift kulmesh, atëherë këto skaje quhen të shumëfishta. Një skaj që lidh një kulm me vetveten quhet një lak. Ju mund të ecni përgjatë skajeve të grafikut, duke lëvizur nga një kulm në tjetrin. Në varësi të faktit nëse është e mundur të ecësh përgjatë skajit në të dy drejtimet, ose vetëm në një drejtim, dallohen përkatësisht grafikët e padrejtuar dhe të drejtuar. Skajet e orientuara quhen harqe. Nëse të gjitha skajet e një grafiku kanë një peshë (dmth., një numër që korrespondon në mënyrë unike me një skaj të caktuar), atëherë grafiku quhet i ponderuar. Kulmet e lidhura nga një skaj quhen fqinjë. Për një graf të padrejtuar, shkalla e një kulmi është numri i skajeve që përmban. Për një grafik të drejtuar, bëhet një dallim midis shkallës sipas hyrjes dhe shkallës sipas skajeve dalëse. Një grafik quhet i plotë nëse ka një skaj midis një çifti kulmesh të dallueshme.

Një grafik është një objekt abstrakt dhe ne mund ta interpretojmë atë në mënyra të ndryshme, në varësi të detyrës specifike. Konsideroni një shembull. Le të jenë kulmet e grafikut qytete, dhe skajet janë rrugët që i lidhin ato. Nëse rrugët kanë trafik njëkahëshe, atëherë grafiku është i orientuar, përndryshe i padrejtuar. Nëse rruga është me pagesë, atëherë grafiku peshohet.

Në letër, është e përshtatshme për të paraqitur një grafik duke përshkruar kulmet si pika dhe skajet si vija që lidhin çifte pikash. Nëse grafiku është i orientuar, duhet të vizatoni një shigjetë në vijat që specifikon drejtimin; nëse grafiku është i peshuar, atëherë në secilën skaj është gjithashtu e nevojshme të futni një numër - pesha e skajit.

Ka disa mënyra për të paraqitur një grafik në kujtesën e kompjuterit. Lidhjet e mëposhtme me teorinë mund të gjenden më poshtë:

1. http://*****/sng/index. shtml

2. http://*****/sng/4/index. shtml

3. https://sites. /site/vzsitgnovosibirsk/distancionnye-kursy/distancionnyj-kurs-graf

4. http://libër. *****/10/grap1021.htm

5. http://ru. wikipedia. org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0 %B2

6. Detyrat dhe zgjidhjet http://*****/olimp/gra_prb. php

Probleme duke përdorur gjeometrinë analitike dhe bazuar në konceptin "vektor"

Gjeometria llogaritëse është një degë e shkencës kompjuterike që studion algoritmet për zgjidhjen e problemeve gjeometrike. Probleme të tilla lindin në grafikën kompjuterike, projektimin e qarqeve të integruara, pajisjet teknike, etj. Të dhënat fillestare në këto probleme mund të jenë një grup pikash, një grup segmentesh, një poligon, etj. Rezultati mund të jetë ose një përgjigje për disa pyetje (të tilla si "ndërpritet nëse këto rreshta"), ose ndonjë objekt gjeometrik (për shembull, shumëkëndëshi më i vogël konveks që përmban pikat e dhëna).

Në Informatikën nr. 14, u botua një artikull i njërit prej autorëve mbi problemet e gjeometrisë llogaritëse në olimpiadat në informatikë. Në veçanti, aty u formuluan një sërë nënproblemesh elementare, mbi të cilat bazohet zgjidhja e shumicës së problemeve të gjeometrisë llogaritëse. Megjithatë, klasat edhe me nxënës të shkollave të mesme të përgatitura mirë matematikisht treguan se zgjidhja e këtyre nëndetyrave u shkakton atyre vështirësi të mëdha. Detyra ose i ngatërron ata, ose metoda e zgjedhur "frontale" e zgjidhjes është aq e ndërlikuar sa studentët nuk mund ta kryejnë atë pa gabime. Analiza e rezultateve të zgjidhjes së problemeve "gjeometrike" në Olimpiadat Gjith-Ruse në Informatikë çon në të njëjtat përfundime. Duke përdorur lidhjet më poshtë, mund të studioni qasjet për zgjidhjen e problemeve gjeometrike në një aeroplan, të cilat ju lejojnë të merrni shpejt dhe me lehtësi zgjidhje për shumicën e nëndetyrave elementare.

1) http://*****/?page=lib_viewarticle&article_id=12.

2) http://*****/artikull. asp? id_sec=1&id_text=1332.

3) Detyrat dhe zgjidhjet http://*****/olimp/geo_prb. php

Problemet e programimit dinamik.

Shumë probleme të olimpiadave, si dhe probleme të programimit praktik, janë detyra për klasifikimin e opsioneve dhe zgjedhjen midis këtyre opsioneve të pranueshme ose më të mirë sipas një ose një kriteri tjetër. Megjithatë, për shkak të numrit të tyre jashtëzakonisht të madh, shpesh nuk është e mundur të merren parasysh të gjitha opsionet.

Për fat të mirë, për një numër problemesh që janë të ngjashme në formulim me problemet që kërkojnë vërtet një numërim të plotë të opsioneve, mund të gjendet një zgjidhje shumë më efikase. Më shpesh, në raste të tilla, zgjidhja zbret në gjetjen e zgjidhjeve për nënproblemet e dimensionit më të ulët, të cilat ruhen në një tabelë dhe nuk rillogariten kurrë, dhe nëndetyrat e dimensionit më të lartë përdorin këto zgjidhje të gjetura tashmë. Kjo metodë quhet programim dinamik, quhet edhe metoda e tabelës. Në një formë të përgjithshme, programimi dinamik kuptohet si një proces i zgjidhjes hap pas hapi të një problemi optimizimi, në të cilin në çdo hap, nga një grup zgjidhjesh të realizueshme, zgjidhet një që optimizon një objektiv ose funksion kriteri të caktuar. Ndonjëherë, në vend të atij të optimizmit, problemi i numërimit të numrit të zgjidhjeve të pranueshme zgjidhet me të njëjtën metodë. Në këtë rast, në çdo hap, në vend të zgjedhjes së zgjidhjes optimale, përmblidhen zgjidhjet e nënproblemave me dimension më të vogël, dhe formulimi i tyre jo gjithmonë përputhet plotësisht me problemin origjinal (shembuj përkatës do të shqyrtohen më poshtë). Në të dyja rastet, zgjidhja e gjetur në hapin aktual zakonisht futet në një tabelë. Si rregull, marrëdhënia midis detyrave dhe nën-detyrave formulohet si një "parim i caktuar i optimizmit" dhe shprehet nga një sistem ekuacionesh (marrëdhënie periodike).

Bazat e teorisë së programimit dinamik u hodhën nga R. Bellman. Vini re se fjala programim në titullin e mësipërm (programim dinamik), si dhe në "programim linear" (programim linear) nuk nënkupton kompilimin e programeve për një kompjuter.

Për të zgjidhur një problem optimizimi në të cilin kërkohet të ndërtohet një zgjidhje me vlerën maksimale ose minimale (optimale) të disa parametrave, një algoritëm i bazuar në programimin dinamik mund të formulohet si më poshtë:

1) identifikoni dhe përshkruani nëndetyrat, përmes zgjidhjes së të cilave do të shprehet zgjidhja e dëshiruar,

2) shkruani marrëdhënie rekursive (ekuacione) që lidhin vlerat optimale të parametrit për nëndetyrat,

3) llogarit vlerën optimale të parametrit për të gjitha nëndetyrat,

4) ndërtoni zgjidhjen më optimale duke përdorur informacionin e marrë.

Nëse ne jemi të interesuar vetëm për vlerën e parametrit, atëherë hapi 4 në algoritëm nuk është i nevojshëm (kjo situatë është tipike, për shembull, për problemet e numërimit të numrit të opsioneve të pranueshme ose disa konfigurimeve, përfshirë ato kombinuese). Sidoqoftë, nëse është e nevojshme të ndërtohet zgjidhja më optimale, ndonjëherë është e nevojshme të merren dhe ruhen informacione shtesë gjatë ekzekutimit të hapit 3 të algoritmit. Shpesh, është hapi 4 që rezulton të jetë më i vështiri kur zbatohen algoritme të tilla.

1) http://*****/blogs/algorithm/113108/.

2) http://www. *****/Olympiads/Rules_Olympiads/Rules21.htm.

3) http://*****/tag/%D0%B4%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81 %D0%BA%D0%BE%D0%B5%20%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8 %D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5/

4) Detyrat dhe zgjidhjet http://*****/olimp/rec_prb. php

INSTITUCIONI ARSIMOR KOMUNAL - SHKOLLA E MESME ARSIMORE MUZHEVSKAYA ME EMËR N.V. ARKHANGELSKY

"Olimpiadat në Informatikë: Metodat e Përgatitjes"

Materiali i përgatitur:

IT-mësues

Galitskaya Irina Viktorovna

Problemet me të cilat përballet mësuesi:

· Studimi i formave të reja të zhvillimit të olimpiadave.

· Njohuri të algoritmeve për zgjidhjen e problemave të olimpiadës.

Prania e vetë detyrave.

· Njohuri të gjuhëve programuese.

· Koha për të studiuar, korrigjuar dhe testuar detyrat.

Mësimi i nxënësve për organizimin e duhur të aktiviteteve në Olimpiadë.

Shumica e mësuesve nuk mund ta bëjnë këtë. Mënyra më e saktë në këtë situatë është rritja e lidhjeve mes shkollës dhe universitetit.

Këtu janë disa veçori të përgatitjes së nxënësve për programimin e Olimpiadës:

1. Në kurrikulën shkollore nuk ekziston një lëndë e tillë “programim”. ato. kursanti duhet të ketë motivimin e tij, mjaft të fortë.

2. Ekziston një kufizim që gjatë zgjidhjes së problemeve është e dëshirueshme të përdoret vetëm një nga gjuhët e programimit (SI ose PASCAL).

3. Stërvitjet e rregullta janë pothuajse në nivel sportiv.

4. Shpenzim i madh kohe, kohëzgjatja e Olimpiadës me analiza shpesh i kalon 6 orë.

5. Algoritmet dhe formulat që përdoren në zgjidhjen e shumicës së problemeve studiohen vetëm në universitete.

Sigurisht, trajnimi i nivelit më të lartë është gjithashtu i nevojshëm që mësuesit të punojnë me studentë të talentuar që marrin pjesë në garat e programimit:

· Mundësisht një arsim i dytë, universitet i specializuar në programim.

· Kurse gjuhe programimi, kurse programimi olimpiada.

· Vetë-përgatitje duke përdorur materiale nga burime shtesë.

Por edhe njohja e mirë e një gjuhe programimi nuk jep një garanci 100% që një nxënës do të fitojë edhe në një olimpiadë shkolle apo rrethi.

Ideja pedagogjike e përvojës

Motivimi është stimuli kryesor për pjesëmarrjen në olimpiada për një nxënës. Një mundësi për të treguar njohuri dhe erudicion mbi problemin që zgjidhet.

Një nga forcat drejtuese kryesore për pjesëmarrjen e nxënësve në garat e programimit është dëshira dhe interesimi i mësuesit, si dhe ndihma, durimi dhe besimi i prindërve.

Në vitin 1964, V. Vroom propozoi "teorinë e pritshmërisë". Ai besonte se nxitja për punë efikase dhe me cilësi të lartë varet nga një kombinim i tre faktorëve - pritjet njerëzore:

1. Pritshmëria se përpjekjet do të çojnë në rezultatin e dëshiruar.

2. Pritshmëria se rezultatet do të çojnë në shpërblime.

3. Pritja se shpërblimi do të jetë me vlerë të mjaftueshme.

Sa më i madh të jetë besimi i personit se të gjitha këto pritshmëri do të realizohen, aq më i fortë do të jetë nxitja për të punuar. E ndryshova paksa formulimin e V. Vroom-it në një kontekst edukativ dhe ja çfarë ndodhi.

Teoria e pritshmërisë thekson se çfarë duhet të bëjnë mësuesit në mënyrë që të kenë stimuj të fortë për studentët për të mësuar:

· Mësojini nxënësit të marrin rezultatet e kërkuara dhe krijoni të gjitha kushtet e nevojshme për këtë.

Vendosni një lidhje të drejtpërdrejtë midis rezultateve të punës dhe vlerësimit të studentëve.

· Hulumtoni nevojat e studentëve për të ditur se cilat shpërblime kanë vlerë për ta.

Mbi këtë bazë, mekanizmat e motivimit dhe faktorët kryesorë të efektivitetit të stimujve mund të shprehen si:

1. Njohuri nga mësuesit për nevojat, interesat, nevojat e nxënësve.

2. Krijimi i një lidhjeje të drejtë të drejtpërdrejtë ndërmjet rezultateve dhe shpërblimit.

3. Urgjenca e shpërblimit.

4. Shkalla e kënaqësisë së pritjeve.

Përjetoni teknologjinë

Sigurisht, përgatitja për Olimpiadat është një proces i gjatë dhe i mundimshëm.

Përdorimi i parimit "Ajo që fituat është ajo që morët" ju lejon të krijoni një nevojë për të rritur aktivitetin njohës të studentëve, vetë-shprehjen dhe interesin e tyre për aktivitetet mësimore produktive, dëshirën për të demonstruar arritjet e tyre.

Zbatimi i përvojës

Interesi për "programimin e olimpiadës" mund të zgjohet në shumë mënyra. Mënyra më e mirë është zgjerimi i njohurive për kompjuterin, llogaritjet kompjuterike, futja e konstruksioneve algoritmike në klasat e shkencave kompjuterike dhe integrimi pasues me një zgjidhje më të ngushtë problemi në një gjuhë programimi specifike.

Hapi i parë. Përgatitore. Klasat zhvillohen në formën e një loje. Një grup komandash po prezantohet gradualisht, gjë që bën të mundur përfshirjen e mjeteve llogaritëse në zgjidhjen e problemeve. Mjafton të përshkruhet algoritmi në çdo gjuhë programimi.

Hapi i dytë. Fillimi i programimit dhe gjatë orëve në vijim prezantohen metoda të ndryshme të zgjidhjes së problemeve duke përdorur algoritme standarde të implementuara në gjuhën e programimit. Prezantohet koncepti i "debugimit të një programi". Është e këshillueshme që të merren parasysh disa zgjidhje në mënyrë që përfundimisht t'u mësohen studentëve elementet e kërkimit optimal.

Hapi i tretë. "Reflektimi i mësimdhënies". Nxënësi u mëson të tjerëve zgjidhjen e problemeve. Kjo zakonisht ndodh kur analizoni detyrat. Kjo e ndihmon studentin të përcaktojë shenjat e optimalitetit (shkurtësia, qartësia), të mësojë të gjurmojë dhe shpjegojë qartë punën e programit.

Hapi i katërt. Ajo rrjedh nga e dyta dhe e treta me ndërlikim të mëvonshëm të detyrave dhe mjeteve për zgjidhjen e tyre. Në këtë fazë, është veçanërisht e rëndësishme përfshirja e mësuesve të universitetit ose kërkimi i detyrave më komplekse që kontribuojnë në zhvillimin e të menduarit logjik, imagjinativ dhe zhvillimin e aftësive kombinuese.

Hapi i pestë. "Reflektim krijues". Hartimi nga studenti i problemave me zgjidhjen e autorit, me teste, kërkesa hyrëse dhe dalëse.

Arritja më e lartë e zotërimit: krijimi dhe aplikimi i teknologjive të të mësuarit të shpikura nga vetë nxënësit për të mësuar të tjerët.

Efikasiteti

Metodologjia e përgatitjes për olimpiadat e programimit mund të përdoret për të zgjidhur problemet me të cilat përballen mësuesit e shkencave kompjuterike që përgatitin pjesëmarrësit në olimpiada dhe studentët që marrin pjesë në olimpiada. Metodologjia e propozuar nuk është një ilaç, por do të ndihmojë jo vetëm në përgatitjen për olimpiadën rajonale, por edhe për olimpiadat e nivelit më të lartë.

Ka shumë programe dhe teste në internet që kryejnë funksionet e mësimit në distancë dhe mësuesit i përdorin ato për të përgatitur nxënësit për olimpiada. Por! Ndonjëherë, për shkak të shpejtësisë dhe cilësisë së komunikimit, është e pamundur të marrësh pjesë në garat e programimit online. Shpesh një student nuk e njeh standardin e ndërfaqes për paraqitjen e detyrave, dhe për të korrigjuar detyrën dhe për të marrë rezultatin, duhet të rihyni në sitin e Olimpiadës. Verifikimi dhe analiza e detajuar e rezultateve kërkon kohë shtesë. Instalimi i një sistemi të tillë serveri në një klasë është mjaft i mundimshëm. Dhe në kompjuterin e shtëpisë së studentit për momentin është pothuajse e pamundur. Jo të gjithë mësuesit e shkencave kompjuterike i dinë rregullat për futjen dhe nxjerrjen e të dhënave përmes një skedari teksti kur dërgojnë dhe marrin vendime nëpërmjet internetit.

Aktualisht, janë zhvilluar shumë metoda të mësimdhënies së informatikës. Por, përkundër faktit se programimi dhe algorithmizimi mund të kombinohen kur studioni shkenca kompjuterike, zgjidhja e problemeve të olimpiadës së programimit kërkon një qasje krejtësisht të ndryshme.

Kur punoni me studentë në përgatitje për Olimpiadat, për të konsoliduar aftësitë, kërkohet të zgjidhen në mënyrë të përsëritur probleme të një lloji të caktuar. Në të njëjtën kohë, mësuesi mund t'ua lëshojë detyrën studentëve në shtëpi në formë elektronike (lidhje me sitin, në arkiv), dhe studentët, pasi kanë zgjidhur problemet, e sjellin zgjidhjen e tyre në një bartës dhe e dorëzojnë për verifikim. . Pas kësaj analizohen detyrat në grup, nxënësit tregojnë mënyrat e zgjidhjes së problemeve.

Në fazat e ardhshme të punës, detyrat bëhen më të vështira.

Problemi i mbingarkesës psikologjike dhe fizike

Nxënësit që marrin pjesë në olimpiada dallohen për kapacitetin e tyre të lartë për punë, dhe ndonjëherë mësuesit, duke e parë këtë, fillojnë të ngrenë gradualisht shiritin e kërkesave dhe notave. Por kur përgatitet për olimpiada të çdo niveli, jo vetëm në programim, një student duhet të punojë shumë dhe fort edhe në shtëpi, në mësime dhe aktivitete jashtëshkollore, edhe në fazat fillestare. Një nxënës mëson shumë tema të lëndëve shkollore në nivelin bazë me një ritëm të përshpejtuar vetëm falë zellit, kapacitetit të madh të punës, me ndihmën e mësuesve dhe prindërve. Detyra e mësuesve dhe e administratës është të mos e kalojnë kufirin në lëndët e tjera për periudhën e përgatitjes. Prandaj kërkohet kontroll dhe mbështetje jo vetëm nga prindërit, por edhe nga mësuesit, ndonjëherë edhe ndihmë dhe mirëkuptim nga administrata.

Një plan, rendi i temave të studiuara, i cili do t'ju ndihmojë të mësoni se si të zgjidhni problemet e Olimpiadës ose të gjeni boshllëqe në njohuritë tuaja.

Seksioni 1. Bazat matematikore të programimit

Seksioni 2. Teknika e programimit

1. Bazat e gjuhës së programimit (Pascal, C) Variablat dhe llojet e thjeshta të të dhënave, madhësitë e llojeve. Programet lineare. Deklarata të kushtëzuara. cikle. procedurat dhe funksionet. Llojet komplekse të të dhënave (vargje, vargje, rekorde, tregues, skedarë).

2. Vargjeve Vargjeve njëdimensionale. Vargje (matrica) dydimensionale. Vargjet shumëdimensionale.

3. Linjat. Elemente të analizimit leksikor dhe sintaksor Veprimet në vargje. Shenjat, duke numëruar argumente të llojeve të ndryshme. Nxjerrja e numrave nga një varg.

4. Puna me skedarë Leximi dhe shkrimi në një skedar teksti. Konvertimi i të dhënave të marra nga skedari në një strukturë të përshtatshme. Puna me skedarë të shtypur. skedarë të pashtypshëm. Buferimi i hyrjes.

5. Rekursion Funksionet matematikore të dhëna rekurzive. Shembuj të rutinave rekursive. Problemi i ndalimit të rekursionit. Zëvendësimi i rekursionit me përsëritjen.

6. Aritmetikë "Long" Ruajtja e numrave në program që nuk përshtaten në llojet standarde. Veprimet aritmetike në numrat "të gjatë". Numrat "të gjatë" me një pjesë dhjetore. Nxjerrja e një rrënjë me një saktësi të caktuar.

7. Ruajtja e informacionit në memorien dinamike. Ruajtja e një grupi të dhënash në lista lineare. Futja në një listë, fshirja nga një listë, kërkimi i një elementi në një listë. lista të lidhura dyfish. Konceptet e strukturave të të dhënave të stivit, unazës, radhës, kuvertës; zbatimin e tyre duke përdorur memorien dinamike. pemë binare. Pemë me një numër të pacaktuar fëmijësh. Ruajtja e vargjeve të mëdha.

Seksioni 3. Algoritmet, metodat dhe parimet për zgjidhjen e problemeve.

1. Koncepti i kompleksitetit të algoritmit. Përkufizimi i kompleksitetit.

2. Algoritmet e kërkimit dhe renditjes Kërkoni për një element në një grup të parregulluar. Kërkimi binar me çelës në një grup të renditur (dikotomia). Kërkimi Fibonacci. Kërkoni në një grup të renditur n-dimensionale. Gjetja e elementit k-të më të madh në një grup. Metoda të thjeshta renditjeje ("flluska", "zgjedh", "fut", "numëro"). Metodat e shpejta ("të shpejta", "bashkimi", "piramidale"), balancimi i pemëve binare. Renditja sipas metodës scoop.

3. Zgjidhja e problemave me numërimin e opsioneve Zbatimi i rekursionit për enumeracion. Gjenerimi i kombinimeve, vendosjeve, permutacioneve dhe grupeve Boolean. Numërimi i plotë. Krasitja zgjedhore (heuristika). Metoda e degës dhe e lidhur.

4. Gjeometria llogaritëse dhe metodat numerike Gjatësia e një segmenti. Ekuacioni i një drejtëze. Produkt skalar dhe vektor. Pika e kryqëzimit të segmenteve. Përkatësia e një pike me një figurë në një plan (për shembull: një trekëndësh). Zona e një shumëkëndëshi konveks. Trupi konveks i një grupi pikash: Graham, Jarvis, algoritme "përça dhe pushto". Çifti më i afërt i pikëve. Metoda e Gausit për zgjidhjen e një sistemi ekuacionesh lineare. Gjetja e një zgjidhjeje për një ekuacion.

5. Parimi i programimit dinamik Koncepti, zbatueshmëria. Krahasimi me numërimin.

6. Algoritmet e pangopur Koncepti, zbatueshmëria. Krahasimi me enumeracion dhe programim dinamik.

7. Teoria e grafikut. Algoritme në grafikë Koncepti i një grafi. Përkufizimet e teorisë së grafikëve. Strukturat e të dhënave për paraqitjen e një grafiku në një program. Algoritmet e përshkimit të grafikut (kërkimet e para të gjerësisë dhe thellësisë). Labirint (metoda e valës). Cikli i Euler-it. Rruga më e shkurtër në një grafik të peshuar (algoritmet e Dijkstra dhe Minty). Mbyllja e grafikut kalimtar (Algoritmi Floyd-Warshill). Pema me shtrirje minimale (algoritmet e Prim dhe Kruskal). Renditja topologjike e një grafi. Rrjedhat në rrjete (algoritmi Ford-Fulkerson). Përputhjet në një grafik dypalësh (metoda e zinxhirit të zgjatjes, zgjidhja e rrjedhës). Problemi i detyrës, caktimi i fytit të ngushtë (algoritmi hungarez). Lojëra me grafik. Grafiku i ngjyrosjes. Vendosja e një grafiku në një aeroplan. Lidhja e fortë dhe dylidhshmëria e grafikut. Izomorfizmi i grafikut. k-klikoni. Cikli Hamilton.

8. Analiza leksikore dhe sintaksore Detyra “Llogaritësi”. Diagramet sintaksore. Format Backus-Naur. Stack dhe model analizues rekurziv. Automata të fundme. Gramatikat.

9. Detyrat me një kthesë

Seksioni 4. Olimpiada në Informatikë

1. Rregulla për zhvillimin e olimpiadave të programimit

2. Gabimet tipike dhe programet e korrigjimit

3. Truket e Olimpiadës

Sipas mendimit tim, seksionet 2 dhe 3 kanë vlerën më të madhe. Ndërsa mësimi i një gjuhe programimi nuk duhet të jetë i vështirë për ju (ka një numër të madh librash për këtë temë), atëherë do të jetë më e vështirë me algoritme. Ka edhe shumë libra për këtë temë, por ato, më së shpeshti, janë shumë të mbingarkuara me teori, dhe në olimpiada nevojitet vetëm praktikë. Nga burimet elektronike mbi algoritmet, unë mund të rekomandoj librin nga SM Okulov dhe siti algolist.manual.ru, i cili synon më pak të studiojë "Olimpiadën e shkencave kompjuterike" sesa libri i Okulov, por përmban një numër të madh algoritmesh që nuk janë në libër, por që nuk ishin keq do ta dinim. Mësohuni të punoni në modalitetin: shkrimi + korrigjimi në Borland Pascal/Borland C++ dhe kompilimi (me një ndryshim paraprak të konstanteve) në Free Pascal/GNU C. Përpiluesit e rinj 32-bit nuk kanë një kufi memorie të vështirë dhe punojnë shumë më i shpejtë (ndryshimi në shpejtësinë e ekzekutimit të programeve 16 dhe 32-bit në P4). Një taktikë e tillë dinak shpjegohet me mungesën e një korrigjuesi të mirë në platformat e reja dhe pajtueshmërinë e tyre pothuajse të plotë me përpiluesit Borland (në FP, mos harroni të mbyllni skedarin e daljes).

Përgatitja e studentëve për Olimpiadën e Informatikës. Programi i përgatitjes individuale për fazën komunale të Olimpiadës Gjith-Ruse për nxënësit e shkollës në lëndën "Informatikë dhe Plani TIK për përgatitjen për Olimpiadën në Informatikë"

Një shkrim nga mësuesja e Liceut nr.8 të OEIT Pangina N.N. nga revista "Mjetet Kompjuterike në Arsim", N1, 2000

Përgatitja e nxënësve për olimpiada në Informatikë.

Ky artikull, si dhe burimet e mëposhtme.

Artikujt kryesorë të lidhur