Priprema učenika za informatičku olimpijadu. Program individualne pripreme za opštinsku etapu Sveruske olimpijade za školsku decu iz predmeta "Informatika i IKT" Plan pripreme za informatičku olimpijadu

Analiza zadataka olimpijskog karaktera.

Metode pripreme za regionalnu etapu Sveruske olimpijade za učenike informatike.

Materijali za majstorsku klasu (prezentacija)

na RMO nastavnici informatike.

nastavnici informatike i IKT

MOU "Licej №23"

Shuvalova Svetlana Yurievna.

U ovom radu sumirani su materijali koje sam prezentovao na RMS nastavnika informatike 2011., 2012. nakon rezultata školskih faza Sveruske olimpijade za školsku decu iz informatike.

Broj učesnika olimpijade za školarce iz programiranja svake godine se smanjuje, zbog smanjenja udjela sati na sadržajnoj liniji „Algoritmizacija i programiranje“ u nastavnom planu i programu školskog predmeta informatika. Olimpijade su osmišljene da identifikuju najdarovitiju djecu u oblasti informatike, razviju njihove sposobnosti i povećaju interesovanje za predmet. Oni omogućavaju školarcima da dobiju rano vođenje karijere, što doprinosi budućem formiranju ruskih stručnjaka u oblasti računarstva, računarske tehnologije i programiranja. Ali dobro poznavanje školskog kursa informatike ne garantuje uspešan nastup na olimpijadi, potrebno je da se sa učenicima bavite i van nastave.

slajd 1.

Cilj informatičke olimpijade jepromovirati potragu za najdarovitijim učenicima.

Važna karakteristika zadataka koji se koriste tokom školske i opštinske faze je njihova orijentacija da testiraju razvoj teorijskog mišljenja, logike, kao i kreativnosti i intuicije učenika.

Zadaci školske faze olimpijade trebali bi biti toliko složeni da ne uplaše učenike, već da im daju priliku da pokažu svoje najbolje kvalitete.

Slajd 2.

Glavni kriterijumi za odabir olimpijskih zadataka za školske i opštinske faze Sveruske olimpijade za školsku decu iz informatike:

• originalna formulacija problema (ili ideja njegovog rješenja);
• u tekstu uslova zadatka ne bi trebalo da postoje pojmovi i pojmovi koji prevazilaze predmete koji se izučavaju u okviru osnovnog nastavnog plana i programa;
• zadatak mora biti nedvosmisleno definisan;
• zadatak ne bi trebao zahtijevati posebno znanje za njegovo rješavanje;
• formulacija problema treba da podrazumeva prisustvo faze formalizacije u njegovom rešavanju;
• Zadatak mora biti razumne složenosti i radnog intenziteta.

Slajd 3.

Olimpijski zadaci za školske i opštinske etape informatičke olimpijade odlikuju se tematskom raznolikošću.

Iz iskustva olimpijada moguće je izdvojiti najčešćesekcije informatike,kojima se predmet zadataka može pripisati:

• kombinatorika;
• sortiranje i pretraživanje;
• obrada sekvence;
• grafski algoritmi;
• elementi računske geometrije.
• nabrajanje opcija i metoda njegovog smanjenja;
• dinamičko programiranje.

slajd 4.

Faze rješavanja olimpijskih zadataka:

• Analiza uslova problema.
• Formalizacija uslova problema.
• Izrada algoritma za rješavanje problema.
• Softverska implementacija algoritma.
• Otklanjanje grešaka i testiranje programa.
• Dostavljanje rješenja na uvid.

Slajd 5.

Važno je to napomenutitekst zadatka uvek treba pažljivo pročitatiod početka do kraja, budući da se ključni uslov može sakriti, na primjer, u formatu ulaznih ili izlaznih podataka, kao iu primjerima datoteka ulaznih i izlaznih podataka.

Prilikom izrade programa posebnu pažnju treba obratiti i na opisformat ulaznih i izlaznih podatakadato u stanju problema. Imena ulaznih i izlaznih datoteka su također opisana u navodu problema, a njihov netačan pravopis u programu smatra se greškom.

Morate imati na umu kada pišete program dačuvanje uređenih fajlova tokom turneje.

Rezultirajući program mora odgovarati datomdimenzije ulaznih podatakai zadovoljiti ograničenja namemorija i vrijeme radanavedeno u problemskom stanju.

slajd 6.

Uobičajene greške:

• Format unosa/izlaza podataka ne odgovara uslovu zadatka

• Nisu razmotreni svi mogući slučajevi

• Nevažeći tip podataka (dimenzija)

• Gubitak uređenih fajlova tokom obilaska

Slajd 7.

Minimalna baza znanja za informatičku olimpijadu.

Programski jezik:

• osnovne algoritamske strukture,
• standardne matematičke funkcije,
• procedure i funkcije za rukovanje string varijablama,
• procedure i funkcije za rad sa nizovima.

Tipični algoritmi.

slajd 8.

Zadaci na olimpijadama iz informatike ne odgovaraju uvijek „Standardu za osnovno i srednje (potpuno) opšte obrazovanje iz informatike i IKT“. Štaviše, kao rješenje ovih problema na olimpijadi je potrebno predstaviti debagovane programe napisane programskim jezikom visokog nivoa, a ne opise algoritama.

Stoga, prema rezultatima olimpijada, nije ispravno vrednovati rad pojedinog nastavnika informatike, jer program školskog predmeta informatika ne može obuhvatiti sve teme čije bi proučavanje moglo poboljšati rezultate nastup školaraca na olimpijadama.

slajd 9.

Internet resursi za pripreme za informatičke olimpijade:

http://algolist.manual.ru/

Analiza problematike školskog kola Olimpijade 2011.

Zadatak br. 1 "Snimanje muzike" (15 bodova)

Proverite da li će muzička kompozicija koja traje m minuta i n sekundi stati na disk računara, da li je slobodan prostor na disku 6 megabajta, a za snimanje jedne sekunde zvuka potrebno je 16 kilobajta.

Algoritam rješenja:

Korištenje formule za izračunavanje i uvjetnog operatora

Zadatak #2 "Kombinovano sigurno zaključavanje"(20 bodova)

Od 10 slova, potrebno je da birate 3. Ponavljanje slova je prihvatljivo. Izbrojite broj mogućih kombinacija kodova.

Algoritam rješenja:

Problem kombinatorike. Da bi se to riješilo, potrebno je primijeniti tipičan algoritam za formiranje grupa plasmana s ponavljanjima. Koriste se ugniježđene petlje.

Zadatak #3 "Pravougaonik"(30 bodova)

Na ravni je N pravougaonika. Svaki pravougaonik je zadan koordinatama donjeg lijevog i gornjeg desnog vrha. Odredite da li pravokutnici imaju zajedničku površinu

Algoritam rješenja:

Ako je maksimalna X-koordinata donjih lijevih vrhova pravokutnika manja od minimalne koordinate gornjih desnih vrhova, a maksimalna Y-koordinata donjih lijevog vrha pravokutnika je manja od minimalne koordinate gornjih desnih vrhova , tada je ukupna površina.

Koristi se tipičan algoritam za pronalaženje maksimalnog (minimalnog) elementa niza.

Zadatak #4 "Magični kvadrat"(35 bodova)

U kvadrat od 3x3 ćelije stavite brojeve 1, 2, ..., 9 tako da su zbroji brojeva u svakom redu, koloni, u svakoj dijagonali jednaki.

Algoritam rješenja.Problem je kako popuniti dvodimenzionalni niz.

(indijski način):

1. U sredinu gornje linije stavljamo 1 , u posljednjem redu kolone koja je susjedna desno 2 .
2. Sljedeći brojevi se postavljaju u dijagonalnom smjeru.
3. Došavši do desne ivice kvadrata, prelaze u najlijevu ćeliju najbliže linije iznad.
4. Došavši do gornje ivice kvadrata, idu u najnižu ćeliju kolone koja je susjedna s desne strane. Bilješka. Kada dođete do ćelije u gornjem desnom uglu, idite u donji lijevi.
5. Došavši do već zauzete ćelije, prelaze u ćeliju koja leži direktno ispod posljednje popunjene ćelije.
6. Ako je posljednja popunjena ćelija u donjem redu kvadrata, idite na najgornju ćeliju u istoj koloni.

Analiza problematike školskog kola Olimpijade 2012. godine.

Zadatak 1.

Ispišite sve trocifrene decimalne brojeve čiji je zbir cifara jednak datom broju.

Algoritam rješenja:

Jedno od brutalnih rješenja:

var a,b,c,n,k:integer;

početi

write("n="); readln(n);

za a:=1 do 9 do

Za b:=0 do 9 uradi

Za c:=0 do 9 uradite

Ako je a+b+c=n onda

početi

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

k:=k+1;

kraj;

Writeln;

WriteIn("k=",k) ;

Writeln;

kraj.

Drugo brutalno rješenje:

Var a,b,c,n,k,m: cijeli broj;

početi

write("n="); readln(n);

za m:=100 do 999 do

početi

c:=m mod 10;

b:= m div 10 mod 10;

a:= mdiv 100;

ako je a+b+c=n onda

početi

pisati (m:5);

k:=k+1;

kraj;

kraj;

writeln("k=",k)

kraj.

Zadatak 2. "Kid i Karlson".

Klinac i Carlson žive u pravougaonoj sobi veličine A x B . Kako mogu izračunati koliko kvadratnih prostirki ima stranu OD da potpuno pokrije pod prostorije? (Kid i Carlson ne mogu ni dijeliti ni množiti.) Napišite program za rješavanje ovog problema.

Algoritam rješenja:

U vanjskoj petlji na jednoj strani sobe (whilep ) rezervišite prostor za seriju ( p:=p+s ), zatim u unutrašnjoj petlji s druge strane (dok je m ) provjeravamo koliko prostirača može zatvoriti red, operater m:=m+s rezerviše prostor za prostirku i operatera kovrik:=kovrik+1 broji ukupan broj položenih prostirki.

var a, b, c, kovrik, m, p: cijeli broj;

početi

readln(a, b, c);

kovrik:= 0;

p:= 0;

whilep

početi

p:= p + c;

m:= 0;

dok je m

početi

m:= m + c;

kovrik:= kovrik + 1

kraj;

pisanje (kovrik)

kraj.

Zadatak 3. "Bakterije".

