Priprema učenika za informatičku olimpijadu. Program individualne pripreme za općinsku etapu Sveruske olimpijade za školarce na temu "Informatika i ICT. Plan pripreme za informatičku olimpijadu

Analiza olimpijskih zadataka.

Metode pripreme za regionalnu fazu Sveruske olimpijade za školarce iz informatike.

Materijali za majstorsku klasu (prezentacija)

na RMO nastavnika informatike.

nastavnika informatike i ICT-a

MOU "Licej br. 23"

Shuvalova Svetlana Yurievna.

Ovaj rad sažima materijale koje sam prezentirao na RMO nastavnika informatike 2011., 2012. na temelju rezultata školskih faza Sveruske olimpijade za školarce iz informatike.

Broj sudionika olimpijade iz programiranja za školarce svake je godine sve manji, zbog smanjenja udjela sati u sadržajnoj liniji "Algoritmizacija i programiranje" u kurikulumu školskog kolegija informatike. Olimpijade su namijenjene prepoznavanju najdarovitijih školaraca u području informatike, razvoju njihovih sposobnosti i povećanju interesa za predmet. Pružaju priliku školarcima da dobiju rano profesionalno usmjeravanje, što pridonosi razvoju ruskih stručnjaka u području informatike, računalne tehnologije i programiranja u budućnosti. Ali dobro poznavanje školskog kolegija informatike ne jamči uspješan nastup na olimpijadama, potrebno je surađivati ​​s učenicima izvan učionice.

Slajd 1.

Cilj informatičke olimpijade jeolakšati potragu za najdarovitijim učenicima.

Važna značajka zadataka koji se koriste tijekom školske i općinske faze je njihova usmjerenost na provjeru razvijenosti teoretskog mišljenja, logike, kreativnosti i intuicije učenika.

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

Slajd 2.

Glavni kriteriji za odabir olimpijskih zadataka za školske i općinske faze Sveruske olimpijade za učenike informatike:

• originalna formulacija problema (ili ideja njegovog rješenja);
• tekst iskaza problema ne smije sadržavati pojmove i pojmove koji nadilaze predmete koji se izučavaju u okviru temeljnog kurikuluma;
• zadatak mora biti nedvosmisleno definiran;
• zadatak ne bi trebao zahtijevati posebno znanje za njegovo rješavanje;
• formulacija problema treba pretpostaviti prisutnost faze formalizacije pri njegovom rješavanju;
• zadatak mora biti razumne složenosti i intenziteta rada.

Slajd 3.

Olimpijske zadaće za školske i općinske etape informatičke olimpijade odlikuju se tematskom raznolikošću.

Iz iskustva s olimpijada, najčešćisekcije 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 iskaza problema.
• Formalizacija iskaza problema.
• Izrada algoritma za rješavanje problema.
• Programska implementacija algoritma.
• Otklanjanje pogrešaka i testiranje programa.
• Dostavljanje rješenja na pregled.

Slajd 5.

Važno je napomenuti datekst problema uvijek se mora pažljivo pročitatiod početka do kraja, budući da se ključni uvjet može sakriti, na primjer, u formatu ulaznih ili izlaznih podataka, kao iu navedenim primjerima datoteka ulaznih i izlaznih podataka.

Prilikom izrade programa posebnu pažnju treba obratiti i na opisformat ulaznih i izlaznih podatakadano u iskazu problema. Nazivi ulaznih i izlaznih datoteka također su opisani u opisu problema, a njihov netočan pravopis u programu smatra se greškom.

Jedna stvar koju treba zapamtiti kada pišete program jespremanje uređenih datoteka tijekom obilaska.

Rezultirajući program mora odgovarati zadanomdimenzije ulaznih podatakai zadovoljiti ograničenja namemorija i vrijeme radanavedeno u opisu problema.

Slajd 6.

Uobičajene pogreške:

• Format unosa-izlaza podataka ne odgovara uvjetu zadatka

• Ne razmatraju se svi mogući slučajevi

• Vrsta podataka (dimenzija) nije ispravno postavljena

• Gubitak uređenih datoteka tijekom obilaska

Slajd 7.

Minimalna baza znanja za informatičku olimpijadu.

Programski jezik:

• osnovne algoritamske konstrukcije,
• standardne matematičke funkcije,
• procedure i funkcije za obradu string varijabli,
• procedure i funkcije za rad s nizovima.

Tipični algoritmi.

Slajd 8.

Zadatci na informatičkim olimpijadama ne odgovaraju uvijek "Standardu osnovnog i srednjeg (potpunog) općeg obrazovanja iz informatike i ICT-a". Štoviše, kao rješenje ovih problema na olimpijadi potrebno je prezentirati debugirane programe napisane programskim jezikom visoke razine, a ne opise algoritama.

Stoga na temelju rezultata olimpijada nije ispravno ocjenjivati ​​rad pojedinog nastavnika informatike, budući da program školskog kolegija informatike ne može obuhvatiti sve teme čije bi proučavanje moglo poboljšati uspjeh školaraca na olimpijade.

Slajd 9.

Internetski izvori za pripremu za olimpijade iz informatike:

http://algolist.manual.ru/

Analiza problematike školskog kola Olimpijade 2011.

Problem broj 1 "Snimanje glazbe" (15 bodova)

Provjerite hoće li glazbena skladba koja traje m minuta i n sekundi stati na disk računala, ako je slobodnog prostora na disku 6 megabajta, a za snimanje jedne sekunde zvuka potrebno je 16 kilobajta.

Algoritam rješenja:

Korištenje formule izračuna i uvjetnog operatora

Problem broj 2 "Kombinirana sigurnosna brava"(20 bodova)

Trebate upisati 3 od 10 slova. Ponavljanje slova je dopušteno. Izbrojite broj mogućih kombinacija kodova.

Algoritam rješenja:

Kombinatorski problem. Za njegovo rješavanje potrebno je primijeniti tipičan algoritam za formiranje skupina plasmana s ponavljanjima. Koriste se ugniježđene petlje.

Problem broj 3 "pravokutnik"(30 bodova)

Na ravnini je prikazano N pravokutnika. Svaki pravokutnik određen je koordinatama donjeg lijevog i gornjeg desnog vrha. Odredite imaju li pravokutnici 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 lijevih vrhova pravokutnika manja je od minimalne koordinate gornjih desnih vrhova , tada je ukupna površina.

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

Problem broj 4 "Čarobni kvadrat"(35 bodova)

U kvadrat 3x3 stavite brojeve 1, 2, ..., 9 tako da su zbroji brojeva u svakom retku, stupcu, u svakoj dijagonali jednaki.

Algoritam za rješavanje.Zadatak na putu ispuniti dvodimenzionalni niz.

(indijski način):

1. U sredini gornje linije stavite 1 , u zadnjem redu stupca s desne strane 2 .
2. Sljedeći brojevi su postavljeni u dijagonalnom smjeru.
3. Došavši do desnog ruba kvadrata, idu do krajnje lijeve ćelije sljedećeg reda iznad.
4. Došavši do gornjeg ruba kvadrata, idu u najnižu ćeliju stupca koja je susjedna s desne strane. Bilješka. Došavši do ćelije u gornjem desnom kutu, idite na donji lijevi.
5. Nakon što su stigli do već zauzete ćelije, odlaze do ćelije koja leži neposredno ispod posljednje popunjene ćelije.
6. Ako je posljednja popunjena ćelija u donjem redu kvadrata, idite na najgornju ćeliju u istom stupcu.

Analiza problematike školskog kola Olimpijade 2012.

Cilj 1.

Ispiši sve troznamenkaste decimalne brojeve koji zbrajaju zadani broj.

Algoritam rješenja:

Jedna od opcija za rješavanje grubom silom:

var a, b, c, n, k: cijeli broj;

početi

napisati ("n ="); readln (n);

za a: = 1 do 9 do

Za b: = 0 do 9 učiniti

Za c: = 0 do 9 učiniti

Ako je a + b + c = n tada

početi

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

k: = k + 1;

kraj;

Writeln;

Writeln ("k =", k);

Writeln;

kraj.

Drugo rješenje je grubom silom:

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

početi

napisati ("n ="); readln (n);

za m: = 100 do 999 do

početi

c: = m mod 10;

b: = m div 10 mod 10;

a: = m div 100;

ako je a + b + c = n tada

početi

pisati (m: 5);

k: = k + 1;

kraj;

kraj;

writeln ("k =", k)

kraj.

Cilj 2. "Klinac i Karlson".