Kolonija se sastojala od n bakterije (ne više od 30.000). U njega je ušao virus koji je u prvoj minuti uništio jednu bakteriju, a potom se podijelio na dva nova virusa. U isto vrijeme, svaka od preostalih bakterija također se podijelila na dvije nove. Sljedeće minute pojavila su se dva virusa koji su uništili dvije bakterije, a onda su se svi virusi i bakterije ponovo razdvojili i tako dalje. Hoće li ova kolonija živjeti beskonačno ili će izumrijeti?

Vaš program mora:

• Zatražite broj bakterija n
• Saznajte i izvijestite: nakon koliko dana, sati i minuta će kolonija bakterija prestati postojati ili izdajte poruku da je kolonija vječna.

Primjer odgovora: Za n=A. Odgovor je B dana C sati D minuta (gdje su A, B, C, D numeričke vrijednosti).

Algoritam rješenja:

Program u programskom jeziku Pascal.

Var a, b, c: shortint;

t, n, v: longint;

početi

Write('Početna veličina kolonije -"); readln(n);

v:=1;

dok n>0 radi

Počni

t:= t + 1; (minuta)

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

v:= v * 2; (virusi)

kraj;

a:=tdiv 1440;

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

c:= t - a - b;

Napišite ("Kolonija će prestati da postoji za ",a, "dane", b, "sate", c, "minuta");

kraj.

Zadatak 4.

Dat je pravougaonik sa stranicama A i B, gdje su A, B prirodni brojevi. Od njega počinjemo odsijecati kvadrate (slika 1). Koliko se takvih kvadrata može odsjeći ako se svaki put odsiječe najveći kvadrat?

Algoritam rješenja:

1 način.

Da bismo riješili ovaj problem, potrebne su nam funkcije MAX i MIN , koristimo potprograme-funkcije da ih odredimo.

predstavimo se:

• pomoćne varijable X i Y (Y>=X) , što odgovara opadajućim stranicama pravokutnika;
• pomoćna varijabla D , koji određuje smanjenje veličine pravokutnika nakon sljedećeg odsjecanja najvećeg kvadrata čija je stranica kao X:=MIN(D,X).

Organizujemo ciklus u kojem je strana Y smanjuje svaki put MIN(D, X) dok ne ostane zadnji kvadrat, ili Y neće biti manji x. U potonjem slučaju, preimenujte stranice preostalog pravokutnika kao Y:=MAX(D,X) i X:=MIN(D,X) i nastavite ciklus.

Program u programskom jeziku Pascal.

var a, b, d, k, x, y: cijeli broj;

funkcija min(i, j: cijeli broj): cijeli broj;

početi

ako ja

min:=j

kraj;

funkcija max(i, j: cijeli broj): cijeli broj;

početi

ako ja

ostalo max:=i

kraj;

početi

ponovi

Writeln("vvedite dva naturalnix chisla");

readln(a,b);

dok (a>0) i (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

dok x y radi

početi

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

kraj;

Writeln("iskomoe čislo kvadratov:", k)

kraj.

2 way.

Problem se može riješiti korištenjem standardnih funkcija PASCAL : Y DIV X i Y MOD X, koristeći Euklid algoritam.

Algoritam rješenja:

Organiziramo ciklus u kojem formiramo ostatke od dijeljenja r 0 , r 1 , r 2 ,..., r n , r n+1 sve dok jedan od ovih ostataka ne bude jednak nuli rn+i =0 . Dakle, gradimo funkciju za generiranje ostatka podjele r n+i = r n mod r n-i , gdje je r 0 = A i r i =B . Za isti sistem ostataka možemo izbrojati koliko puta ostatak savršeno odgovara r n-i do r n .

(Euklidov algoritam)

var A, B, R0, R, R1, K: cijeli broj;

početi

ponovi

Write ("UNESITE PRIRODNI BROJ A = ");

readln (A);

Napišite ("UNESITE PRIRODNI BROJ U

readln(B);

sve dok (B > 0) i (A > 0) i (A >= B);

R0:= A;

R1:= B;

K:= R0 div R1;

dok R0 mod R1 0 radi

početi

R:= R0 mod R1;

R0:=R1;

R1:=R;

K:= K + R0 div R1

kraj;

Writeln ("ŽELJENI BROJ KVADRATA K = ", K);

Članak nastavnika OEIT Liceja br. 8 Pangine N.N. iz časopisa "Računarski alati u obrazovanju", N1, 2000

Priprema učenika za olimpijade iz informatike.

Olimpijade iz informatike su u suštini programske olimpijade. Rješavanje olimpijskih zadataka je potpuno samostalna nastavna sekcija sa obimnim teorijskim i praktičnim dijelovima.

Već šest godina na bazi škole-liceja broj 8 u Sosnovom Boru, školarci se pripremaju za olimpijade na različitim nivoima. Već pet godina učenici liceja su pobjednici regionalnih takmičenja u programiranju, učesnici i pobjednici Sveruskih olimpijada.

Rješenja olimpijskih zadataka gotovo svih faza olimpijada, od regionalnog do međunarodnog nivoa, zasnivaju se na dobro definisanim algoritmima, nadaleko poznatim u matematici i računarstvu. A da biste uspješno riješili olimpijske probleme, morate prije svega savladati ove algoritme, vidjeti ih i vješto ih primijeniti u predloženim zadacima, a ako ne znate, onda ih možete smisliti, izmisliti. Ali upoznavanje s ovim algoritmima najčešće se događa samo na fakultetu, i to je sasvim razumljivo, jer razvoj ovih algoritama zahtijeva poznavanje nekih dijelova više matematike.

pitanje 1. Pa da li je moguće pripremiti školarce za olimpijade?

Moguće je, ali ne u okviru osnovnog programa.

Štaviše, gotovo je neophodan uslov da ovi učenici dodatno studiraju matematiku (bolje je da su to odeljenja sa detaljnim proučavanjem matematike). Nije slučajno da su naši ruski izuzetni školarci u oblasti informatike bili podjednako uspješni u matematici:

Viktor Bargačev, dvostruki apsolutni svjetski prvak u informatici među školarcima, pobjednik je Međunarodne matematičke olimpijade (srebrna medalja);

Nikolaj Durov, 4-struki pobjednik Međunarodnih informatičkih olimpijada (3 srebrne i jedna zlatna medalja), vlasnik je dvije zlatne medalje na Međunarodnim olimpijadama iz matematike;

Vladimir Martjanov iz Nižnjeg Novgoroda (dvostruki apsolutni prvak svijeta u informatici) bio je pobjednik zonskih ruskih olimpijada iz matematike i fizike.

U Lenjingradskoj oblasti, može se navesti kao primjer Stratonnikov Aleksej, Potapov Aleksej, Ananijev Artem, Pangin Andrej.

Pitanje 2 . U kom uzrastu učenici treba da počnu da se pripremaju?

Što prije to bolje, ali u granicama razumnog.

Za nivo

dovoljno je započeti regionalne olimpijade od 7. do 8. razreda;

Preporučljivo je započeti ruske olimpijade od 5. do 6. razreda.

Primjer: prvak Moskve u programiranju među školarcima 1998. godine, Petr Mitričev, učenik 7. razreda, bio je i najmlađi učesnik 9. Sveruske olimpijade za školarce iz informatike i učesnik kampova za pripremu ruskog tim za međunarodnu olimpijadu.

Pitanje 3 . U kom obliku treba održavati nastavu u pripremi za olimpijade?

U obliku izbornih ili specijalnih predmeta.

Da bi se učenik dobro pripremio, da se izrazim dobro poznatom frazom, važno je, prije svega, „ne samo napuniti čašu znanja, već i zapaliti baklju“. Drugim riječima - da ulije interes!

Prema iskustvu našeg liceja, tome doprinosi:

Interdisciplinarne veze igraju važnu ulogu.

Licej već petu godinu izvodi specijalni kurs "Matematika na računaru" za 5-6 razred. Učenici se u vizuelnom obliku upoznaju sa matematičkim konceptima (na primjer, animirano skeniranje kocke, koordinatna ravan s cjelobrojnom mrežom), uče kreativno pristupiti rješavanju standardnih problema (na primjer, korištenjem grafičkog prikaza problema transfuzije i vaganja). na računaru).

Razvijanje interesovanja olakšavaju lekcije na temu "Modeliranje kretanja" od najjednostavnijeg kretanja bilijarske lopte do složenog uzorka linija jačine električnog polja dva naelektrisanja. Posebno impresivna je simulacija na kompjuteru „leta papirnatog aviona“ i demonstracija ovog leta u stvarnosti. Zanimljiv je i zadatak modeliranja kretanja satelita i određivanja prve, druge svemirske brzine, vremena leta rakete Vostok sa Jurijem Gagarinom oko Zemlje (ovaj događaj bi svi trebali znati!).

Takvi časovi se izvode diferencirano prema stepenu pripremljenosti učenika.

Tokom prve dve-tri nedelje letnjeg raspusta organizuje se školski kamp „Intelekt“ za 7-8 razrede, gde deca uče informatiku po posebnom programu.

Na primjer, program "Labirint" uključuje teme:

konstrukcija lavirinta (zanimljiv algoritam za generisanje slučajnog lavirinta različite složenosti);

kretanje po lavirintu pomoću kontrolnih tipki;

tražiti izlaz iz lavirinta, počevši od najjednostavnijeg prema pravilu lijeve ruke (držeći se na jednoj strani lavirinta);

potražite najkraći put u lavirintu.

Ovaj program podstiče učenike da razviju vlastite igre hodanja i pucanja. Glavna stvar je spoznaja da oni sami to mogu stvoriti!

Za desete razrede organizuje se letnja praksa u raznim preduzećima u Sosnovom Boru u trajanju od mesec dana. Studenti stiču vještine rješavanja praktičnih zadataka, učvršćuju svoja znanja o radu sa bazama podataka, računovodstvenim aplikacijama, samostalno kreiraju programe po uputama kustosa, stiču dodatna znanja (npr. pri radu sa računarskim mrežama, operativnim sistemom Unix). Priznanje preduzeća je uobičajen rezultat takvog rada.

Momci demonstriraju sopstvene programe na tradicionalnoj školskoj konferenciji informatike „Mi i računar“, ove godine je već šesta po redu. Najbolja softverska rješenja djeca svake godine predstavljaju na Međunarodnoj konferenciji „Školska informatika i problemi održivog razvoja“, održanoj u Sankt Peterburgu, gdje se rad djece ocjenjuje diplomama I i II stepena.

Kao edukativni materijal koriste se zasebni programi.

Za grupu „ljubitelja kompjutera“ u dobrom smislu, a ne u smislu, na primjer, kompjuterskih igrica, izvode se posebno usmjereni izborni predmeti i specijalni kursevi na teme: učenje dodatnog programskog jezika, algoritmizacija nestandardnih problema, olimpijski zadaci, teorija grafova itd.

Pitanje 4 . Koliko bi ljudi trebalo da bude u časovima posebno usmerenih izbornih predmeta?

Grupe od 6 – 12 osoba.

Kada radite za određeni rezultat (tj. pripremate se za gradsku, regionalnu ili rusku olimpijadu), grupa bi trebala biti od 3 do 6 ljudi. Ovi časovi se već obučavaju, a ovdje nastavnik više djeluje kao trener, a ne kao nastavnik. Kako ide lekcija?

To se zove tema.

Navedeni su zadaci na ovu temu.

Odabran je jedan od najpopularnijih ili najzanimljivijih zadataka.

Usmeno, zajedno s momcima, raspravlja se o algoritmu rješenja.

Momci pišu program, nastavnik popravlja vrijeme, ocjenjuje implementaciju rješenja, pomaže u pronalaženju grešaka, ukazuje na nedostatke u efikasnosti (broj operacija, korištenje RAM-a, vrijeme rješenja).

Pitanje 5 . Koje teme treba izučavati na časovima priprema za olimpijadu?

Nemoguće je sve predvidjeti, ali se mogu razlikovati sljedeće grupe algoritama:

Algoritmi nad cijelim brojevima.

Rekurzija.

Sortiranje.

Zadaci nabrajanja.

Geometrijski problemi.

Numeričke metode.

Statističko modeliranje.

Grafovi i stabla.

Transformacije teksta.

Razmotrimo detaljnije teme koje su potrebne za proučavanje u pripremi za olimpijade. Teorijska nastava treba da sadrži definicije, iskaze (u nekim slučajevima, obavezno sa dokazima).

Algoritmi nad cijelim brojevima

djeljivost

Prilikom proučavanja ove teme potrebno je dati definicije djelitelja, višekratnika, prostih i koprostih brojeva, dati iskaze sa dokazima o djeljivosti zbira i razlike dva broja, o djeljivosti proizvoda.

Prva modifikacija Euklidovog algoritma (sa oduzimanjem)

Uzastopnim smanjenjem brojeva (zamjenjujući veći s razlikom brojeva) dok ne postanu jednaki, dolazimo do najvećeg zajedničkog djelitelja ovih brojeva.

Zadaci koje je potrebno analizirati prilikom proučavanja ove teme:

Odrediti da li je više brojeva međusobno prostih

Smanjite razlomak (unosi se brojilac i nazivnik razlomka)

Napišite program "Kalkulator" u jednostavnim razlomcima

Druga modifikacija Euklidovog algoritma, koristeći dijeljenje s ostatkom

gdje r – ostatak dijeljenja većeg broja manjim brojem.

Tako, smanjenjem brojeva, dobijamo najveći zajednički djelitelj kao zadnji ostatak koji nije nula.

Problem za rješavanje: pravougaonik sa dužinama stranica a i b, gdje su a i b prirodni brojevi, izrezan na kvadrate najveće površine. Odredite veličinu kvadrata i njihov ukupan broj.

Diofantove jednadžbe

Koristeći tvrdnju o prikazu najvećeg zajedničkog djelitelja dva broja kao linearnu kombinaciju ovih brojeva, dolazimo do tvrdnje o rješivosti u cijelim brojevima jednadžbe oblika ax + by = c(Diofantova jednadžba).

Zadaci koje treba analizirati prilikom proučavanja ove teme:

Zadaci za razmjenu novca kovanicama određenog apoena.

Zadaci transfuzije.

Prilikom proučavanja algoritma za rješavanje problema transfuzije, čini se korisnim korištenje pomoćnog programa demonstracije i obuke „Transfuzija“, uz pomoć kojeg studenti mogu primijeniti proučavani algoritam u praksi. Potrebno je popraviti ovaj algoritam kako bi se pronašlo barem jedno rješenje Diofantove jednadžbe. Zatim je dat opći algoritam za rješavanje Diofantove jednadžbe sa formulama za pronalaženje cjelokupnog skupa rješenja.

primarni brojevi

Mnogi olimpijski problemi različitih nivoa povezani su sa prostim brojevima. Klasična metoda za pronalaženje prostih brojeva je Eratostenovo sito. Uz ovaj algoritam su povezana rješenja sljedećeg zadataka:

Brojevi blizanaca;

Savršeni brojevi;

Ulama stolnjak;

Prijateljski brojevi itd.

"Duga" aritmetika

Zadaci za "dugu" aritmetiku nastaju kada nije moguće pohraniti rezultat u standardnim tipovima podataka (cijeli brojevi ili dugi cijeli brojevi), jer je tako velik. U ovom slučaju se koristi metoda pohranjivanja dugih brojeva kao niza cifara, a za izvođenje aritmetičkih operacija s takvim brojevima potrebno je napisati posebne procedure za sabiranje, množenje i dijeljenje dugih brojeva.

Tipični zadaci: pronađite broj N! (N-faktorski), odrediti period razlomka.

rekurzija

Gotovo svaka knjiga o programiranju bavi se rekurzivnim i rekurzivnim procedurama i funkcijama. Ali postoji vrlo malo knjiga u kojima bi se tema rekurzije detaljno obradila. Tradicionalno, razmatranje rekurzivne funkcije počinje pronalaženjem faktorijala broja. Kratka funkcija u jednom redu, ali nije jasno zašto se faktorijel računa rekurzivno, ako se već razmatra jednostavno u jednom ciklusu sa parametrom.

Što su učenici mlađi, to su im principi jasnoće i jednostavnosti važniji. Uvod u rekurziju može započeti dobro poznatom rimom o "10 malih Indijanaca".

Sljedeći korak su rekurzivni crteži. Počinjemo s najjednostavnijim crtežima, na primjer, crtanjem pojednostavljene "matrjoške".

pahulje koje padaju po cijelom ekranu;

grane različitih boja, različite lepršavosti i različitih veličina (nasumična komponenta se unosi u dužinu grane).

Za djecu su od velikog interesa fraktalni setovi: salveta i stolnjak Sierpinskog, Mandelbrotov model ljudskih pluća, Harter-Hateway fraktal (poznat nam kao izlomljena linija Zmaja), Hilbertove krive, Kochova pahulja. Rekurzija je ovde toliko prirodna da se niko ne pita da li je moguće bez nje. I tek sada, kada šarm i ljepota rekurzije ne izazivaju nikakve sumnje, možemo prijeći na zadatke koji su, po svojoj definiciji, rekurzivni. To su sljedeći zadaci: faktorijel broja, N-ta potencija broja, gcd( a, b), Ackermanova funkcija, Fibonačijevi brojevi, konverzija brojeva iz 10. brojevnog sistema u 2., pronalaženje maksimuma i minimuma u nizu. Ispostavilo se da se mnogi zadaci mogu obaviti pomoću rekurzije. Glavna stvar je da se vizija rekurzije pojavljuje u zadacima koji se ranije nisu rješavali rekurzivno. U svrhu novine, na primjer, u problemu rezanja pravougaonika na kvadrate maksimalne površine, predlaže se izrada vizualne grafičke podrške pomoću rekurzije. I apsolutno je "loše" bez rekurzije pri rješavanju problema kao što je "Hanojska kula". U ovom slučaju, program demonstracije i obuke "Hanojska kula" pomaže da se to realizuje i u praksi savlada rekurzivni algoritam za rješavanje ovog problema.

Sortiranje

Bez poznavanja algoritama za sortiranje, ne može se osjećati ugodno na olimpijadama različitih nivoa. Problemi se mogu formulisati eksplicitno sa spominjanjem algoritma sortiranja, i podrazumevajući upotrebu algoritma sortiranja unutar rešenja. Dva najjednostavnija algoritma koja treba poznavati su sortiranje mehurića i sortiranje razmjenom (pretragom uzastopnih minimuma). Za male količine podataka ove dvije metode su sasvim dovoljne, ali kada radite s podacima mjerenim u desetinama i stotinama KB, morate znati jednu od brzih sorti. Hoareovo brzo sortiranje, koje se implementira rekurzivno, može biti poželjnije. Također morate znati neke trikove kada organizirate podatke u velikim datotekama. Cijela datoteka je podijeljena na nekoliko dijelova koji se mogu sortirati pomoću QSORT-a, a zatim se sortirani fajlovi mogu spojiti bez programa za sortiranje (usput rečeno, ovo je vrlo koristan zadatak sa tehničke tačke gledišta koji zahtijeva preciznost i dobra tehnika programiranja).

Traženje opcija

Problemi pretraživanja čine ogromnu klasu olimpijskih zadataka. Nabrajanje počinje najjednostavnijim traženjem minimuma i maksimuma u jednodimenzionalnom nizu ili traženjem elementa sa datim svojstvima. Zatim, ponavlja se preko parova elemenata koristeći ugniježđenu petlju, zatim iterira preko trostrukih elemenata koristeći trostruku petlju (kao, na primjer, u problemu pronalaženja tri tačke na ravni između datih N tačaka koje čine trokut s maksimalnom površinom ). A ako sortirate kombinacije od 4, 5, 6, itd. elementi? Koliko ciklusa je potrebno? Ispostavilo se da postoje algoritmi koji značajno smanjuju nabrajanje.

Prilično dugo u smislu vremena izvršenja, ali jedan od najsvestranijih algoritama iteracije je vraćanje unazad ili vraćanje unazad. Programirano rekurzivno. To je najbolje objašnjeno u sljedećim zadacima:

Pomerajte viteza po šahovskoj tabli N*M;

Rasporedite 8 dama na šahovsku ploču veličine 8 * 8 tako da ne prijete jedna drugoj;

Pronađite izlaz iz lavirinta itd.

Također je potrebno objasniti studentima da je u slučaju predugog vremena izvođenja programa potrebno ograničiti „povratak“. Na primjer, u šahovskom problemu s veličinom ploče 8 * 8, program radi već duže vrijeme. Moguće je, pa čak i potrebno primijeniti simetriju, zrcaljenje, izvođenje zadatka za polovinu ili četvrtinu šahovske ploče.

Klasični problem "povratka" je problem "ranca", tada možemo razmotriti derivate ovog problema:

Podijelite N brojeva na dva podskupa koja su najbliža zbroju;

Od datog skupa riječi, odaberite maksimalan podniz riječi u redoslijedu rječnika.

Kombinatorni problemi su takođe povezani sa nabrajanjem. Trebali biste savladati algoritme za kreiranje leksikografskog reda.

Zadaci iz geometrije

Obavezni minimum koji morate znati kada rješavate probleme geometrije uključuje sljedeće:

Biti u stanju dovesti jednadžbu prave linije koja prolazi kroz dvije tačke na oblik

Ax + By + C = 0;

Biti u stanju odrediti da li tačka pripada pravoj ili segmentu;

Biti u stanju odrediti da li se dvije prave seku, i ako se sijeku, onda odrediti njihovu presječnu tačku (da biste to učinili, izračunajte determinantu 2. reda);

Znati napisati jednačinu okomite linije ili odrediti da li je jedna prava okomita na drugu (koristeći svojstvo da je skalarni proizvod okomitih vektora jednak nuli);

Znati izračunati udaljenost od tačke do prave.

Osim toga, za rješavanje problema regionalnog i sveruskog nivoa potrebno je poznavanje početnog kursa analitičke geometrije: skalarni i vektorski proizvod vektora, njihov izraz u koordinatama. Skalarni proizvod se koristi za pronalaženje ugla (ili kosinusa ugla) kada se konstruiše, na primer, konveksni omotač datih tačaka. Unakrsni proizvod dva vektora koristi se, prvo, za izračunavanje površina poligona, a drugo, za određivanje smjera u odgovarajućim problemima. Ovo znanje je takođe neophodno da bi se rešio takav klasični olimpijski problem kao što je da li se tačka nalazi unutar proizvoljnog poligona.

Učenicima je potrebno skrenuti pažnju na višeznačnost pojmova koji se mogu koristiti u različitim zadacima. Na primjer, za koncept vektorskog proizvoda

modul numeričke vrijednosti određuje površinu paralelograma izgrađenog na datim vektorima;

nulta vrijednost - paralelni vektori;

znak znači da se jedan vektor nalazi "lijevo" ili "desno" od drugog;

rezultirajući vektor definira normalu na ravan datih vektora.

Numeričke metode

metoda dihotomije

Za traženje podataka u uređenom skupu koristi se metoda dihotomije (ili prepolovljenja), nakon čega slijedi provjera željenih svojstava. Ova metoda, koja je poznatija za pronalaženje aproksimacija korijena nelinearnih jednačina, može se koristiti za pretraživanje kroz "ogromnu" količinu podataka. U ovom slučaju ćemo više koristiti termin "binarna pretraga". Tipičan zadatak je pronaći zadatu riječ u rječniku.

Općenito, ova metoda je optimalna.

Rješavanje sistema linearnih jednačina: Cramerova metoda, Gaussova metoda.

klasične metode. Obično u problemima broj jednačina nije veći od tri. Ali poznavanje opšteg slučaja će verovatno dobro doći.

Zadatak sa regionalne olimpijade star 94 godine.

Jednačina hemijske reakcije upisuje se kao prava: potrebno je izjednačiti, tj. urediti koeficijente.

Statističko modeliranje (Monte Carlo metoda).

Veoma je korisno znati ovu metodu:

za modeliranje probabilističkih situacija u igri (bacanje novčića, kockice, lutanje). To je „zaigrana” ili vezana za nešto poznato (poznato, „svakodnevno”) formulacija problema koja pomaže u razumijevanju metode, koncepta vjerovatnoće. Učenicima možete ponuditi zanimljive zadatke:

Što je više, svodivi ili nesvodivi razlomci? (Matematička formulacija: procijeniti vjerovatnoću da je slučajno odabrani razlomak nesvodljiv);

najbolja opklada za prostake ("Quantum" br. 5, 1987);

kombinatorni zadaci.

Odrediti površine figura, kada su analitička rješenja teška.

Dakle, u problemu (regionalna olimpijada 1999.) pronalaženja površine presjeka tri kruga, Monte Carlo metoda se može koristiti kao alternativa direktnoj analitičkoj metodi, jer je vrlo teško izvesti rješenje pomoću trigonometrije odnosi. Najbolji način je "koristiti geometriju" za analizu posebnih slučajeva (kada nema raskrsnice, kada je raskrsnica u jednoj tački, jedan krug unutar druge), i Monte Carlo metodu za opšti slučaj.

Dinamičko programiranje.

Postoje slučajevi kada je nemoguće riješiti problem potpunim nabrajanjem opcija zbog njihovog ogromnog broja. Ali ako se u svakom koraku problem može podijeliti na jednostavnije i za njih se može pronaći optimalno rješenje bez razmatranja svih rješenja općeg problema, a zatim se pronađena rješenja mogu primijeniti na sljedeće korake, onda to znači da u ovom U slučaju da je primjenjiv princip dinamičkog programiranja.

Ovaj princip se najlakše uočava na specifičnim zadacima. Ali objašnjenje se može započeti zabavnom pričom o zlatnim faraonovim ljestvama (izneseno u časopisu "Kvant" br. 10, 1991.), a zatim prijeći na sljedeće zadatke:

Klasični problem pronalaženja tako najkraćeg puta u NxN numeričkoj matrici A od A(1,1) do A(n,n) u kojoj je zbir cifara u ćelijama minimalan ili maksimalan.

Pronalaženje zajedničkog podniza maksimalne dužine (problem koji je proizašao iz modernog stvarnog problema molekularne biologije o zajedničkim genetskim informacijama u molekulima DNK).

Grafovi i stabla.

Veoma važna tema. Gotovo nijedna olimpijada na ruskom nivou ne može bez upotrebe nekog algoritma na grafovima. Potrebno je uvesti pojam grafa kroz vrhove i ivice, pojam usmerenih ili neusmerenih grafova, analizirati metode za predstavljanje grafova u obliku matrice, susednosti, matrice incidencije, link liste.

Da biste rastavili glavne algoritme na grafovima:

pretraga u dubinu (drugim riječima, „traženje unazad“ ili pretraživanje unazad);

pretraga u širinu (ili metoda popunjavanja);

Dijkstrin algoritam za pronalaženje najkraćih puteva u grafu od datog vrha do svih ostalih;

Floydov algoritam za pronalaženje najkraćih puteva u grafu između svih parova vrhova.

Transformacije teksta

Zadaci u kojima je potrebno raščlaniti niz ponekad dodatno uključuju rad sa datotekama, grafičkim konstrukcijama (slično naredbama tekstualnog ili grafičkog uređivača) ili korištenje bilo koje programske tehnike (na primjer, predstavljanje „stoga“ kao niza znakova u problem ispravnog izraza zagrade za nekoliko tipova zagrada).

Prikazan je širok, ali daleko od kompletnog skupa tema koje pokrivaju olimpijadni problemi. U mnogo čemu zavisi od preferencija organizatora olimpijada različitih nivoa (teorijski krugovi, zadaci koji koriste strategije igre, primenjena „kancelarijska“ priroda).

Pitanje 6 . Šta možete savjetovati prilikom rješavanja zadataka na olimpijadi?

Pod pretpostavkom da je teorija algoritama „proučena“ i savladane osnove programiranja, učesniku takmičenja se može savjetovati:

Omogućite "u rezervi" određeni "zagarantovani" (po vašem mišljenju) rezultat na jednostavnim zadacima. To ne znači da teške zadatke treba ostaviti za posljednji trenutak. Kada se razmišlja o njihovom rješenju, može se pronaći „dobar“ algoritam, a odgovarajući veliki udio bodova će poslužiti kao uspjeh.

Ako vam je problem težak ili nemate dovoljno vremena da ga riješite, programirajte jednostavne posebne slučajeve ( možda neki testovi će proći) ili koristite neki suboptimalan algoritam, kao što je algoritam grube sile.

Ako zadatak ima vremensko ograničenje za rješavanje, a vaš algoritam nabrajanja se ne uklapa u ovo vrijeme, ubacite tajmer u algoritam koji, kada se približi kritičnom vremenu, završava zadatak i prikazuje najbolju pronađenu opciju nabrajanja (možda će budi tačan).

Važan je i izbor algoritamskog jezika, na primjer, u Basic programu je lakše raditi sa grafikom, dok Pascal program ima prednost u brzini.

Strogo poštujte ulazno-izlazne formate navedene u uslovu zadatka: „autotester“ može pogrešno uočiti dodatni razmak ili izvorni testovi sadrže zarez u kojem ste dali razmak u unosu zadatka (karakteristike Pascal i Basic operatora unosa ).

U osnovi, svaki program ima strukturu:

Unos podataka

Blok naselja

Rezultat Izlaz

Potvrdite i provjerite da li je I/O ispravan (uz moguću analizu pogrešnih podataka) prije programiranja obračunskog bloka.

Postavite opcije kompajlera za rukovanje svim vrstama grešaka (korisno za otklanjanje grešaka) i onemogućite ove opcije prije slanja zadatka (da biste ignorirali moguće greške testiranja koje ne utječu na rješenje).

Provjerite problem za data maksimalna ograničenja (na primjer, ako je dato n  1000, provjerite da li je n = 1000). Pazite na tip deklariranih varijabli (poželjno je koristiti tip "long integer" za deklariranje cjelobrojnih varijabli).

Iskoristite žalbu mudro. Moguće je dvosmisleno razumijevanje problema. Žiri su također ljudi, a vi možete braniti svoj stav, uvjeriti ih da vam daju željene bodove.

U krajnjem slučaju, ako ste „kul haker“ (kul specijalista za sistemski deo), pokrenite „susedski“ program kao svoj (pretpostavljam da niko neće primetiti).

Dozvoljeno je imati vlastite cheat sheets (ne u elektronskom obliku) ili koristiti svoje „slobodno“ vrijeme za proučavanje referentne literature.

Neki od ovih savjeta su "štetni", u skladu sa principima "možda, pretpostavljam, i nekako". Molimo vas da ih shvatite kritički, ali oni su od vitalnog značaja.

Pitanje 7 . Koju literaturu treba koristiti u pripremi za olimpijade?

Ovaj članak, kao i sljedeći izvori.

A. Shen. Programiranje: teoreme i problemi, M. MTsNMO, 1995.

A. L. Brudno, L. I. Kaplan. Moskovske programske olimpijade, M: Nauka, 1990.

V.A.Dagene, G.K.Grigas. 100 programskih zadataka, M: Prosvjeta, 1993.

V.M. Bondarev, V.I. Rublinetsky, E.G. Kachko. Osnove programiranja, Harkov: Folio, 1997.

V.M.Kirjuhin, A.V.Lapunov, S.M.Okulov. Zadaci iz informatike. Međunarodne olimpijade. M: ABF, 1996.

N.M.Badin, S.G.Volchenkov, N.L.Dashnits. Jaroslavske olimpijade iz informatike. Jaroslavlj, 1995.

S.M. Okulov. Sažeci nastave informatike (algoritmi na grafovima). Kirov, 1996.

A.V. Aleksejev. Školske olimpijade iz informatike. Krasnojarsk izdavačka kuća, 1995.

A.S. Sipin, A.I. Dunaev. Regionalne olimpijade iz informatike. Vologda, 1994.

V.Pinaev. Gradska olimpijada iz programiranja. Ribinsk, 1998.

S.A. Abramov. Matematičke konstrukcije i programiranje. 1987.

Pitanje 1. Kako naučiti rješavati olimpijske zadatke iz informatike?

Da biste naučili kako rješavati olimpijske zadatke iz informatike, potrebno je rješavati zadatke iz informatike... Naravno, u isto vrijeme uvid u relevantnu literaturu.

Pitanje 2. Koliko zadataka treba da rešite da biste adekvatno nastupili na informatičkim olimpijadama?

Pitanje je, naravno, postavljeno netačno i vjerovatno je teško odgovoriti na njega, ali vrijedi reći nekoliko riječi o tome. Kako mi je rekao Mihail Medvedev, stručnjak u oblasti priprema za ACM olimpijade, kreiranje suštinski novog olimpijskog problema nije tako lako kao što se na prvi pogled čini. Iz tog razloga, ljudi koji su odgovorni za vođenje Olimpijade jednostavno uzimaju probleme iz prošlih godina i serviraju ih sa "novim sosom". Često se dešava da se problemi za regionalne i zonske olimpijade iz informatike „otrgnu“ bez ikakvih promjena sa sajtova posvećenih programiranju olimpijada.

Dakle, pošto su mnogi problemi vrlo, vrlo slični, potrebno je naučiti rješavati probleme iz cijelog niza: sortiranje, dinamičko programiranje, duga aritmetika itd.

Pitanje 3. Da li je moguće pripremiti školarce za informatičke olimpijade u okviru školskog programa?

Mislim da je to nerealno. Svi već odavno znaju da je školski kurs informatike jedno, a informatičke olimpijade drugo. Da, u oglednom programu informatike, u 9. razredu, prilično veliki broj sati je posvećen učenju programiranja. U Semakinovom udžbeniku za 9. razred programiranje je bazirano na jeziku Pascal, Ugrinovičevi primjeri su dati u odnosu na Visual Basic. Ali, čak i ako primijenimo diferenciran pristup podučavanju školaraca, malo je vjerovatno da će ovi sati biti dovoljni da se pojedini školarci pripreme za olimpijade od nule.

Pitanje 4. Ako u programu nema dovoljno sati za pripremu školaraca za olimpijade, kako se onda pripremiti?

Po prve dvije opcije sve je jasno, ali mora postojati razumijevanje rukovodstva škole. Često se vodi "bitka za sat" između nastavnika i to možda neće pasti u krug ili izborni program u programiranju sata.

Lični entuzijazam doveden do krajnjih granica je, po mom mišljenju, vrlo pogubna pojava. Rusko obrazovanje ne treba da počiva na entuzijazmu. Inače, ispada da dok postoji entuzijazam, stvari se odvijaju, fitilj je prestao i sve se srušilo. Entuzijazam neće dugo trajati, ali ponekad ga vrijedi pokazati u nadi da će stvari krenuti s početka.

Pitanje 5. Imam 25 (26, 30...) sati glavnog opterećenja, da li je još moguće učiti sa studentima u klubu programiranja?

Čini mi se da je sa takvim opterećenjem realnije poludjeti nego pripremati učenike za olimpijade. Iskreno saosjećam sa svim nastavnicima sa velikim opterećenjem. Razumijem da nije potrebno odvojiti veliki broj sati od dobrog života, ali ne razumijem kako se može raditi u takvim uslovima.

Pitanje 6. Da li se školarci mogu pripremati za olimpijadu van školskih časova, i ako mogu, kako najbolje organizovati pripremu?

Mogu, ali bi barem trebali imati kućni računar. U idealnom slučaju, trebalo bi da postoji i internet. Ako imate računar i internet, probleme možete riješiti na jednoj od specijaliziranih stranica uz automatsku provjeru rješenja, na primjer, na stranici Škola programera.

Pitanje 7. Šta je potrebno od nastavnika za kvalitetnu pripremu učenika za olimpijadu?

• Sposobnost učenja. Uostalom, kako to biva, osoba je završila obrazovnu ustanovu i tu se ponekad završava njegov razvoj u smislu dobijanja informacija. Čini se da je to dovoljno za rad u školi, pa zašto se uopće truditi...
• Uvijek budite u kontaktu. Vaš učenik može imati pitanje u svakom trenutku, na kraju krajeva, ima onih koji rješavaju probleme noću. Ako ne možete da spavate, zašto ne, ako je moguće, odgovorite mu koristeći isti "ICQ" ili Skype program.

Metode pripreme za olimpijade iz informatike

Relevantnost teme

U vezi sa aktualizacijom i aktiviranjem olimpijadnog pokreta, sve je akutniji problem pripreme učenika za učešće na olimpijadama. Priprema "učenika-olimpijade" počinje pripremom nastavnika.

Problemi sa kojima se suočava nastavnik:

1. Proučavanje novih oblika izvođenja olimpijada.

2. Poznavanje algoritama za rješavanje olimpijskih zadataka.

3. Prisutnost samih zadataka.

4. Poznavanje programskih jezika.

5. Vrijeme za proučavanje, otklanjanje grešaka i testiranje zadataka.

6. Učenje učenika pravilnoj organizaciji aktivnosti na olimpijadi.

Uprkos činjenici da je opseg zadataka koji se razmatraju na Olimpijadi iz programiranja ograničen, rješavanje problema može biti teško ne samo za učenika, već i za nastavnika, jer neki zadaci zahtijevaju poznavanje više matematike. Validacija rješenja i priprema testova obično oduzimaju dosta vremena.

Evo nekih karakteristike pripreme školaraca za programiranje olimpijade :

· U školskom planu i programu ne postoji takav predmet „programiranje“, pa čak ni takav dio. Odnosno, polaznik mora imati vlastitu, prilično jaku motivaciju.

· Postoji ograničenje da je prilikom rješavanja problema poželjno koristiti samo jedan od programskih jezika (SI ili PASCAL).

· Konstantni treninzi idu gotovo na sportskom nivou.

· Veliki utrošak vremena, trajanje olimpijade sa analizom često prelazi 6 sati.

· Algoritmi i formule koji se koriste u rješavanju većine problema proučavaju se samo na univerzitetima.

Naravno viši nivo obuke je takođe potreban za nastavnike za rad sa darovitim učenicima koji učestvuju na takmičenjima u programiranju:

· Eventualno drugo obrazovanje, specijalizovani univerzitet za programiranje.

· Nastavnici IPK, kursevi izučavanja programskih jezika, programiranje olimpijada.

· Samopriprema korištenjem materijala iz dodatnih izvora.

Ali čak ni dobro poznavanje programskog jezika ne daje 100% garanciju da će učenik pobijediti čak i na školskoj ili okružnoj olimpijadi.

Pedagoška ideja

Motivacija je glavni stimulans za učešće na olimpijadama za školarce. Ovo nije samo prilika da poboljšate svoju ocjenu, već i prilika da pokažete znanje i erudiciju o problemu koji se rješava, svoje organizacijske sposobnosti, da date priliku da "zarade ocjenu" drugim učenicima (čak i onima koji ne učestvuju na olimpijadi).

Želja učenika za liderstvom, demonstriranjem sopstvenih dostignuća jedan je od osnovnih uslova za učešće u olimpijadi. Naravno, sa takvom motivacijom ima dovoljno ljudi koji žele da rade, ali u toku rada dolazi do delimične rotacije, a to je neminovno sa savremenim opterećenjem školaraca. Ostaju uglavnom vrijedna djeca, oni učenici koji se ne boje poraza i postavljaju sebi konkretne ciljeve.

Jedna od glavnih pokretača za učešće učenika na takmičenjima u programiranju je želja i interesovanje nastavnika, kao i pomoć, strpljenje i poverenje roditelja.

1964. V. Vroom je predložio "teoriju očekivanja". On je u to vjerovao podsticaj za efikasan i kvalitetan rad zavisi od kombinacije tri faktora – ljudskih očekivanja:

1. Očekivanje da će napori dovesti do željenog rezultata.

2. Očekivanje da će rezultati dovesti do nagrada.

3. Očekivanje da će nagrada biti dovoljne vrijednosti.

Što je veća vjera osobe da će se sva ta očekivanja ostvariti, to će biti jači poticaj za rad. Ako malo promijenimo formulaciju V. Vrooma u obrazovnom kontekstu, onda se događa sljedeće:

Teorija očekivanja ukazuje na ono što nastavnici treba da urade da bi motivacije učenika za učenje bile jake:

o Naučiti studente da postignu tražene rezultate i stvoriti sve potrebne uslove za to;

o Uspostaviti direktnu vezu između rezultata rada i ocjenjivanja učenika;

o Istražite potrebe učenika da znaju koje su nagrade od vrijednosti za njih.

Polazeći od toga, mehanizmi motivacije i glavni faktori efektivnosti podsticaja mogu se izraziti kao:

o Poznavanje nastavnika o potrebama, interesovanjima, potrebama učenika.

o Uspostavljanje pravične direktne veze između rezultata i nagrada.

o Neposredna naknada.

o Stepen zadovoljenja očekivanja.

Da biste se pripremili za olimpijade iz programiranja, možete primijeniti metodologiju koristeći sistem testiranja "NSUTS" , razvijen na bazi NSU-a, koji vam omogućava brzo rješavanje mnogih od ovih problema.

Tehnologija korišćenja sistemaNSUTS »

Sistem se nalazi na adresi https://olympics. *****/nsuts-test/nsuts_new_login. cgi. Kada kliknete na ovaj link, dolazimo do stranice za autorizaciju, gdje unosom korisničkog imena i lozinke možete ući u sistem.

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

U ovom slučaju biramo npr. školske vežbe, nakon čega ćete biti preusmjereni na stranicu " Stranica za registraciju za Školsku obuku gdje je registracija jednostavna i jasna. Samo imajte na umu da podaci koje unosite moraju biti pouzdani.

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

Na kartici " Upomoć» možete pročitati kratku instrukciju za rad u sistemu. Razmotrite sadržaj ove stranice.

NSUTS sistem testiranja. Vrlo kratak opis.

Nalazite se u sistemu automatskog testiranja NSUTS za vođenje i provjeru olimpijada iz programiranja. Trenutni odjeljak je prikazan na vrhu ekrana. U gornjem desnom uglu - naziv trenutne olimpijade, naziv vašeg tima i dugme za izlazak iz sistema - " Izači».

u odjeljku " Tour» možete odabrati trenutni krug olimpijade.

u odjeljku " vijesti» možete pročitati najave i komentare žirija i organizacionog odbora Olimpijade. Također saznajte vrijeme početka i završetka olimpijade. Nakon početka olimpijade na ovoj stranici se pojavljuju linkovi na uslove zadataka.

u odjeljku " Proći» zadaci se šalju na testiranje. Da biste predali problem na testiranje, navedite jezik na kojem je rješenje napisano i broj problema. Zalijepite tekst odluke u polje za unos i kliknite na " poslati". Ili odaberite datoteku koristeći traku za odabir datoteke, a zatim kliknite na " poslati". Vaše rješenje će se pojaviti na listi predatih zadataka u " rezultate».

Vaša rješenja bi trebala čitati unos iz datoteke unos. poruka i ispisati rezultat u datoteku izlaz. poruka . Zabranjeno je čitanje iz standardnog ulaznog toka, pisanje u standardni izlazni tok, standardni tok grešaka. Program učesnika ne smije otvarati, čitati ili mijenjati datoteke osim unosa. txt i izlaz. txt ili druge navedene u izjavi problema. Pristup sistemu datoteka i drugim resursima osim onih navedenih u izjavi zadatka je zabranjen. Kršenje ovog uslova može biti razlog za diskvalifikaciju tima. Ograničenje veličine izvornog koda je 100 kilobajta. Izlazni format mora točno odgovarati zahtjevima opisanim u iskazu problema.

Učesnik može koristiti bilo koji od kompajlera navedenih u " Proći».

Opcije kompilacije:

Visual C++ 6.0
Visual C++ 2005	cl. exe /EHsc /Ox zadatak. cpp /link /STACK:
MinGW 5.1.4 (GCC 3.4.5)	c++.exe - Zid - Wl,--stack= - O2 zadatak. cpp
Freepascal 2.2.0	ppc386.exe - O2 - Cs zadatak. pas
Java 1.6.0_07	javac. exe zadatak. java
lansiratiJava	java - Xmx480m - Xss32m - Djava. sigurnost. menadžer - Duser. language=en_US Zadatak
Borland Delphi 2006

u rubrici " rezultate» Možete vidjeti status testiranja i rezultate testiranja zadataka koje ste poslali. U redu " Vrijeme» označava vrijeme u trenutku podnošenja rješenja, programski jezik koji ste naveli prilikom podnošenja ovog rješenja. Veza " View izvor» će biti prikazan tekst dostavljene odluke.

U redu " Rezultat» prikazuje se rezultat testa:

U redu čekanja - rješenje je u redu čekanja za testiranje.

Testiranje... - trenutno se testira.

Premašeno je ograničenje izvornog koda - prekoračeno je ograničenje izvornog koda programa.

Greška kompajliranja - Prevođenje nije uspjelo (naveden razlog).

Kada se rješenje testira, status poprima jednu od sljedećih vrijednosti:

PRIHVAĆENO! - odluka se smatra ispravnom.

Pogrešan odgovor - pogrešan odgovor na testu.

Vremensko ograničenje je prekoračeno - rješenje nije ispunilo dodijeljeno procesorsko vrijeme.

Timeout - rješenje nije ispunilo predviđeno vrijeme.

Run-time Error - rješenje je vratilo kod greške koji nije nula.

Ograničenje memorije je premašeno - rješenje nije zadovoljilo ograničenje dodijeljene memorije.

Nema izlazne datoteke - nema izlazne datoteke. poruka.

Kršenje sigurnosti - rješenje je izvršilo radnju zabranjenu pravilima.

U ovom slučaju, naznačen je broj testa na kojem je došlo do greške (za ACM olimpijade).

Kratko pravilo za formiranje rejtinga za ACM olimpijade je sledeće: od dva tima, onaj sa najvećim brojem rešenih zadataka biće viši u rejtingu; ako je broj zadataka isti, onda je tim sa manjim kaznenim vremenom veći. Ako su broj zadataka i kazneno vrijeme isti za više ekipa, tada ove ekipe zauzimaju nekoliko uzastopnih mjesta.

Kazneno vrijeme je zbir kaznenog vremena za sve zadatke. Kazneno vrijeme za jedan zadatak je 0 ako se zadatak ne preda. Ako je zadatak položen, tada se njegovo kazneno vrijeme izračunava prema formuli:

vrijeme_ispravnog_rješenja + (broj_neuspjelih_pokušaja * 20).

Odjeljak " Pitanja i odgovori» namijenjen je komunikaciji sa Žirijem Olimpijade. Žiriju možete postaviti pitanja o uslovima problema ili ukazati na netačnost formulacije problema.

Osim toga, ukoliko Žiri smatra da je potrebno izvršiti bilo kakve izmjene uslova problema, izmjene će biti objavljene u ovoj rubrici ili u vijestima.

Sada kada smo pokrili osnove rada sa sistemom, hajde da pogledamo Kako da dobijem zadatak za olimpijadu.

Na kartici "Obilazak" odaberite obilazak Olimpijade koja nam je potrebna, na primjer " Priprema za Sverusku olimpijadu 21.03.2010. (geometrija) ». Nakon toga idite na karticu "Novosti" i pratite link "Uslovi obilaska" da biste preuzeli datoteku u formatu MS Office Word, koja sadrži zadatke predstavljene za rješavanje na ovom obilasku.

Nakon što smo riješili problem, na kartici "Pošalji" ga šaljemo na provjeru, postavljajući sve potrebne parametre (jezik, tekst programa ili datoteku sa programom). Rezultati testa se mogu naći na kartici "Rezultati".

Glavne klase zadataka koje se postavljaju za olimpijade iz informatike

Za uspješan završetak ne samo olimpijade, već i zadataka unutar razreda potrebno je:

1. Da tečno govori programski jezik i okruženje (u našem slučaju to je Free Pascal), da bude u stanju da izgradi i implementira različite algoritme koristeći ovaj jezik.

2. Posjedovati neophodan matematički aparat.

3. Poznavati algoritme za rješavanje glavnih klasa problema, njihovu optimizaciju.

Zadaci programiranja Olimpijade pokrivaju veoma širok spektar znanja, ali najčešće se susreću i izazivaju najveće poteškoće su sledeći:

1. Zadaci koji koriste složene strukture podataka kao što su nizovi, redovi, stekovi, povezane liste i stabla.

2. Grafovi kao skup objekata sa mnogo veza.

3. Zadaci koji koriste analitičku geometriju na konceptu "vektora".

4. Problemi dinamičkog programiranja.

Razmotrimo ove klase problema detaljnije.

Zadaci koji koriste složene strukture podataka kao što su nizovi, redovi, stekovi, povezane liste i stabla.

Programi se sastoje od algoritama i struktura podataka. Dobri programi koriste i jedno i drugo. Izbor i dizajn strukture podataka jednako je važan kao i dizajn procedure koja njima manipuliše. Organizacija informacija i načini pristupa njima obično su određeni prirodom zadatka sa kojim se programer suočava. Stoga svaki programer u svom „prtljagu” mora imati odgovarajuće metode za predstavljanje i traženje podataka koje može primijeniti u svakoj konkretnoj situaciji.

U stvari, strukture podataka u računaru su izgrađene na osnovu osnovnih tipova podataka kao što su "char", "integer", "real". Na sljedećem nivou su nizovi, koji su zbirke osnovnih tipova podataka. Zatim postoje zapisi, koji su grupe tipova podataka kojima se pristupa jednim od podataka, a na posljednjoj razini, kada se fizički aspekti predstavljanja podataka više ne razmatraju, pažnja se posvećuje redoslijedu po kojem se podaci pohranjuju i u kojoj se pretražuje. U suštini, fizički podaci su povezani sa "mašinom podataka" koji kontroliše kako se pristupa informacijama u vašem programu. Postoje četiri takve "mašine":

1. okret;

3. povezana lista;

4. binarno stablo.

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/ocher. html.

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

4) T. Kormen. Algoritmi. Konstrukcija i analiza. 2nd ed. Strana 255

5) Zadaci i rješenja http://*****/olimp/str_prb. php.