Kid i Carlson žive u pravokutnoj sobi veličine A x B ... Kako izračunati koliko će kvadratnih prostirki sa stranom biti potrebno S potpuno prekriti pod sobe? (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 (dok je str ) rezerviraj prostor za red ( p: = p + c ), zatim u unutarnjoj petlji uz drugu stranu (dok je m ) provjeravamo koliko se prostirača može koristiti za zatvaranje reda, operater m: = m + s rezervira prostor za prostirku i operatera kovrik: = kovrik + 1 izračunava ukupan broj postavljenih prostirki.

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

početi

readln (a, b, c);

kovrik: = 0;

p: = 0;

dok je str

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. Istovremeno se svaka od preostalih bakterija također podijelila na dvije nove. U sljedećoj minuti dva virusa koja su nastala uništila su dvije bakterije, a onda su se svi virusi i bakterije opet razdvojili, i tako dalje. Hoće li ova kolonija živjeti u nedogled ili će izumrijeti?

Vaš program bi trebao:

• Zatražite broj bakterija n;
• Saznajte i javite: za koliko dana, sati i minuta će bakterijska kolonija prestati postojati ili izdati poruku da je kolonija vječna.

Primjer odgovora: Za n = A. Odgovor - 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 ('Inicijalna veličina kolonije -"); readln (n);

v: = 1;

dok je n> 0

Početi

t: = t + 1; (minuta)

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

v: = v * 2; (virusi)

kraj;

a: = t div 1440;

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

c: = t - a - b;

Napišite ("Kolonija će prestati postojati za", a, "dani", b, "sati", c, "minute");

kraj.

Zadatak 4.

Dobili ste pravokutnik sa stranicama A i B, gdje su A, B prirodni brojevi. Od njega počinjemo odrezati kvadrate (slika 1). Koliko ovih kvadrata možete odrezati ako svaki put odsiječete najveći kvadrat?

Algoritam rješenja:

1 način.

Da bismo riješili ovaj problem, potrebne su nam funkcije MAX i MIN , za njihovu definiciju koristimo potprograme-funkcije.

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 izrezivanja najvećeg kvadrata čija se stranica nalazi kao X: = MIN (D, X).

Organiziramo ciklus u kojem se strana Y svaki put se smanjuje za MIN (D, X) dok ne ostane zadnji kvadrat, ili Y neće postati manje X. U potonjem slučaju preimenujte stranice preostalog pravokutnika kao Y: = MAX (D, X) i X: = MIN (D, X) i nastavi 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

inače min: = j

kraj;

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

početi

ako ja

inače max: = i

kraj;

početi

ponoviti

Writeln ("vvedite dva naturalnix chisla");

Readln (a, b);

sve 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 chislo kvadratov:", k)

kraj.

Metoda 2.

Problem se može riješiti standardnim funkcijama PASCAL: Y DIV X i Y MOD X, koristeći Euklidov algoritam.

Algoritam rješenja:

Organiziramo ciklus u kojem formiramo ostatke dijeljenja r 0, r 1, r 2, ..., r n, r n + 1 sve dok jedan od tih ostataka ne bude jednak nuli r n + i = 0 ... Dakle, konstruiramo funkciju za generiranje ostatka dijeljenja r n + i = r n mod r n-i, gdje je r 0 = A i r i = B ... Za isti sustav ostataka možemo izračunati koliko puta ostatak potpuno odgovara r n-i do r n.

(Euklidov algoritam)

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

početi

ponoviti

Napišite ("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 Rl;

dok R0 mod R1 0 čini

početi

R: = R0 mod Rl;

R0: = Rl;

R1: = R;

K: = K + R0 div R1

kraj;

Writeln ("SLJEDEĆI BROJ KVADRATA K =", K);

Članak učiteljice OIVT Liceja broj 8 Pangine N.N. iz časopisa "Računalni alati u obrazovanju", N1, 2000

Priprema učenika za olimpijade iz informatike.

Olimpijade iz informatike su u biti olimpijade iz programiranja. Rješavanje olimpijskih zadataka potpuno je samostalna nastavna sekcija s opsežnim teorijskim i praktičnim dijelovima.

Već šest godina, na bazi škole-liceja br. 8 u Sosnovym Boru, školarci se pripremaju za olimpijade različitih razina. Već pet godina učenici Liceja su pobjednici regionalnih olimpijada iz programiranja, sudionici i dobitnici sveruskih olimpijada.

Rješenja olimpijskih zadataka u gotovo svim fazama olimpijada, od regionalne do međunarodne, temelje se na dobro definiranim algoritmima koji su nadaleko poznati u matematici i informatici. A da biste uspješno riješili olimpijske probleme, prije svega morate svladati 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 sveučilištu, i to je sasvim razumljivo, budući da svladavanje ovih algoritama zahtijeva poznavanje nekih dijelova više matematike.

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

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

Štoviše, gotovo je nužan uvjet da ti studenti dodatno studiraju matematiku (bolje je da su to razredi s dubljim proučavanjem matematike). Nije slučajno da su naši ruski izvrsni školarci u području informatike bili jednako uspješni u matematici:

Victor Bargachev, 2-struki apsolutni svjetski prvak u informatici među školarcima, dobitnik je nagrade Međunarodne olimpijade iz matematike (srebrna medalja);

Nikolay 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 (2 puta apsolutni svjetski prvak u informatici) pobjednik je ruskih zonskih olimpijada iz matematike i fizike.

U Lenjingradskoj regiji mogu se navesti, na primjer, Aleksej Stratonikov, Aleksej Potapov, Artem Ananjev, Andrej Pangin.

2. pitanje ... U kojoj dobi trebate početi pripremati školarce?

Što prije to bolje, ali u razumnim granicama.

Za razinu

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

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

Primjer: prvak Moskve u programiranju među školarcima 1998., Pyotr Mitrichev, učenik 7. razreda, bio je najmlađi sudionik 9. Sveruske olimpijade za školarce iz informatike i sudionik trening kampa za pripremu ruskog tima za međunarodnu olimpijadu.

3. pitanje ... U kojem obliku provoditi nastavu u pripremi za olimpijade?

U obliku izbornih ili posebnih predmeta.

Za dobru pripremu učenika, govoreći dobro poznatom frazom, važno je, prije svega, "ne samo napuniti čašu znanja, nego i zapaliti baklju". Drugim riječima – uliti interes!

Prema iskustvu našeg liceja, to olakšava sljedeće:

Važnu ulogu imaju interdisciplinarne veze.

U Liceju već pet godina postoji poseban tečaj „Matematika na računalima“ za 5-6 razreda. Učenici se upoznaju s matematičkim pojmovima u vizualnom obliku (na primjer, animirani zamah kocke, koordinatna ravnina s cjelobrojnom mrežom), uče biti kreativni u rješavanju standardnih problema (na primjer, korištenjem grafičkog prikaza problema s transfuzijom i vaganjem na Računalo).

Razvijanje interesa olakšavaju lekcije na temu "Modeliranje gibanja" od najjednostavnijeg gibanja biljarske lopte do složene slike linija električnog polja dvaju naboja. Posebno je dojmljiva računalna simulacija "leta papirnatog aviona" i demonstracija ovog leta u stvarnosti. Zanimljiv je i problem simulacije kretanja satelita i određivanja prve, druge svemirske brzine, vremena leta rakete Vostok s Jurijem Gagarinom oko Zemlje (svi bi trebali znati ovaj događaj!).

Takva se nastava izvodi diferencirano prema stupnju pripremljenosti učenika.

Za 7. - 8. razrede organizira se školski kamp "Intelekt" tijekom prva dva do tri tjedna ljetnih praznika, gdje se djeca po posebnom programu bave informatikom.

Na primjer, program Labirint uključuje teme:

izgradnja labirinta (zanimljiv algoritam za generiranje slučajnog labirinta različite složenosti);

kretanje kroz labirint pomoću kontrolnih tipki;

tražiti izlaz iz labirinta, počevši od najjednostavnijeg prema pravilu lijeve strane (pridržavajući se jedne strane labirinta);

pronalaženje najkraćeg puta u labirintu.

Ovaj program učenicima daje poticaj da razviju vlastite igre hodalica i pucačina. Glavna stvar je spoznaja da oni sami to mogu stvoriti!

Za 10 razreda ljetna industrijska praksa organizira se u raznim poduzećima u gradu Sosnovy Bor u trajanju od mjesec dana. Studenti stječu vještine rješavanja praktičnih zadataka, učvršćuju znanja o radu s bazama podataka, računovodstvenim uredskim aplikacijama, samostalno izrađuju programe prema zadacima kustosa, stječu dodatna znanja (npr. pri radu s računalnim mrežama, operativnim sustavom Unix). Pohvalna recenzija poduzeća čest je rezultat takvog rada.

Djeca demonstriraju vlastite programe na tradicionalnom školskom skupu informatike "Mi i računalo", ove godine je već šesta konferencija. Najbolji razvoj softvera dečki godišnje prezentiraju 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 stupnja.

Kao nastavni materijal koriste se individualni programi.

Za grupu "ljubitelja računala" u dobrom smislu, a ne u smislu npr. računalnih igrica, izvode se posebno ciljani izborni predmeti i specijalni tečajevi na sljedeće teme: učenje dodatnog programskog jezika, algoritmizacija nestandardnih problemi, olimpijski zadaci, teorija grafova itd.

4. pitanje ... Koliko bi ljudi trebalo biti u posebno usmjerenim izbornim predmetima?

Grupe od 6 - 12 osoba.

Prilikom rada na određenom rezultatu (tj. priprema za gradsku, regionalnu ili rusku olimpijadu) treba biti grupa od 3 do 6 ljudi. Ovi razredi se već treniraju, a ovdje učitelj više djeluje kao trener, a ne kao učitelj. Kako ide lekcija?

Tema je imenovana.

Navedeni su zadaci na ovu temu.

Odabran je jedan od najpopularnijih ili najzanimljivijih zadataka.

Algoritam rješenja se usmeno razgovara s djecom.

Dečki pišu program, učitelj popravlja vrijeme, ocjenjuje implementaciju rješenja, pomaže u traženju pogrešaka, ukazuje na nedostatke u učinkovitosti (broj operacija, korištenje RAM-a, vrijeme rješenja).

Pitanje 5 ... Koje teme treba proučiti u pripremi za olimpijade?

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

Algoritmi nad cijelim brojevima.

Rekurzija.

Sortiranje.

Nabrojani zadaci.

Geometrijski problemi.

Numeričke metode.

Statističko modeliranje.

Grafovi i stabla.

Transformacije teksta.

Razmotrimo detaljnije teme potrebne za proučavanje u pripremi za olimpijade. Teorijske studije trebaju uključivati ​​definicije, izjave (u nekim slučajevima, nužno s dokazima).

Algoritmi nad cijelim brojevima

Djeljivost

Prilikom proučavanja ove teme potrebno je dati definicije djelitelja, višekratnika, prostih i koprostih brojeva, dati tvrdnje s dokazima o djeljivosti zbroja i razlici dvaju brojeva, o djeljivosti umnoška.

Prva modifikacija Euklidovog algoritma (s oduzimanjem)

Sukcesivno smanjujući brojeve (zamjenjujući veći s razlikom brojeva) dok ne postanu jednaki, dolazimo do najvećeg zajedničkog djelitelja tih brojeva.

Zadaci koje je potrebno riješiti prilikom proučavanja ove teme:

Odrediti je li više brojeva međusobno prostih

Smanji razlomak (unosi se brojnik i nazivnik razlomka)

Napišite program "Kalkulator" u jednostavnim razlomcima

Druga modifikacija Euklidovog algoritma korištenjem dijeljenja ostatka

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

Tako, smanjenjem brojeva, dobivamo najveći zajednički djelitelj kao zadnji ostatak koji nije jednak nuli.

Izazov za rješavanje: pravokutnik sa stranicama a i b, gdje su a i b prirodni brojevi, izrezani 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 dvaju brojeva u obliku linearne kombinacije tih brojeva, dolazimo do tvrdnje o rješivosti u cijelim brojevima jednadžbe oblika ax + by = c(Diofantova jednadžba).

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

Zadaci za razmjenu novca kovanicama određene vrijednosti.

Transfuzijski zadaci.

Prilikom proučavanja algoritma za rješavanje problema transfuzije čini se korisnim koristiti pomoćni demonstracijski i trening program "Overflow", uz pomoć kojeg studenti mogu praktično primijeniti proučavani algoritam. Potrebno je konsolidirati ovaj algoritam kako bi se pronašlo barem jedno rješenje Diofantove jednadžbe. Zatim je dan opći algoritam za rješavanje Diofantove jednadžbe s formulama za pronalaženje cijelog skupa rješenja.

primarni brojevi

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

Dvostruki brojevi;

Savršeni brojevi;

Ulam stolnjak;

Prijateljski brojevi itd.

Duga aritmetika

Dugi aritmetički problemi nastaju kada rezultat nije moguće pohraniti u standardne tipove podataka (cijeli ili dugi cijeli brojevi), jer je tako velik. U ovom slučaju koristi se tehnika pohranjivanja dugih brojeva u obliku niza znamenki, a za izvođenje aritmetičkih operacija s takvim brojevima potrebno je napisati posebne postupke za zbrajanje, množenje, dijeljenje dugih brojeva.

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

Rekurzija

Gotovo svaka knjiga o programiranju bavi se rekurzivnim i rekurzivnim postupcima i funkcijama. Ali vrlo je malo knjiga koje se detaljno bave temom rekurzije. Tradicionalno, razmatranje rekurzivne funkcije počinje pronalaženjem faktorijala broja. Kratka funkcija u jednom retku, ali nije jasno zašto je potrebno faktorijal razmatrati rekurzivno, ako se već smatra elementarnim samo u jednoj petlji s parametrom.

Što su učenici mlađi, to su im važnija načela jasnoće i jednostavnosti. Uvod u rekurziju može se započeti s dobro poznatom pjesmom "10 malih Indijanaca".

Sljedeći korak su rekurzivni crteži. Počinjemo s najjednostavnijim crtežima, na primjer, crtanjem pojednostavljene "gnijezdeće lutke".

pahulje koje padaju po cijelom ekranu;

grančice različitih boja, različite pahuljasti i različitih veličina (u dužinu grane se unosi slučajna komponenta).

Djecu jako zanimaju fraktalni setovi: salveta i stolnjak Sierpinski, Mandelbrotov model ljudskih pluća, Harter-Haytwayjev fraktal (kod nas poznat kao Zmajeva izlomljena linija), Hilbertove krivulje, Kochova snježna pahulja. Rekurzija je ovdje toliko prirodna da nitko ne postavlja pitanje je li moguće bez nje. I tek sada, kada nitko ne sumnja u ljepotu i ljepotu rekurzije, možete prijeći na zadatke koji su po definiciji rekurzivni. To su sljedeći zadaci: faktorijel broja, N-ti stepen broja, gcd ( a, b), Ackermanova funkcija, Fibonaccijevi brojevi, pretvaranje brojeva iz 10. brojevnog sustava u 2., pronalaženje maksimuma i minimuma u nizu. Mnogi se zadaci, pokazalo se, mogu obaviti pomoću rekurzije. Glavna stvar je da se vizija rekurzije pojavljuje u problemima koji prethodno nisu bili riješeni rekurzivno. U svrhu novosti, primjerice, u problemu rezanja pravokutnika na kvadrate najveće površine, predlaže se izrada vizualne grafičke pratnje pomoću rekurzije. I stvarno je "loše" bez rekurzije pri rješavanju problema poput Hanojske kule. U ovom slučaju, program demonstracije i obuke "Hanoi toranj" pomaže da se to ostvari i u praksi svlada rekurzivni algoritam za rješavanje ovog problema.

Sortiranje

Bez poznavanja algoritama za razvrstavanje, ne može se osjećati ugodno na olimpijadama različitih razina. Problemi se mogu formulirati eksplicitno uz spominjanje algoritma razvrstavanja, i podrazumijevajući korištenje algoritma sortiranja unutar rješenja. Dva najjednostavnija algoritma koje trebate znati su mjehurić i razmjena sortiranja (traženjem uzastopnih minimuma). Za male količine podataka ove dvije metode su sasvim dovoljne, ali pri radu s podacima mjerenim u desecima i stotinama KB potrebno je poznavanje jedne od brzih sorti. Prednost se može dati Hoare brzom sortiranju, koje se implementira rekurzivno. Također biste trebali biti upoznati s nekim trikovima prilikom organiziranja podataka u velikim datotekama. Cijela datoteka je podijeljena u nekoliko dijelova koji se mogu razvrstati pomoću QSORT-a, a zatim spojiti sortirane datoteke bez programa za sortiranje (usput rečeno, ovo je vrlo koristan zadatak s tehničke točke gledišta, koji zahtijeva točnost i dobro programiranje tehnika).

Nabrajanje opcija

Zadaci nabrajanja čine ogromnu klasu olimpijskih zadataka. Nabrajanje počinje najjednostavnijim traženjem minimuma i maksimuma u jednodimenzionalnom nizu ili elementu s određenim svojstvima. Zatim slijedi nabrajanje parova elemenata pomoću ugniježđene petlje, zatim nabrajanje trojki elemenata pomoću trostruke petlje (kao, na primjer, u problemu pronalaženja tri točke na ravnini između zadanih N točaka koje tvore trokut s maksimalna površina). A ako razvrstate kombinacije 4, 5, 6, itd. elementi? Koliko je ciklusa potrebno? Ispada da postoje algoritmi koji značajno smanjuju pretragu.

Dosta dugo u vremenu izvršenja, ali jedan od najsvestranijih algoritama grube sile je vraćanje ili vraćanje unatrag. Programibilno rekurzivno. Najbolje objašnjeno na sljedećim zadacima:

Viteškim potezom obiđite šahovsku ploču N * M;

Postavite 8 kraljica na šahovsku ploču 8 * 8 tako da ne prijete jedna drugoj;

Pronađite izlaz iz labirinta itd.

Također je potrebno objasniti studentima da je u slučaju predugog vremena izvođenja programa potrebno ograničiti "backtracking". Na primjer, u šahovskom problemu s pločom veličine 8 * 8, program radi već duže vrijeme. Moguće je, pa čak i potrebno primijeniti simetriju, zrcaljenje, dovršavanje zadatka za polovicu ili četvrtinu šahovske ploče.

Klasični problem "backtracking" je problem "ruksaka", a zatim se mogu uzeti u obzir derivati ​​ovog problema:

Podijelite N brojeva na dva podskupa koji su zbrojem najbliži;

Iz zadanog skupa riječi odaberite maksimalan podniz riječi u rječničkom redoslijedu.

Kombinatorni problemi također su povezani s nabrajanjem. Trebali biste svladati algoritme za kreiranje leksikografskog reda.

Problemi s geometrijom

Obvezni minimum koji morate znati pri rješavanju geometrijskih problema uključuje sljedeće:

Da bi se jednadžba ravne koja prolazi kroz dvije točke mogla dovesti u oblik

Ax + By + C = 0;

Znati odrediti pripada li točka pravoj liniji ili segmentu;

Da biste mogli odrediti sijeku li se dvije ravne, a sijeku li se, onda odredite njihovu točku sjecišta (za to izračunajte determinantu 2. reda);

Znati napisati jednadžbu okomite linije ili odrediti je li jedan pravac okomit na drugi (koristeći svojstvo da je skalarni umnožak okomitih vektora jednak nuli);

Znati izračunati udaljenost od točke do ravne linije.

Osim toga, za rješavanje problema na regionalnoj i sveruskoj razini potrebno je poznavanje početnog tečaja analitičke geometrije: skalarni i križni produkt vektora, njihov izraz kroz koordinate. Točkasti proizvod se koristi za pronalaženje kuta (ili kosinusa kuta) kada se konstruira, na primjer, konveksna trupa zadanih točaka. Unakrsni umnožak dvaju vektora koristi se, prvo, za izračunavanje površina poligona, a kao drugo, za određivanje smjera u odgovarajućim problemima. Ovo znanje je također potrebno kako bi se riješio takav klasični olimpijski problem kao što je nalazi li se točka unutar proizvoljnog poligona.

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

modul brojčane vrijednosti određuje površinu paralelograma izgrađenog na zadanim vektorima;

nulta vrijednost - paralelizam vektora;

znak znači da se jedan vektor nalazi "lijevo" ili "desno" u odnosu na drugi;

rezultirajući vektor definira normalu na ravninu zadanih 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 približnih vrijednosti korijena nelinearnih jednadžbi, može se koristiti za pretraživanje kroz "ogromnu" količinu podataka. U ovom slučaju više ćemo koristiti izraz "binarna pretraga". Tipičan zadatak je pronaći zadanu riječ u rječniku.

Općenito, ova metoda je optimalna.

Rješavanje sustava linearnih jednadžbi: Cramerova metoda, Gaussova metoda.

Klasične metode. Obično u problemima broj jednadžbi nije veći od tri. Ali poznavanje općeg slučaja vjerojatno će dobro doći.

Problem s regionalne olimpijade '94.

Jednadžba kemijske reakcije upisuje se u obliku linije: potrebno je izjednačiti, t.j. postavite koeficijente.

Statističko modeliranje (Monte Carlo metoda).

Poznavanje ove metode je vrlo korisno:

za simuliranje vjerojatnosnih situacija u igri (bacanje novčića, kocke, lutanje). To je “igra” ili vezana uz nešto poznato (poznato, “svakodnevno”) formulacija problema koja pomaže u razumijevanju metode, koncepta vjerojatnosti. Učenicima možete ponuditi zanimljive zadatke:

što je više, poništivi ili nesvodljivi razlomci? (Matematička formulacija: procijeniti vjerojatnost da je slučajni razlomak nesmanjiv);

najbolja opklada za prostake ("Quant" br. 5.1987);

kombinatorni problemi.

Za određivanje područja brojki kada su analitičke odluke teške.

Dakle, u zadatku (regionalna olimpijada 1999.) za pronalaženje područja presjeka triju kružnica, Monte Carlo metoda se može koristiti kao alternativa izravnoj analitičkoj metodi, jer je vrlo teško izvesti rješenje pomoću trigonometrije odnosima. Najbolji način je "koristiti geometriju" za analizu posebnih slučajeva (kada nema raskrižja, kada je sjecište u jednoj točki, jedna kružnica je unutar druge), a Monte Carlo metoda je za opći 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 za sljedeće korake, onda to znači da u ovom U slučaju da je primjenjiv princip dinamičkog programiranja.

Ovo načelo najlakše je uočiti za specifične zadatke. No, njegovo objašnjenje može se započeti zabavnom pričom o zlatnim faraonovim ljestvama (izneseno u časopisu "Quant" 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 zbroj znamenki u ćelijama minimalan ili maksimalan.

Pronalaženje općeg podniza maksimalne duljine (problem koji je proizašao iz suvremenog stvarnog problema molekularne biologije o općim genetskim informacijama u molekulama DNA).

Grafovi i stabla.

Vrlo važna tema. Gotovo nijedna olimpijada na ruskoj razini nije potpuna bez upotrebe nekog algoritma na grafovima. Potrebno je uvesti pojam grafa kroz vrhove i bridove, pojam usmjerenih ili neusmjerenih grafova, rastaviti metode predstavljanja grafova u obliku matrice, susjednosti, matrice incidencije, popisa poveznica.

Analizirajte osnovne algoritme grafa:

pretraživanje u dubinu (drugim riječima, "backtracking" ili brute-force s backtracking);

Breadth First Search (ili metoda popunjavanja);

Dijkstraov algoritam za pronalaženje najkraćih putova u grafu od zadanog vrha do svih ostalih;

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

Transformacije teksta

Zadaci u kojima je potrebno raščlaniti niz ponekad dodatno uključuju rad s 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 problemu ispravnog izraza zagrade za nekoliko vrsta zagrada).

Prikazan je širok, ali daleko od cjelovitog niza tema koje obrađuju olimpijada. To uvelike ovisi o preferencijama organizatora olimpijada različitih razina (teorijski krugovi, problemi s korištenjem strategija igre, primijenjena "uredska" priroda).

Pitanje 6 ... Što možete savjetovati pri rješavanju zadataka na olimpijadi?

Pod pretpostavkom da je teorija algoritama "proučena" i savladane osnove programiranja, natjecatelju se može savjetovati sljedeće:

Osigurajte "u pričuvi" određeni "zajamčeni" (po vašem mišljenju) skup bodova za jednostavne zadatke. To ne znači da se teški zadaci ostavljaju posljednjem trenutku. Kada se razmišlja o njihovom rješenju, može se pronaći “dobar” algoritam, a odgovarajući veliki udio bodova bit će uspješan.

Ako vam je problem težak ili nedostaje vremena za rješavanje, programirajte jednostavne posebne slučajeve ( može biti neki testovi će proći) ili koristite neki neoptimalan algoritam, na primjer, iscrpni algoritam pretraživanja.

Ako je određeno vremensko ograničenje za problem, a vaš algoritam iscrpnog pretraživanja ne uklapa se u to vrijeme, tada u algoritam umetnite mjerač vremena koji, kada se približi kritičnom vremenu, završava problem i prikazuje najbolju pronađenu opciju iscrpnog pretraživanja ( možda je točno).

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

Strogo poštujte ulazno-izlazne formate navedene u izjavi o problemu: "auto-tester" može pogrešno uočiti dodatni razmak ili izvorni testovi sadrže zarez gdje ste naveli razmak u unosu zadatka (značajke Pascala i Osnovni operatori unosa).

U osnovi, svaki program ima strukturu:

Unos podataka

Blok naselja

Izlaz rezultata

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

Supply compiler se prebacuje za rukovanje svim vrstama pogrešaka (korisno za otklanjanje pogrešaka), a prije slanja zadatka onemogućite ove opcije (kako biste zanemarili prevodilac zbog mogućih pogrešaka testiranja koje ne utječu na rješenje).

Provjerite problem za data maksimalna ograničenja (na primjer, ako je dano n  1000, provjerite n = 1000). Pratite vrstu deklariranih varijabli (poželjno je koristiti tip "dugi cijeli broj" za opisivanje cjelobrojnih varijabli).

Iskoristite svoju žalbu mudro. Moguća je nejasnoća u razumijevanju problema. U žiriju su i ljudi, a vi možete braniti svoj stav, uvjeriti ih da dodaju bodove koje želite.

U krajnjoj nuždi, ako ste "kul haker" (kul stručnjak za dio sustava), pokrenite program "susjeda" kao svoj (vjerojatno nitko neće primijetiti).

Dopušteno vam je imati vlastite cheat sheets (ne u elektroničkom obliku) ili koristiti "slobodno" vrijeme za proučavanje referentne literature.

Neki od navedenih savjeta su "štetni", odgovaraju načelima "možda, pretpostavljam, i nekako". Molim vas, shvatite ih kritički, ali oni su vitalni.

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

Ovaj članak, kao i sljedeći izvori.

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

A.L.Brudno, L.I.Kaplan. Moskovske olimpijade iz programiranja, M: Znanost, 1990.

V. A. Dagen, G. K. Grigas. 100 programskih problema, M: Obrazovanje, 1993.

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

V.M.Kirjuhin, A.V. Lapunov, S.M. Okulov. Informatički zadaci. 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. Olimpijade za školarce 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 rješavati olimpijske zadatke iz informatike, morate riješiti probleme iz informatike... Naravno, gledajući relevantnu literaturu.

Pitanje 2. Koliko je zadataka potrebno riješiti da bi se na informatičkim olimpijadama moglo adekvatno nastupiti?

Pitanje naravno nije ispravno postavljeno i vjerojatno je teško na njega odgovoriti, ali vrijedi reći nekoliko riječi o tome. Kako mi je rekao Mihail Medvedev, stručnjak za područje priprema za ACM olimpijade, stvaranje temeljno novog olimpijskog problema nije tako lako kao što se na prvi pogled čini. Iz tog razloga odgovorni za olimpijade jednostavno uzmu probleme iz prošlih godina i serviraju ih pod "novim umakom". Često se događa da se problemi za regionalne i zonske olimpijade iz informatike "otrgnu" bez ikakvih promjena sa stranica posvećenih programiranju olimpijada.

Dakle, budući da su mnogi zadaci vrlo, vrlo slični, potrebno je naučiti rješavati probleme iz cijelog niza: sortiranje, dinamičko programiranje, duga aritmetika itd.

Pitanje 3. Je li moguće pripremiti školarce za olimpijade iz informatike u sklopu školskog programa?

Mislim da je ovo nerealno. Svi već odavno znaju da je školski kolegij informatike jedno, a olimpijade iz informatike nešto sasvim drugo. Da, u oglednom programu informatike za 9. razred dosta sati je posvećeno učenju programiranja. U Semakinovom udžbeniku za 9. razred programiranje se temelji na jeziku Pascal, Ugrinovich daje primjere u odnosu na Visual Basic. No, čak i ako primijenimo diferenciran pristup poučavanju školaraca, malo je vjerojatno da će ti sati biti dovoljni za pripremu pojedinih školaraca za olimpijade od nule.

Pitanje 4. Ako sati programa nisu dovoljni za pripremu školaraca za olimpijade, kako se onda pripremati?

Na prve dvije opcije sve je jasno, ali mora postojati razumijevanje od strane vodstva škole. Često postoji "bitka za sat" između nastavnika i možda neće spadati u razred ili izborni predmet o programiranju sata.

Osobni entuzijazam doveden do ekstremne mjere je, po mom mišljenju, vrlo pogubna pojava. Rusko obrazovanje ne treba voditi entuzijazmom. Inače, ispada da dok god postoji entuzijazam, stvari idu, fitilj je prestao i sve se urušilo. Nećete dugo izdržati na entuzijazmu, ali ponekad to treba pokazati u nadi da će se stvar pokrenuti.

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

Čini mi se da je s takvim opterećenjem realnije poludjeti nego pripremati učenike za olimpijade. Iskreno suosjećam sa svim učiteljima s velikim opterećenjem. Razumijem da uzimanje velikog broja sati ne proizlazi iz dobrog života, ali ne razumijem kako možete raditi u takvim uvjetima.

Pitanje 6. Mogu li se školarci pripremati za olimpijade izvan školskih sati i ako mogu, kako najbolje organizirati pripremu?

Mogu, ali bi barem trebali imati kućno računalo. U idealnom slučaju, trebao bi postojati i internet. Ako imate računalo i internet, probleme možete riješiti na jednoj od specijaliziranih stranica s automatiziranom provjerom rješenja, na primjer, na web stranici Škole programera.

Pitanje 7. Što je potrebno od učitelja za kvalitetnu pripremu školaraca za olimpijadu?

• Sposobnost učenja. Uostalom, kako to biva, osoba je završila obrazovnu ustanovu i tu ponekad završava njegov razvoj u smislu dobivanja informacija. Čini se da je dovoljno za rad u školi, pa zašto se mučiti...
• Uvijek budite u kontaktu. Vaš učenik može imati pitanje u bilo kojem trenutku, jer ima onih koji probleme rješavaju noću. Ako ne možete spavati, zašto ne, ako je moguće, on ne može odgovoriti pomoću istog ICQ ili Skype softvera.

Metodika pripreme za olimpijade iz informatike

Relevantnost teme

U vezi s aktualizacijom i aktiviranjem olimpijadnog pokreta, sve je akutniji problem pripreme učenika za sudjelovanje na olimpijadama. Priprema „učeničke olimpijade“ počinje pripremom nastavnika.

Problemi s kojima se susreće učitelj:

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

2. Poznavanje algoritama za rješavanje olimpijskih zadataka.

3. Prisutnost samih zadataka.

4. Poznavanje programskih jezika.

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

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

Unatoč činjenici da je raspon zadataka koji se razmatraju na natjecanju iz programiranja ograničen, rješavanje problema može biti teško ne samo za studenta, već i za nastavnika, jer neki problemi zahtijevaju poznavanje više matematike. Obično je potrebno puno vremena za validaciju rješenja i pripremu testova.

Evo nekih značajke pripreme školaraca za programiranje olimpijada :

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

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

· Konstantni treninzi su gotovo na atletskoj razini.

· Veliki utrošak vremena, trajanje olimpijade s raščlanjivanjem često prelazi 6 sati.

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

Naravno za nastavnike je također neophodna viša obuka za rad s darovitim učenicima koji sudjeluju na olimpijadama iz programiranja:

· Eventualno drugo obrazovanje, specijalizirano sveučilište za programiranje.

· IPC učitelji, tečajevi učenja programskih jezika, programiranje olimpijada.

· Samopriprema korištenjem materijala iz dodatnih izvora.

Ali ni dobro poznavanje programskog jezika ne daje 100% jamstvo da će učenik pobijediti čak ni na školskoj ili regionalnoj olimpijadi.

Pedagoška ideja

Glavni poticaj učenika za sudjelovanje na olimpijadama je motivacija. 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 pružite priliku drugim učenicima (čak i nesudjelujući na olimpijadi) da "zarade ocjenu". ).

Želja učenika za vodstvom, demonstracijom vlastitih postignuća jedan je od temeljnih uvjeta za sudjelovanje u olimpijadnom pokretu. Naravno, uz takvu motivaciju ima dovoljno ljudi koji žele raditi, ali u toku rada dolazi do djelomične rotacije i to je neminovno s obzirom na trenutnu opterećenost školaraca. Uglavnom, tu su vrijedna djeca, oni učenici koji se ne boje poraza i postavljaju si konkretne ciljeve.

Jedna od glavnih pokretača učeničkog sudjelovanja na programerskim olimpijadama je želja i interes učitelja, kao i pomoć, strpljenje i povjerenje roditelja.

1964. V. Vroom je predložio “teoriju očekivanja”. Vjerovao je u to poticaj za učinkovit i kvalitetan rad ovisi o kombinaciji tri čimbenika – očekivanja osobe:

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

2. Očekivanje da će rezultati za sobom povlačiti nagrade.

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

Što više osoba vjeruje da će sva ta očekivanja biti opravdana, to će biti jači poticaj za djelovanje. Ako malo promijenimo formulaciju V. Vrooma u obrazovnom kontekstu, onda ćete dobiti sljedeće:

Teorija očekivanja pokazuje što učitelji trebaju učiniti kako bi imali jake poticaje za učenike da uče:

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

o Uspostaviti izravnu vezu između uspješnosti i ocjenjivanja učenika;

o Istražite potrebe učenika kako bi znali koje su nagrade za njih vrijedne.

Na temelju toga, mehanizmi motivacije i glavni čimbenici učinkovitosti poticaja mogu se izraziti kao:

o Poznavanje od strane nastavnika potreba, interesa, potreba učenika.

o Uspostavljanje poštene i izravne veze između učinka i nagrade.

o Hitnost nagrade.

o Stupanj zadovoljenja očekivanja.

Da biste se pripremili za olimpijade iz programiranja, metodologiju možete primijeniti pomoću sustava testiranja "NSUTS" , razvijen na temelju NSU-a, koji vam omogućuje brzo rješavanje mnogih od ovih točaka.

Tehnologija korištenja sustava"NSUTS »

Sustav se nalazi na adresi https: // olimpijski. ***** / nsuts-test / nsuts_new_login. cgi... Kada kliknete na ovu poveznicu, dolazimo do stranice za autorizaciju, gdje unosom korisničkog imena i lozinke možete ući u sustav.

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

U ovom slučaju biramo npr. Školski treninzi, nakon čega ćete biti preusmjereni na stranicu " Stranica za registraciju školskih treninga", gdje je registracija jednostavna i jasna. Samo trebate uzeti u obzir da podaci koje unosite moraju biti pouzdani.

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

Na kartici " Pomozite»Možete pročitati kratku uputu za rad u sustavu. Pogledajmo sadržaj ove stranice.

NSUTS sustav za ispitivanje. Vrlo kratak opis.

Nalazite se u automatiziranom sustavu testiranja NSUTS-a za provođenje i provjeru olimpijada iz programiranja. Trenutni odjeljak prikazuje se na vrhu zaslona. U gornjem desnom kutu - naziv trenutne olimpijade, naziv vašeg tima i gumb za izlazak iz rada sa sustavom - " Odjaviti se».

U poglavlju " Obilazak»Možete odabrati trenutni krug olimpijade.

U poglavlju " vijesti»Možete pročitati najave i komentare žirija i organizacijskog odbora Olimpijade. Također saznajte vrijeme početka i završetka olimpijade. Nakon početka olimpijade na ovoj stranici pojavljuju se poveznice na uvjete zadatka.

U poglavlju " Proći»Zadaci se šalju na testiranje. Za slanje problema na testiranje navedite jezik na kojem je rješenje napisano i broj problema. Zalijepite tekst rješenja u polje za unos i kliknite na " poslati". Ili odaberite datoteku pomoću retka za odabir datoteke, a zatim kliknite " poslati". Vaše rješenje će se pojaviti na popisu poslanih zadataka u odjeljku “ rezultate».

Vaša rješenja trebaju čitati unos iz datoteke ulazni. txt i ispisati rezultat u datoteku izlaz. txt ... Zabranjeno je čitanje iz standardnog ulaznog toka, pisanje u standardni izlazni tok i standardni tok grešaka. Program Contributor ne smije otvarati, čitati ili mijenjati datoteke osim ulaznih. txt i izlaz. txt ili druge navedene u izjavi problema. Pristup datotečnom sustavu i drugim resursima osim onih navedenih u opisu problema je zabranjen. Kršenje ovog zahtjeva 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 opisu problema.

Sudionik može koristiti bilo koji prevodilac naveden u odjeljku “ 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, - stog = - O2 zadatak. cpp
Freepascal 2.2.0	ppc386.exe - O2 - Cs zadatak. pas
Java 1.6.0_07	javac. exe Zadatak. Java
TrčanjeJava	java - Xmx480m - Xss32m - Djava. sigurnost. upravitelj - Duser. jezik = hr_US Zadatak
Borland Delphi 2006

U odjeljku " rezultate»Možete vidjeti status testiranja i rezultate testiranja problema koje ste poslali. U redu " Vrijeme»Naznačeno je vrijeme u trenutku isporuke rješenja, programski jezik koji ste naveli prilikom slanja ovog rješenja. Veza " View izvor»Pokazat će tekst donesene odluke.

U redu " Proizlaziti»Prikazuje se rezultat testa:

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

Testiranje ... se trenutno testira.

Prekoračeno je ograničenje izvornog koda - prekoračeno je ograničenje izvornog koda programa.

Pogreška kompajliranja - kompajliranje 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 zadovoljilo dodijeljeno procesorsko vrijeme.

Timeout - rješenje nije ispunilo zadano vrijeme.

Run-time Error - rješenje je vratilo kod pogreške različit od nule.

Prekoračeno je ograničenje memorije - rješenje se nije uklapalo u dodijeljeno ograničenje memorije.

Nema izlazne datoteke - nema izlazne datoteke. txt.

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

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

Kratko pravilo za konstruiranje ocjene za ACM olimpijade je sljedeće: od dvije ekipe, ona će biti viša u ocjeni, koja je riješila veći broj problema; ako je broj zadataka isti, onda je tim s kraćim kaznenim vremenom veći. Ako su broj zadataka i kazneno vrijeme isti za nekoliko ekipa, tada te ekipe zauzimaju nekoliko uzastopnih mjesta.

Kazneno vrijeme je zbroj kaznenog vremena za sve probleme. Kazneno vrijeme za jedan zadatak je 0 ako se zadatak ne preda. Ako je zadatak dostavljen, tada se njegovo kazneno vrijeme izračunava po formuli:

vrijeme_podnošenja_ispravnog_rješenja + (broj_neuspjelih_pokušaja * 20).

odjeljak " Pitanja i odgovori„Namijenjen je komunikaciji s žirijem Olimpijade. Žiriju možete postaviti pitanja o terminima problema ili ukazati na netočnost formulacije problema.

Osim toga, ako Ocjenjivački sud smatra potrebnim promijeniti uvjete problema, izmjene će biti objavljene u ovoj rubrici ili u vijestima.

Sada kada smo se upoznali s osnovama rada u sustavu, razmotrit ćemo, kako mogu dobiti zadatak za olimpijadu.

Na kartici "Obilazak" odaberite potrebnu Olimpijadu, na primjer, " Priprema za Sverusku olimpijadu 21.03.2010 (geometrija) "... Nakon toga idite na karticu "Vijesti" i kliknite na poveznicu "Uvjet obilaska" kako biste preuzeli MS Office Word datoteku koja sadrži zadatke predane na rješavanje u ovom krugu.

Nakon što smo riješili problem, na kartici "Pass", šaljemo ga na provjeru, postavljajući sve potrebne parametre (jezik, tekst programa ili datoteku s programom). Rezultate provjere možete pronaći na kartici "Rezultati".

Glavne klase zadataka postavljenih na informatičkim olimpijadama

Da biste uspješno završili ne samo olimpijadu, već i zadatke unutar razreda, trebate:

1. Tečno govoriti jezik i programsko okruženje (u našem slučaju to je Free Pascal), biti sposoban graditi i implementirati različite algoritme koristeći ovaj jezik.

2. Posjedovati potreban matematički aparat.

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

Programski problemi Olimpijade pokrivaju vrlo širok raspon znanja, ali najčešće se susreću i uzrokuju najveće poteškoće su sljedeći:

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

2. Grafovi, kao skup objekata s mnogo veza.

3. Problemi pomoću analitičke geometrije i temeljeni na konceptu "vektora".

4. Problemi dinamičkog programiranja.

Razmotrimo ove klase zadataka detaljnije.

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

Programi se sastoje od algoritama i struktura podataka. Dobri programi iskorištavaju i jedno i drugo. Odabir i projektiranje struktura podataka jednako je važno kao i projektiranje postupka koji njima manipulira. Organizacija informacija i načini pristupa njima obično su određeni prirodom zadatka s kojim se programer suočava. Stoga bi svaki programer u svojoj "prtljazi" trebao imati odgovarajuće metode predstavljanja i pronalaženja podataka, koje se mogu primijeniti u svakoj konkretnoj situaciji.

U stvarnosti, računalne strukture podataka izgrađene su na temelju osnovnih tipova podataka kao što su "char", "integer", "real". Na sljedećoj razini nalaze se 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 prezentacije podataka više ne razmatraju, pozornost se posvećuje redoslijedu kojim se podaci nalaze. pohranjena i u kojoj se traži. U osnovi, fizički podaci povezani su s "podatkovnim strojem" koji upravlja načinom na koji se pristupa informacijama u vašem programu. Postoje četiri takva "stroja":

1. red čekanja;

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

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

4) T. Cormen. Algoritmi. Konstrukcija i analiza. 2. izd. stranica 255

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

Grafovi su poput skupa objekata s mnogo veza.

Graf je apstraktni matematički objekt. Sastoji se od vrhova i bridova. Svaki brid povezuje par vrhova. Ako nekoliko bridova povezuje isti par vrhova, onda se ti bridovi nazivaju višestruki. Rub koji povezuje vrh sa sobom naziva se petlja. Možete hodati po rubovima grafa, krećući se od jednog vrha do drugog. Ovisno o tome je li moguće hodati po rubu u oba smjera ili samo u jednom, razlikuju se neusmjereni i usmjereni grafovi. Orijentirani bridovi nazivaju se lukovi. Ako svi bridovi grafa imaju težine (tj. neki broj koji jedinstveno odgovara danom bridu), tada se graf naziva ponderiranim. Vrhovi spojeni bridom nazivaju se susjedni. Za neusmjereni graf, stupanj vrha je broj bridova uključenih u njega. Za usmjereni graf, stupanj se razlikuje po ulaznim, a stupanj po izlaznim bridovima. Graf se naziva potpunim ako postoji brid između bilo kojeg para različitih vrhova.

Graf je apstraktan objekt i možemo ga interpretirati na različite načine, ovisno o konkretnom zadatku. Pogledajmo primjer. Vrhovi grafa neka budu gradovi, a rubovi ceste koje ih povezuju. Ako ceste imaju jednosmjerni promet, tada je graf orijentiran, inače neusmjeren. Ako se cestama plaća cestarina, tada se graf ponderira.

Prikladno je prikazati graf na papiru, prikazujući vrhove s točkama, a rubove - linijama koje povezuju parove točaka. Ako je graf orijentiran, na linijama treba nacrtati strelicu koja označava smjer; ako je graf ponderiran, tada je na svaki brid također potrebno upisati broj - težinu brida.

Postoji nekoliko načina za predstavljanje grafa u memoriji računala. Nadalje, teoriju možete pronaći na poveznicama:

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

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

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

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

Problemi s korištenjem analitičke geometrije i temeljeni na konceptu "vektora"

Računalna geometrija je grana računalne znanosti koja proučava algoritme za rješavanje geometrijskih problema. Takvi problemi nastaju u računalnoj grafici, dizajnu integriranih sklopova, tehničkih uređaja itd. Početni podaci u takvim problemima mogu biti skup točaka, skup segmenata, poligon itd. Rezultat može biti ili odgovor na pitanje (kao što je "sijeku jesu li to ravne linije"), ili neki geometrijski objekt (na primjer, najmanji konveksni poligon koji sadrži zadane točke).

U "Informatici" broj 14 objavljen je članak jednog od autora posvećen problemima računske geometrije na olimpijadama iz informatike. Konkretno, tu je formuliran niz elementarnih podproblema na kojima se temelji rješenje većine problema računske geometrije. No, nastava i s matematički dobro pripremljenim srednjoškolcima pokazala je da im rješavanje ovakvih podzadataka izaziva velike poteškoće. Problem ih ili zbunjuje, ili je odabrano "frontalno" rješenje toliko komplicirano da ga učenici ne mogu riješiti bez grešaka. Analiza rezultata rješavanja "geometrijskih" zadataka na Sveruskim olimpijadama iz informatike dovodi do istih zaključaka. Koristeći donje poveznice, možete proučavati pristupe rješavanju geometrijskih problema na ravnini, koji vam omogućuju da brže i što jednostavnije dobijete rješenja za većinu elementarnih podproblema.

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

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

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

Problemi s dinamičkim programiranjem.

Mnogi olimpijski zadaci, kao i praktični problemi programiranja, problemi su nabrajanja opcija i odabira između tih opcija prihvatljivog ili najboljeg prema jednom ili drugom kriteriju. Međutim, razmatranje svih opcija, zbog iznimno velikog broja njih, često nije moguće.

Srećom, za niz problema koji su po formulaciji slični problemima koji doista zahtijevaju iscrpnu pretragu opcija, može se pronaći puno učinkovitije 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 pamte u tablici i nikada više ne preračunavaju, a podproblemi veće dimenzije koriste ta već pronađena rješenja. Ova metoda se naziva dinamičko programiranje, a naziva se i metodom tablice. U svom općem obliku, dinamičko programiranje shvaća se kao proces postupnog rješavanja optimizacijskog problema, u kojem se u svakom koraku odabire jedno od skupa izvedivih rješenja, čime se optimizira zadana ciljna ili kriterijska funkcija. Ponekad se, umjesto optimizacijskog, istom metodom rješava problem izračunavanja broja izvedivih rješenja. U tom se slučaju na svakom koraku umjesto odabira optimalnog rješenja zbrajaju rješenja podproblema niže dimenzije, koja se u svojoj formulaciji ne podudaraju 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 tablicu. Veza između zadataka i podzadataka u pravilu se formulira u obliku određenog “načela optimalnosti” i izražava se sustavom jednadžbi (rekurzivnih odnosa).

Temelje teorije dinamičkog programiranja postavio je R. Bellman. Imajte na umu da riječ “programiranje” u gornjem nazivu (dinamičko programiranje), kao i u “linearnom programiranju” (linearno programiranje), ne znači pisanje programa za računalo.

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

1) odabrati i opisati podprobleme kroz čije rješenje će se izraziti željeno rješenje,

2) zapisati rekurentne relacije (jednadžbe) koje povezuju optimalne vrijednosti parametra za podprobleme,

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

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

Ako nas zanima samo vrijednost parametra, tada korak 4 u algoritmu nije potreban (ova situacija je tipična, na primjer, za probleme izračunavanja broja dopuštenih opcija ili nekih konfiguracija, uključujući kombinatorne). Međutim, ako je potrebno konstruirati najoptimalnije rješenje, ponekad je potrebno dobiti i pohraniti dodatne informacije u procesu izvođenja koraka 3 algoritma. Često se pokaže da je korak 4 najteži kod implementacije takvih algoritama.

1) http: // ***** / blogovi / algoritam / 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) Problemi i rješenja http: // ***** / olimp / rec_prb. php

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

"Olimpijade iz informatike: Metodika priprema"

Materijal pripremio:

IT-učitelj

Galitskaja Irina Viktorovna

U vezi s aktualizacijom i aktiviranjem olimpijadnog pokreta, sve je akutniji problem pripreme učenika za sudjelovanje na olimpijadama. Priprema „učeničke olimpijade“ počinje pripremom nastavnika.

Problemi s kojima se susreće učitelj:

· Proučavanje novih oblika vođenja olimpijada.

· Poznavanje algoritama za rješavanje olimpijskih zadataka.