Grafovi su poput skupa objekata sa mnogo veza.

Graf je apstraktni matematički objekat. Sastoji se od vrhova i ivica. Svaki rub povezuje par vrhova. Ako nekoliko bridova povezuje isti par vrhova, onda se ti rubovi nazivaju višestrukim. Ivica koja povezuje vrh sa sobom naziva se petlja. Možete hodati duž ivica grafa, krećući se od jednog vrha do drugog. U zavisnosti od toga da li je moguće hodati duž ivice u oba smjera ili samo u jednom smjeru, razlikuje se neusmjereni i usmjereni grafovi, respektivno. Orijentirane ivice se nazivaju lukovi. Ako svi rubovi grafa imaju težinu (tj. neki broj koji jedinstveno odgovara datom rubu), tada se graf naziva ponderiranim. Vrhovi povezani rubom nazivaju se susjedi. Za neusmjereni graf, stepen vrha je broj ivica koje sadrži. Za usmjereni graf, pravi se razlika između stepena po ulaznim i stepena po izlaznim ivicama. Graf se naziva kompletnim ako postoji ivica između bilo kojeg para različitih vrhova.

Graf je apstraktni objekat i možemo ga interpretirati na različite načine, ovisno o konkretnom zadatku. Razmotrimo primjer. Neka su vrhovi grafa gradovi, a ivice putevi koji ih povezuju. Ako putevi imaju jednosmjerni promet, onda je graf orijentisan, inače neusmjeren. Ako je cesta naplaćena, tada se graf ponderira.