· Prisutnost samih zadataka.

· Poznavanje programskih jezika.

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

· Podučavanje učenika pravilnoj organizaciji aktivnosti na olimpijadi.

Unatoč činjenici da je raspon zadataka koji se razmatraju na natjecanju iz programiranja ograničen, rješavanje problema može biti teško ne samo za studenta, već i za nastavnika, jer neki problemi zahtijevaju poznavanje više matematike. Obično je potrebno puno vremena za validaciju rješenja i pripremu testova.

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

Evo nekih značajki pripreme školaraca za programiranje olimpijada:

1. U školskom kurikulumu nema takvog predmeta “programiranje”. Oni. pripravnik mora imati vlastitu prilično jaku motivaciju.

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

3. Stalni treninzi su gotovo na atletskoj razini.

4. Veliki utrošaci vremena, trajanje olimpijade s raščlanjivanjem često prelazi 6 sati.

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

Naravno, za rad s darovitim učenicima koji sudjeluju na programerskim olimpijadama potrebna je i viša razina obuke:

· Eventualno drugo obrazovanje, specijalizirano sveučilište za programiranje.

· Tečajevi učenja programskih jezika, programiranje olimpijada.

· Samopriprema korištenjem materijala iz dodatnih izvora.

Ali ni dobro poznavanje programskog jezika ne daje 100% jamstvo da će učenik pobijediti čak ni na školskoj ili regionalnoj olimpijadi.