Na papiru je zgodno predstaviti graf tako što se vrhovi prikazuju kao tačke, a ivice kao linije koje povezuju parove tačaka. Ako je graf orijentisan, potrebno je da nacrtate strelicu na linijama koja određuje pravac; ako je graf ponderisan, onda je na svaku ivicu potrebno upisati i broj - težinu ivice.

Postoji nekoliko načina da se graf predstavi u memoriji računara. Sljedeće veze do teorije možete pronaći u nastavku:

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

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

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

4. http://book. *****/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. Zadaci i rješenja http://*****/olimp/gra_prb. php

Problemi sa upotrebom analitičke geometrije i zasnovani na konceptu "vektora"

Računarska geometrija je grana računarske nauke koja proučava algoritme za rješavanje geometrijskih problema. Ovakvi problemi nastaju u kompjuterskoj grafici, projektovanju integrisanih kola, tehničkih uređaja itd. Početni podaci u takvim problemima mogu biti skup tačaka, skup segmenata, poligon itd. Rezultat može biti ili odgovor na neko pitanje (kao što je „seku da li se ove linije“), ili neki geometrijski objekat (na primer, najmanji konveksni poligon koji sadrži date tačke).

U "Informatici" broj 14 objavljen je članak jednog od autora posvećen problemima računske geometrije na olimpijadama iz informatike. Tamo je posebno formulisan niz elementarnih podproblema na kojima se zasniva rešavanje većine problema računarske geometrije. Međutim, nastava i sa matematički dobro pripremljenim srednjoškolcima pokazala je da im rješavanje ovakvih podzadataka izaziva velike poteškoće. Zadatak ih ili zbunjuje, ili je odabrana “frontalna” metoda rješavanja toliko komplikovana da je učenici ne mogu obaviti bez grešaka. Analiza rezultata rješavanja "geometrijskih" zadataka na Sveruskim olimpijadama iz informatike dovodi do istih zaključaka. Koristeći donje veze, možete proučavati pristupe rješavanju geometrijskih problema na ravni, koji vam omogućavaju da brzo i jednostavno dobijete rješenja za većinu elementarnih podzadataka.

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

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