Pedagoška ideja iskustva

Glavni poticaj učenika za sudjelovanje na olimpijadama je motivacija. Sposobnost pokazivanja znanja i erudicije o problemu koji se rješava.

Želja učenika za vodstvom, demonstracijom vlastitih postignuća jedan je od temeljnih uvjeta za sudjelovanje u olimpijadnom pokretu. Naravno, uz takvu motivaciju ima dovoljno ljudi koji žele raditi, ali u toku rada dolazi do djelomične rotacije i to je neminovno s obzirom na trenutnu opterećenost školaraca. Uglavnom, tu su vrijedna djeca, oni učenici koji se ne boje poraza i postavljaju si konkretne ciljeve.

Jedna od glavnih pokretača učeničkog sudjelovanja na programerskim olimpijadama je želja i interes učitelja, kao i pomoć, strpljenje i povjerenje roditelja.

1964. V. Vroom je predložio “teoriju očekivanja”. Vjerovao je da poticaj za učinkovit i kvalitetan rad ovisi o kombinaciji tri čimbenika – očekivanja osobe:

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

2. Očekivanje da će rezultati za sobom povlačiti nagrade.

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

Što više osoba vjeruje da će sva ta očekivanja biti opravdana, to će biti jači poticaj za djelovanje. Malo sam promijenio formulaciju V. Vrooma u obrazovnom kontekstu i dogodilo se to.