3) Zadaci i rješenja http://*****/olimp/geo_prb. php

Problemi dinamičkog programiranja.

Mnogi olimpijski zadaci, kao i zadaci praktičnog programiranja, su zadaci za sortiranje opcija i izbor među njima prihvatljive ili najbolje po jednom ili drugom kriteriju. Međutim, zbog njihovog izuzetno velikog broja, često nije moguće razmotriti sve opcije.

Srećom, za brojne probleme koji su po formulaciji slični problemima koji zaista zahtijevaju kompletno nabrajanje opcija, može se pronaći mnogo efikasnije rješenje. Najčešće se u takvim slučajevima rješenje svodi na pronalaženje rješenja za podprobleme niže dimenzije, koji se pohranjuju u tablicu i nikada se ne preračunavaju, a podzadaci veće dimenzije koriste ova već pronađena rješenja. Ova metoda se naziva dinamičko programiranje, a naziva se i metodom tabele. U opštem obliku, dinamičko programiranje se shvata kao proces korak-po-korak rešavanja optimizacijskog problema, u kojem se na svakom koraku, iz skupa izvodljivih rešenja, bira jedno koje optimizuje datu ciljnu ili kriterijumsku funkciju. Ponekad se, umjesto optimizacijskog, istim metodom rješava problem brojanja dopuštenih rješenja. U ovom slučaju, na svakom koraku, umjesto izbora optimalnog rješenja, rješenja podproblema manje dimenzije se sabiraju, a njihova formulacija se ne poklapa uvijek u potpunosti s izvornim problemom (odgovarajući primjeri će biti razmotreni u nastavku). U oba slučaja, rješenje pronađeno u trenutnom koraku obično se unosi u tabelu. Po pravilu, odnos između zadataka i podzadataka formuliše se kao određeni „princip optimalnosti“ i izražava se sistemom jednačina (rekurentne relacije).

Osnove teorije dinamičkog programiranja postavio je R. Bellman. Imajte na umu da riječ programiranje u gornjem naslovu (dinamičko programiranje), kao i u "linearnom programiranju" (linearno programiranje) ne znači kompajliranje programa za računar.

Za rješavanje problema optimizacije u kojem je potrebno konstruirati rješenje s maksimalnom ili minimalnom (optimalnom) vrijednošću nekog parametra, algoritam baziran na dinamičkom programiranju može se formulirati na sljedeći način:

1) identifikuje i opiše podzadatke kroz čije će se rješenje iskazati željeno rješenje,

2) ispisati rekurzivne relacije (jednačine) koje povezuju optimalne vrijednosti parametra za podzadatke,

3) izračunati optimalnu vrijednost parametra za sve podzadatke,

4) izgraditi najoptimalnije rješenje koristeći primljene informacije.

Ako nas zanima samo vrijednost parametra, onda korak 4 u algoritmu nije potreban (ova situacija je tipična, na primjer, za probleme brojanja dopuštenih opcija ili nekih konfiguracija, uključujući i kombinatorne). Međutim, ako je potrebno konstruisati najoptimalnije rješenje, ponekad je potrebno dobiti i pohraniti dodatne informacije tokom izvršavanja koraka 3 algoritma. Često se pokaže da je korak 4 najteži pri implementaciji takvih algoritama.

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