Teorija očekivanja ističe što učitelji trebaju učiniti kako bi imali jake poticaje za učenje za svoje učenike:

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

· Uspostaviti izravnu vezu između uspješnosti i ocjenjivanja učenika.

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

Na temelju toga, mehanizmi motivacije i glavni čimbenici učinkovitosti poticaja mogu se izraziti kao:

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

2. Uspostavljanje poštene i izravne veze između rezultata i nagrada.

3. Hitnost nagrade.

4. Stupanj zadovoljenja očekivanja.

Doživite tehnologiju

Naravno, priprema za olimpijade je dug i naporan proces.

Korištenje načela "Ono što si zaradio, to si i dobio" omogućuje stvaranje potrebe za povećanjem kognitivne aktivnosti učenika, njihova samoizražavanja i interesa za produktivne aktivnosti učenja, želju za pokazivanjem vlastitih postignuća.

Iskustvo implementacije

Interes za "olimpijadno programiranje" može se probuditi na različite načine. Najbolji način je proširenje znanja o računalu, računalnim proračunima, uvođenje algoritamskih konstrukcija u nastavu informatike i naknadna integracija s užim rješavanjem problema u određenom programskom jeziku.

Prvi korak. Pripremni. Nastava se izvodi na igriv način. Postupno se uvodi skup naredbi, što omogućuje korištenje računalnih alata za rješavanje problema. U ovom slučaju dovoljan je opis algoritma u bilo kojem programskom jeziku.