2) http://www. *****/Olimpijade/Pravila_Olimpijade/Pravila21.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) Zadaci i rješenja http://*****/olimp/rec_prb. php

OPŠTINSKA OBRAZOVNA USTANOVA - SREDNJA OBRAZOVNA ŠKOLA MUZHEVSKAYA IME N.V. ARKHANGELSKY

"Olimpijade iz informatike: Metode priprema"

Pripremljen materijal:

IT-učitelj

Galitskaja Irina Viktorovna

U vezi sa aktualizacijom i aktiviranjem olimpijadnog pokreta, sve je akutniji problem pripreme učenika za učešće na olimpijadama. Priprema "učenika-olimpijade" počinje pripremom nastavnika.

Problemi sa kojima se suočava nastavnik:

· Proučavanje novih oblika izvođenja olimpijada.

· Poznavanje algoritama za rješavanje olimpijskih zadataka.

Prisutnost samih zadataka.

· Poznavanje programskih jezika.

· Vrijeme za proučavanje, otklanjanje grešaka i testiranje zadataka.

Učenje učenika pravilnoj organizaciji aktivnosti na olimpijadi.

Uprkos činjenici da je opseg zadataka koji se razmatraju na Olimpijadi iz programiranja ograničen, rješavanje problema može biti teško ne samo za učenika, već i za nastavnika, jer neki zadaci zahtijevaju poznavanje više matematike. Validacija rješenja i priprema testova obično oduzimaju dosta vremena.

Većina nastavnika to ne može. Najispravniji izlaz u ovoj situaciji je jačanje veza između škole i univerziteta.

Evo nekih karakteristika pripreme školaraca za programiranje olimpijade:

1. U školskom planu i programu ne postoji takav predmet "programiranje". One. pripravnik mora imati vlastitu, prilično jaku motivaciju.

2. Postoji ograničenje da je prilikom rješavanja problema poželjno koristiti samo jedan od programskih jezika (SI ili PASCAL).

3. Redovni treninzi su skoro na sportskom nivou.

4. Veliki utrošak vremena, trajanje olimpijade sa analizom često prelazi 6 sati.

5. Algoritmi i formule koji se koriste u rješavanju većine problema proučavaju se samo na univerzitetima.

Naravno, potrebna je i obuka višeg nivoa za nastavnike za rad sa darovitim učenicima koji učestvuju na takmičenjima u programiranju:

· Eventualno drugo obrazovanje, specijalizovani univerzitet za programiranje.

· Kursevi programskog jezika, Olimpijski kursevi programiranja.

· Samopriprema korištenjem materijala iz dodatnih izvora.

Ali čak ni dobro poznavanje programskog jezika ne daje 100% garanciju da će učenik pobijediti čak i na školskoj ili okružnoj olimpijadi.

Pedagoška ideja iskustva

Motivacija je glavni stimulans za učešće na olimpijadama za školarce. Prilika da se pokaže znanje i erudicija o problemu koji se rješava.

Želja učenika za liderstvom, demonstriranjem sopstvenih dostignuća jedan je od osnovnih uslova za učešće u olimpijadi. Naravno, sa takvom motivacijom ima dovoljno ljudi koji žele da rade, ali u toku rada dolazi do delimične rotacije, a to je neminovno sa savremenim opterećenjem školaraca. Ostaju uglavnom vrijedna djeca, oni učenici koji se ne boje poraza i postavljaju sebi konkretne ciljeve.

Jedna od glavnih pokretača za učešće učenika na takmičenjima u programiranju je želja i interesovanje nastavnika, kao i pomoć, strpljenje i poverenje roditelja.

1964. V. Vroom je predložio "teoriju očekivanja". Smatra da podsticaj za efikasan i kvalitetan rad zavisi od kombinacije tri faktora – ljudskih očekivanja:

1. Očekivanje da će napori dovesti do željenog rezultata.

2. Očekivanje da će rezultati dovesti do nagrada.

3. Očekivanje da će nagrada biti dovoljne vrijednosti.

Što je veća vjera osobe da će se sva ta očekivanja ostvariti, to će biti jači poticaj za rad. Malo sam promijenio formulaciju V. Vrooma u obrazovnom kontekstu i evo šta se dogodilo.

Teorija očekivanja ukazuje na ono što nastavnici moraju učiniti kako bi imali jake poticaje za učenike da uče:

· Naučiti učenike da postignu tražene rezultate i stvoriti sve potrebne uslove za to.

Uspostaviti direktnu vezu između rezultata rada i ocjenjivanja učenika.

· Istražite potrebe učenika da znaju koje su nagrade od vrijednosti za njih.

Na osnovu toga, mehanizmi motivacije i glavni faktori efektivnosti podsticaja mogu se izraziti kao:

1. Poznavanje od strane nastavnika potreba, interesovanja, potreba učenika.

2. Uspostavljanje pravične direktne veze između rezultata i nagrađivanja.

3. Hitnost nagrade.

4. Stepen zadovoljenja očekivanja.

Iskusite tehnologiju

Naravno, priprema za olimpijade je dug i naporan proces.

Korištenje principa "Ono što si zaradio, to si i dobio" omogućava vam da stvorite potrebu za povećanjem kognitivne aktivnosti učenika, njihovog samoizražavanja i interesa za produktivne aktivnosti učenja, želju za pokazivanjem vlastitih postignuća.

Implementacija iskustva

Interes za "olimpijadno programiranje" može se pobuditi na mnogo načina. Najbolji način je proširenje znanja o računaru, kompjuterskim proračunima, uvođenje algoritamskih konstrukcija u časove informatike i naknadna integracija sa užim rešavanjem problema u određenom programskom jeziku.

Prvi korak. Pripremni. Nastava se odvija u obliku igre. Postepeno se uvodi skup naredbi, što omogućava uključivanje računskih alata u rješavanje problema. Algoritam je dovoljno opisati u bilo kom programskom jeziku.

Drugi korak. Na početku programiranja iu toku narednih časova uvode se različite metode rješavanja problema korištenjem standardnih algoritama implementiranih u programskom jeziku. Uvodi se koncept "debagovanja programa". Preporučljivo je razmotriti nekoliko rješenja kako bi se studenti u konačnici naučili elementima optimalnog pretraživanja.

Treći korak. "Nastavna refleksija". Učenik podučava druge rješavanju problema. To se obično dešava prilikom raščlanjivanja zadataka. Ovo pomaže učeniku da odredi znakove optimalnosti (kratkoća, jasnoća), nauči jasno pratiti i objasniti rad programa.

Četvrti korak. To proizlazi iz drugog i trećeg uz naknadno usložnjavanje zadataka i alata za njihovo rješavanje. U ovoj fazi posebno je važno uključiti univerzitetske nastavnike ili tražiti složenije zadatke koji doprinose razvoju logičkog, maštovitog mišljenja i razvijanju kombinatornih sposobnosti.

Peti korak. "Kreativna refleksija". Studentska kompilacija zadataka sa autorskim rešenjem, sa testovima, ulaznim i izlaznim zahtevima.

Najviše dostignuće majstorstva: stvaranje i primjena tehnologija učenja koje su sami učenici izmislili da bi podučavali druge.

Efikasnost

Metodologija pripreme za olimpijade iz programiranja može se koristiti za rješavanje problema sa kojima se suočavaju nastavnici informatike koji pripremaju učesnike olimpijada i učenici koji učestvuju na olimpijadi. Predložena metodologija nije lijek, ali će pomoći ne samo u pripremama za regionalnu olimpijadu, već i za olimpijade višeg nivoa.

Na internetu postoji mnogo programa i testova koji obavljaju funkciju učenja na daljinu i nastavnici ih koriste za pripremu učenika za olimpijade. Ali! Ponekad je zbog brzine i kvaliteta komunikacije nemoguće učestvovati na online takmičenjima u programiranju. Često učenik ne poznaje standard sučelja za podnošenje zadataka, a da biste otklonili grešku u zadatku i dobili rezultat, potrebno je ponovo ući na stranicu olimpijade. Provjera i detaljna analiza rezultata zahtijeva dodatno vrijeme. Instaliranje ovakvog serverskog sistema u učionici je prilično naporno. A na kućnom računaru učenika trenutno je gotovo nemoguće. Ne znaju svi nastavnici informatike pravila za unos i izlaz podataka putem tekstualne datoteke prilikom slanja i primanja odluka putem interneta.

Trenutno su razvijene mnoge metode nastave informatike. No, unatoč činjenici da se programiranje i algoritmizacija mogu kombinirati prilikom studiranja informatike, rješavanje problema sa Olimpijade iz programiranja zahtijeva potpuno drugačiji pristup.

U radu sa učenicima u pripremi za olimpijade, u cilju učvršćivanja vještina, potrebno je više puta rješavati zadatke određene vrste. Istovremeno, nastavnik može učenicima izdati zadatak kod kuće u elektronskom obliku (link na sajt, u arhivi), a učenici, nakon što reše probleme, svoje rešenje donose na nosaču i predaju na proveru. . Nakon toga se u grupi analiziraju zadaci, učenici govore o načinima rješavanja zadataka.

U narednim fazama rada zadaci postaju teži.

Problem psihičkog i fizičkog preopterećenja

Učenici koji učestvuju na olimpijadama odlikuju se velikom radnom sposobnošću, a ponekad nastavnici, videći to, počnu postepeno da podižu ljestvicu zahtjeva i ocjena. Ali kada se priprema za olimpijade bilo kog nivoa, ne samo u programiranju, učenik se mora dodatno truditi i naporno raditi kod kuće, na nastavi i vannastavnim aktivnostima, čak iu početnim fazama. Učenik uči mnoge teme školskih predmeta na osnovnom nivou ubrzanim tempom samo zahvaljujući marljivosti, velikoj radnoj sposobnosti, uz pomoć nastavnika i roditelja. Zadatak nastavnika i administracije je da za vrijeme priprema ne prekoračuju granice iz drugih predmeta. Stoga je potrebna kontrola i podrška ne samo roditelja, već i nastavnika, a ponekad i pomoć i razumijevanje administracije.

Plan, redoslijed proučavanih tema, koji će vam pomoći da naučite kako riješiti olimpijske zadatke ili pronaći praznine u svom znanju.

Odjeljak 1. Matematičke osnove programiranja

Odjeljak 2. Tehnika programiranja

1. Osnove programskog jezika (Pascal, C) Varijable i jednostavni tipovi podataka, veličine tipova. Linearni programi. Uslovne izjave. ciklusa. procedure i funkcije. Složeni tipovi podataka (nizovi, nizovi, zapisi, pokazivači, fajlovi).

2. Nizovi Jednodimenzionalni nizovi. Dvodimenzionalni nizovi (matrice). Višedimenzionalni nizovi.

3. Linije. Elementi leksičkog i sintaksičkog raščlanjivanja Operacije nad stringovima. Žetoni, brojeći žetone raznih vrsta. Izdvajanje brojeva iz niza.

4. Rad sa datotekama Čitanje i pisanje u tekstualnu datoteku. Pretvaranje podataka primljenih iz datoteke u prikladnu strukturu. Rad sa kucanim fajlovima. neotkucani fajlovi. Ulazno baferovanje.

5. Rekurzija Matematičke funkcije zadane rekurzivno. Primjeri rekurzivnih rutina. Problem zaustavljanja rekurzije. Zamjena rekurzije iteracijom.

6. "Duga" aritmetika Pohranjivanje brojeva u program koji se ne uklapaju u standardne tipove. Aritmetičke operacije nad "dugim" brojevima. "Dugi" brojevi sa decimalnim dijelom. Ekstrahiranje korijena sa zadatom tačnošću.

7. Pohranjivanje informacija u dinamičku memoriju. Pohranjivanje skupa podataka u linearne liste. Umetanje u listu, brisanje sa liste, traženje elementa na listi. dvostruko povezane liste. Koncepti struktura podataka steka, prstena, reda, špila; njihova implementacija pomoću dinamičke memorije. binarnih stabala. Drveće sa neograničenim brojem djece. Skladištenje velikih nizova.

Odjeljak 3. Algoritmi, metode i principi za rješavanje problema.

1. Koncept složenosti algoritma. Definicija složenosti.

2. Algoritmi pretraživanja i sortiranja Potražite element u neuređenom nizu. Binarno pretraživanje po ključu u uređenom nizu (dihotomija). Fibonačijeva pretraga. Traži u uređenom n-dimenzionalnom nizu. Pronalaženje k-tog najvećeg elementa u nizu. Jednostavne metode sortiranja ("bubble", "select", "insert", "count"). Brze metode ("brzo", "spajanje", "piramidalno"), balansiranje binarnih stabala. Sortiranje metodom merica.

3. Rješavanje problema nabrajanjem opcija Primjena rekurzije za nabrajanje. Generiranje kombinacija, plasmana, permutacija i Booleovih skupova. Puno nabrajanje. Obrezivanje po izboru (heuristika). Metoda grananja i veza.

4. Računska geometrija i numeričke metode Dužina segmenta. Jednačina prave linije. Skalarni i vektorski proizvod. Tačka sjecišta segmenata. Pripadnost tačke figuri na ravni (na primjer: trokut). Površina konveksnog poligona. Konveksni trup skupa tačaka: Graham, Jarvis, "zavadi pa vladaj" algoritmi. Najbliži par tačaka. Gaussova metoda za rješavanje sistema linearnih jednačina. Pronalaženje rješenja jednadžbe.

5. Princip dinamičkog programiranja Koncept, primjenjivost. Poređenje sa nabrajanjem.

6. Pohlepni algoritmi Koncept, primjenjivost. Poređenje sa nabrajanjem i dinamičkim programiranjem.

7. Teorija grafova. Algoritmi na grafovima Koncept grafa. Definicije teorije grafova. Strukture podataka za predstavljanje grafa u programu. Algoritmi prelaska grafa (prve pretrage po širini i dubini). Labirint (talasna metoda). Eulerov ciklus. Najkraći put u ponderiranom grafu (Dijkstra-ov i Mintyjev algoritam). Zatvaranje tranzitivnog grafa (Floyd-Warshill algoritam). Minimalno razapinjuće stablo (Primovi i Kruskalovi algoritmi). Topološko sortiranje grafa. Tokovi u mrežama (Ford-Fulkerson algoritam). Podudaranja u bipartitnom grafu (metoda lanca produženja, rješenje protoka). Problem zadatka, dodjela uskog grla (mađarski algoritam). Grafičke igre. Grafikon bojanja. Postavljanje grafa na ravan. Jaka povezanost i bikonektivnost grafa. Izomorfizam grafa. K-klik. Hamiltonov ciklus.

8. Leksička i sintaktička analiza Zadatak "Kalkulator". Sintaksički dijagrami. Backus-Naur forme. Model steka i rekurzivnog raščlanjivanja. Konačni automati. Gramatike.

9. Zadaci sa preokretom

Odjeljak 4. Olimpijade iz informatike

1. Pravila održavanja olimpijada iz programiranja

2. Tipične greške i programi za otklanjanje grešaka

3. Olimpijski trikovi

Po meni su od najveće vrednosti odeljci 2 i 3. Dok učenje programskog jezika ne bi trebalo da vam bude teško (postoji ogroman broj knjiga na ovu temu), onda će biti teže sa algoritmima. Ima i dosta knjiga na ovu temu, ali one su najčešće preopterećene teorijom, a na olimpijadama je potrebna samo praksa. Od elektronskih izvora o algoritmima, mogu preporučiti knjigu SM Okulova i sajt algolist.manual.ru, koji je manje namenjen proučavanju "olimpijadne informatike" od Okulove knjige, ali sadrži veliki broj algoritama koji se ne nalaze u knjiga, ali koji nisu bili loši znali bi. Naviknite se na rad u režimu: pisanje + otklanjanje grešaka u Borland Pascal/Borland C++, i kompajliranje (sa preliminarnom promjenom konstanti) u Free Pascal/GNU C. Novi 32-bitni kompajleri nemaju teško ograničenje memorije i rade puno brži (razlika u brzini izvršavanja 16 i 32-bitnih programa na P4). Takva lukava taktika objašnjava se nedostatkom pristojnog debagera na novim platformama i njihovom gotovo potpunom kompatibilnošću s Borland kompajlerima (u FP-u ne zaboravite zatvoriti izlaznu datoteku).