Drugi korak. Na početku programiranja i tijekom sljedećih lekcija uvode se različite metode rješavanja problema korištenjem standardnih algoritama implementiranih u programskom jeziku. Uvodi se koncept "debugging programa". Preporučljivo je razmotriti nekoliko rješenja kako bi se studenti na kraju naučili elementima optimalnog pretraživanja.

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

Četvrti korak. Slijedi iz drugog i trećeg, s naknadnim kompliciranjem zadataka i alata za njihovo rješavanje. U ovoj fazi posebno je važno uključiti sveučilišne nastavnike ili sami tražiti složenije zadatke koji pridonose razvoju logičkog, figurativnog mišljenja, razvijaju kombinatorne sposobnosti.

Peti korak. „Kreativna refleksija“. Sastavljanje zadataka od strane učenika s autorskim rješenjem, s testovima, ulaznim i izlaznim zahtjevima.

Najviše postignuće majstorstva: stvaranje i primjena nastavnih tehnologija koje su sami polaznici izmislili kako bi podučavali druge.

Učinkovitost

Metodologija pripreme za programiranje olimpijada može se koristiti za rješavanje problema s kojima se susreću učitelji informatike koji osposobljavaju sudionike olimpijada i učenici koji sudjeluju na olimpijadama. Predložena metoda nije lijek, ali će pomoći ne samo u pripremama za regionalnu olimpijadu, već i za olimpijade više razine.

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 kvalitete komunikacije nemoguće sudjelovati u online natjecanjima u programiranju. Često učenik ne poznaje standard sučelja za predaju zadataka, a da bi se riješio problem i dobio rezultat, potrebno je ponovno ući na stranicu Olimpijade. Provjera i detaljna analiza rezultata zahtijeva dodatno vrijeme. Postavljanje takvog poslužiteljskog sustava u učionici je dosta dugotrajno. A na kućnom računalu učenika trenutno je to gotovo nemoguće. Nisu svi nastavnici informatike upoznati s pravilima za unos i izlaz podataka kroz tekstualnu datoteku pri podnošenju i primanju odluka putem interneta.

Trenutno su razvijene mnoge metode podučavanja informatike. No, unatoč činjenici da se programiranje i algoritmizacija mogu kombinirati u studiju informatike, rješavanje olimpijskih programskih problema zahtijeva potpuno drugačiji pristup.

U radu s učenicima na pripremi za olimpijade, na učvršćivanju vještina, potrebno je više puta rješavati zadatke određene vrste. U tom slučaju nastavnik može dati zadatak učenicima kod kuće u elektroničkom obliku (link na web stranicu, u arhivi), a učenici nakon rješavanja problema donose svoje rješenje na mediju i predaju ga na provjeru. Nakon toga se u grupi analiziraju zadaci, učenici govore načine rješavanja zadataka.

U sljedećim fazama rada zadaci postaju složeniji.

Problem psihičkog i fizičkog preopterećenja

Učenici koji sudjeluju na olimpijadama odlikuju se velikom učinkovitošću, a ponekad učitelji, uvidjevši to, počinju postupno podizati ljestvicu zahtjeva i ocjena. Ali u pripremama za olimpijade bilo koje razine, ne samo u programiranju, učenik mora puno i dodatno raditi kod kuće, na nastavi i izvannastavnim aktivnostima, čak i u početnim fazama. Učenik uči mnoge predmete akademskih predmeta na osnovnoj razini ubrzano samo zahvaljujući marljivosti, velikoj učinkovitosti, uz pomoć nastavnika i roditelja. Zadatak nastavnika i administracije je da tijekom školovanja ne prekoračuju granice iz drugih predmeta. Stoga je potrebna kontrola i podrška ne samo od roditelja, već i od učitelja, 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 najjednostavniji tipovi podataka, veličine tipova. Linearni programi. Uvjetni operatori. Ciklusi. Postupci i funkcije. Složeni tipovi podataka (nizovi, nizovi, zapisi, pokazivači, datoteke).

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

3. Žice. Elementi leksičkih i operacija raščlanjivanja Operacije nad nizovima. Leksemi, brojeći lekseme raznih vrsta. Izdvoj brojeve iz niza.

4. Rad s datotekama Čitanje i pisanje u tekstualnu datoteku. Pretvaranje podataka primljenih iz datoteke u prikladnu strukturu. Rad s upisanim datotekama. Utipkane datoteke. Ulazni međuspremnik.

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 s decimalnim dijelom. Vađenje korijena zadanom preciznošću.

7. Pohranjivanje informacija u dinamičku memoriju. Pohranjivanje skupa podataka u linearne liste. Umetanje na popis, uklanjanje s popisa, traženje stavke na popisu. Dvostruko povezane liste. Koncepti struktura podataka stog, prsten, red, špil; implementirajući ih pomoću dinamičke memorije. Binarna stabla. Stabla s neodređenim brojem potomaka. Pohranjivanje velikih nizova.

Odjeljak 3. Algoritmi, metode i principi rješavanja problema.

1. Koncept složenosti algoritma. Određivanje složenosti.

2. Algoritmi pretraživanja i sortiranja Tražite element u neuređenom nizu. Binarno pretraživanje po ključu u uređenom nizu (dihotomija). Fibonaccijevo pretraživanje. Traži u uređenom n-dimenzionalnom nizu. Potražite k-ti najveći element niza. Jednostavne metode razvrstavanja ("mjehur", "odabir", "umetanje", "broj"). Brze metode ("brzo", "spajanje", "piramidalno"), balansiranje binarnih stabala. Sortiranje metodom scoop.

3. Rješavanje problema nabrajanjem opcija Korištenje rekurzije za nabrajanje. Generiranje kombinacija, položaja, permutacija i skupnih logičkih vrijednosti. Potpuna pretraga. Mogućnosti izrezivanja (heuristika). Metoda grananja i veza.

4. Računska geometrija i numeričke metode Duljina segmenta. Jednadžba ravne linije. Skalarni i križni proizvod. Točka sjecišta odsječaka pravca. Pripadnost točke liku na ravnini (na primjer: trokut). Područje konveksnog poligona. Konveksni trup skupa točaka: Graham, Jarvis, podijeli i vladaj algoritmi. Najbliži par točaka. Gaussova metoda za rješavanje sustava linearnih jednadžbi. Pronalaženje rješenja jednadžbe.

5. Princip dinamičkog programiranja Koncept, primjenjivost. Usporedba s grubom silom.

6. Pohlepni algoritmi Koncept, primjenjivost. Usporedba s grubom silom i dinamičkim programiranjem.

7. Teorija grafova. Algoritmi na grafovima Pojam grafa. Definicije teorije grafova. Strukture podataka za predstavljanje grafa u programu. Algoritmi prelaska grafova (pretraživanja u širinu i u dubinu). Labirint (valna metoda). Eulerov ciklus. Najkraći put u ponderiranom grafu (Dijkstrini i Mintyjevi algoritmi). Tranzitivno zatvaranje grafa (Floyd-Warshill algoritam). Minimalno razapinjuće stablo (Prim i Kruskal algoritmi). Topološko sortiranje grafa. Tokovi u mrežama (Ford-Fulkerson algoritam). Usklađivanje u bipartitnom grafu (metoda lanca produljenja, rješenje za strujanje). Problem zadataka, zadaci usko grlo (mađarski algoritam). Igre s grafovima. Bojanje grafikona. Izgled grafa na ravnini. Snažno povezan i dvostruko povezan graf. Izomorfizam grafa. K-klik. Hamiltonov ciklus.

8. Leksička i sintaktička analiza Zadatak "Kalkulator". Sintaktički dijagrami. Backus-Naur oblici. Model slaganja i rekurzivne analize. Konačni strojevi. Gramatika.

9. Zadaci s "okretima"

Odjeljak 4. Olimpijade iz informatike

1. Pravila vođenja olimpijada iz programiranja

2. Tipične pogreške i otklanjanje pogrešaka programa

3. Tehnike Olimpijade

Po mom mišljenju najveću vrijednost imaju odjeljci 2 i 3. Ako ne biste trebali imati poteškoća s učenjem programskog jezika (postoji ogroman broj knjiga na ovu temu), onda će s algoritmima biti teže. Ima i dosta knjiga na ovu temu, ali one su, najčešće, preopterećene teorijom, a na olimpijadama je potrebna samo praksa. Iz elektroničkih izvora o algoritmima mogu preporučiti knjigu SM Okulova i stranicu algolist.manual.ru, koja je manje usmjerena na proučavanje "olimpijadne informatike" od Okulove knjige, ali sadrži veliki broj algoritama kojih nema u knjizi, ali koje nije bilo loše znati. Naviknite se na rad u načinu rada: pisanje + otklanjanje pogrešaka u Borland Pascal / Borland C ++ i kompilacija (s preliminarnom promjenom konstanti) u Free Pascal / GNU C. Novi 32-bitni prevoditelji nemaju ograničenje tvrde memorije i rade puno brže (razlika je posebno vidljiva u brzini izvršavanja 16 i 32-bitnih programa na P4). Ova zeznuta taktika objašnjava se nedostatkom pristojnog alata za ispravljanje pogrešaka na novim platformama i njihovom gotovo potpunom kompatibilnošću s Borland kompajlerima (u FP-u ne zaboravite zatvoriti izlaznu datoteku).