Preparare gli studenti alle Olimpiadi dell'Informatica. Programma di preparazione individuale per la fase municipale delle Olimpiadi panrusse per gli scolari nella materia "Informatica e TIC" Piano di preparazione per le Olimpiadi dell'informatica

02.07.2020 Windows 8

Analisi dei problemi delle Olimpiadi.

Metodi di preparazione per la fase regionale delle Olimpiadi panrusse per gli scolari di informatica.

Materiali della master class (presentazione)

presso la RMO per docenti di informatica.

docenti di informatica e ICT

Istituzione educativa municipale "Liceo n. 23"

Shuvalova Svetlana Yurievna.

Questo articolo riassume i materiali che ho presentato all'incontro degli insegnanti di informatica russi nel 2011, 2012 sulla base dei risultati delle fasi scolastiche delle Olimpiadi panrusse per gli scolari di informatica.

Il numero di partecipanti alle Olimpiadi di programmazione per gli scolari diminuisce ogni anno, ciò è dovuto a una diminuzione della quota di ore sulla riga di contenuto “Algoritmizzazione e programmazione” nel curriculum del corso di informatica scolastica. Le Olimpiadi sono progettate per identificare gli scolari più dotati nel campo dell'informatica, sviluppare le loro capacità e aumentare l'interesse per l'argomento. Offrono agli scolari l'opportunità di ricevere un orientamento iniziale nella carriera, che contribuisce al futuro sviluppo degli specialisti russi nel campo dell'informatica, della tecnologia informatica e della programmazione. Ma una buona conoscenza del corso di informatica scolastica non garantisce il successo nelle competizioni, è necessario studiare con gli studenti al di fuori dell'orario di lezione.

Diapositiva 1.

L'obiettivo delle Olimpiadi dell'informatica ècontribuire alla ricerca degli studenti più dotati.

Una caratteristica importante dei compiti utilizzati durante le fasi scolastiche e comunali è il loro orientamento a testare lo sviluppo del pensiero teorico, della logica, nonché delle capacità creative e dell’intuizione degli studenti.

I compiti della fase scolastica delle Olimpiadi dovrebbero essere di tale complessità da non spaventare gli studenti, ma dare loro l'opportunità di dimostrare le loro migliori qualità.

Diapositiva 2.

I criteri principali per la selezione dei problemi delle Olimpiadi per le fasi scolastiche e comunali delle Olimpiadi panrusse per scolari in informatica:

formulazione originale del problema (o idea per la sua soluzione);
il testo delle condizioni del compito non deve contenere termini e concetti che vanno oltre le materie studiate nell'ambito del curriculum di base;
il compito deve essere chiaramente definito;
il compito non dovrebbe richiedere conoscenze speciali per essere risolto;
la formulazione del problema dovrebbe implicare la presenza di una fase di formalizzazione al momento della sua risoluzione;
il compito deve essere di ragionevole complessità e intensità di lavoro.

Diapositiva 3.

I compiti olimpici per le fasi scolastiche e municipali delle Olimpiadi dell'informatica si distinguono per la diversità tematica.

Dall'esperienza delle Olimpiadi si possono identificare quelli più comuni:sezioni di informatica,che comprendono i seguenti argomenti:

combinatoria;
ordinamento e ricerca;
elaborazione di sequenze;
algoritmi grafici;
elementi di geometria computazionale.
enumerazione delle opzioni e dei metodi per ridurlo;
programmazione dinamica.

Diapositiva 4.

Fasi di risoluzione dei problemi delle Olimpiadi:

Analisi delle condizioni problematiche.
Formalizzazione delle condizioni problematiche.
Sviluppo di un algoritmo per la risoluzione del problema.
Implementazione software dell'algoritmo.
Debug e test del programma.
Invio della soluzione per la revisione.

Diapositiva 5.

È importante notarloIl testo dell'attività deve essere sempre letto attentamentedall'inizio alla fine, poiché la condizione chiave può essere nascosta, ad esempio, nel formato dei dati di input o di output, nonché nei file di dati di input e output di esempio forniti.

Quando sviluppi un programma, dovresti prestare particolare attenzione anche alla descrizioneformato dei dati di input e outputindicato nella dichiarazione del problema. I nomi dei file di input e di output sono descritti anche nella dichiarazione del problema e scriverli in modo errato nel programma è considerato un errore.

Una cosa da ricordare quando si scrive un programma èsalvataggio dei file modificati durante il giro.

Il programma risultante deve corrispondere a quello indicatodimensioni dei dati di inpute soddisfare le restrizioni sumemoria e tempo di funzionamento, specificato nella dichiarazione del problema.

Diapositiva 6.

Errori comuni:

Il formato di input/output dei dati non corrisponde alle condizioni dell'attività

Non sono stati presi in considerazione tutti i casi possibili

Il tipo di dati (dimensione) non è impostato correttamente

Perdita di file modificati durante un tour

Diapositiva 7.

Conoscenze di base minime per le Olimpiadi dell'Informatica.

Linguaggio di programmazione:

progetti algoritmici di base,
funzioni matematiche standard,
procedure e funzioni per l'elaborazione di variabili stringa,
procedure e funzioni per lavorare con gli array.

Algoritmi tipici.

Diapositiva 8.

I problemi alle Olimpiadi dell’informatica non sempre corrispondono allo “Standard dell’istruzione generale di base e secondaria (completa) in informatica e TIC”. Inoltre, per risolvere questi problemi alle Olimpiadi, è necessario presentare programmi di debug scritti in un linguaggio di programmazione di alto livello e non descrizioni di algoritmi.

Pertanto, non è corretto valutare il lavoro di un particolare insegnante di informatica in base ai risultati delle Olimpiadi, poiché il programma del corso di informatica scolastica non può coprire tutti gli argomenti il cui studio potrebbe migliorare i risultati delle prestazioni degli scolari alle Olimpiadi .

Diapositiva 9.

Risorse Internet per la preparazione alle Olimpiadi dell'informatica:

http://algolist.manual.ru/

Analisi dei compiti della gita scolastica delle Olimpiadi del 2011.

Compito n. 1 “Registrazione di musica” (15 punti)

Controlla se una composizione musicale che dura m minuti en secondi si adatterà al disco del computer, se lo spazio libero su disco è di 6 megabyte e per registrare un secondo di suono sono necessari 16 kilobyte.

Algoritmo di soluzione:

Utilizzando una formula di calcolo e un operatore condizionale

Compito n. 2 "Chiusura a combinazione della cassaforte"(20 punti)

Su 10 lettere devi digitarne 3. Le lettere ripetute sono accettabili. Contare il numero di possibili combinazioni di codici.

Algoritmo di soluzione:

Problema combinatorio. Per risolverlo è necessario applicare un algoritmo standard per formare gruppi di posizionamento con ripetizioni. Vengono utilizzati cicli nidificati.

Compito n.3 "Rettangolo"(30 punti)

Sul piano ci sono N rettangoli. Ogni rettangolo è specificato dalle coordinate dei vertici in basso a sinistra e in alto a destra. Determina se i rettangoli hanno un'area comune

Algoritmo di soluzione:

Se la coordinata massima dell'asse X dei vertici inferiori a sinistra dei rettangoli è inferiore alla coordinata minima dei vertici superiori a destra e la coordinata massima dell'asse Y dei vertici inferiori a sinistra dei rettangoli è inferiore alla coordinata minima dei vertici superiori vertici destri, allora l'area totale è lì.

Viene utilizzato un algoritmo standard per trovare l'elemento massimo (minimo) dell'array.

Compito n. 4 "Piazza Magica"(35 punti)

In un quadrato di 3x3 celle, inserisci i numeri 1, 2, ..., 9 in modo che le somme dei numeri in ciascuna riga, colonna e diagonale siano uguali.

Algoritmo risolutivo.Un problema su come riempire un array bidimensionale.

(metodo indiano):

Nel mezzo della riga superiore mettiamo 1 , nell'ultima riga della colonna adiacente a destra 2 .
I seguenti numeri sono posizionati in direzione diagonale.
Raggiunto il bordo destro del quadrato, si spostano nella cella più a sinistra della linea sovrastante più vicina.
Raggiunto il bordo superiore del quadrato, si spostano nella cella più bassa della colonna adiacente a destra. Nota. Dopo aver raggiunto la cella dell'angolo in alto a destra, si spostano in basso a sinistra.
Dopo aver raggiunto una cella già occupata, si spostano nella cella che si trova direttamente sotto l'ultima cella riempita.
Se l'ultima cella riempita si trova nella riga inferiore del quadrato, passa alla cella più in alto nella stessa colonna.

Analisi dei compiti della visita scolastica delle Olimpiadi del 2012.

Compito 1.

Stampa tutti i numeri decimali a tre cifre le cui cifre si sommano al numero specificato.

Algoritmo di soluzione:

Una delle soluzioni di forza bruta:

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

inizio

scrivi("n="); leggiln(n);

per a:=da 1 a 9 fai

Per b:=da 0 a 9 fai

Per c:=da 0 a 9 fai

Se a+b+c=n allora

inizio

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

k:=k+1;

FINE;

Scrivi;

Writeln("k=",k) ;

Scrivi;

FINE.

Seconda soluzione di forza bruta:

Var a,b,c,n,k,m: intero;

inizio

scrivi("n="); leggiln(n);

per m:=da 100 a 999 do

inizio

c:=m mod 10;

b:= m div 10 mod 10;

a:= m div 100;

se a+b+c=n allora

inizio

scrivi(m:5);

k:=k+1;

FINE;

scriviln("k=",k)

FINE.

Compito 2. "Baby e Carlson."

Il ragazzo e Carlson vivono in una stanza rettangolare delle stesse dimensioni AxB . Come possono calcolare quanti tappeti quadrati hanno un lato CON coprire completamente il pavimento della stanza? (The Kid e Carlson non possono né dividere né moltiplicare.) Scrivi un programma per risolvere questo problema.

Algoritmo di soluzione:

Nel circuito esterno su un lato della stanza (mentre pag ) riserva un posto per una fila ( p:=p+s ), quindi nel circuito interno sull'altro lato (mentre m ) controlliamo quanti tappeti possono essere utilizzati per coprire una fila, operatore m:=m+s riserva un posto per il tappeto e per l'operatore kovrik:=kovrik+1 conta il numero totale di tappetini posati.

var a, b, с, kovrik, m, p: intero;

inizio

leggiln(a, b, c);

kovrik:= 0;

p:= 0;

mentre pag

inizio

p:= p + c;

m:= 0;

mentre m

inizio

m:= m+c;

kovrik:= kovrik + 1

FINE;

writeln (kovrik)

FINE.

Compito 3. “Batteri”.

La colonia era composta da N batteri (non più di 30.000). È entrato in un virus che nel primo minuto ha distrutto un batterio e poi si è diviso in due nuovi virus. Allo stesso tempo, anche ciascuno dei batteri rimanenti si è diviso in due nuovi. Il minuto successivo emersero due virus che distrussero due batteri, quindi tutti i virus e i batteri si separarono di nuovo e così via. Questa colonia vivrà indefinitamente o si estinguerà?

Il tuo programma dovrebbe:

Richiedi la conta dei batteri N ;
Scopri e segnala: dopo quanti giorni, ore e minuti la colonia di batteri cesserà di esistere o darà il messaggio che la colonia è eterna.

Risposta di esempio: per n=A. La risposta è B giorni C ore D minuti (dove A, B, C, D sono valori numerici).

Algoritmo di soluzione:

Programma nel linguaggio di programmazione Pascal.

Var a, b, c: breve;

t, n, v: longint;

inizio

Write('Dimensione iniziale della colonia -"); readln(n);

v:=1;

mentre n>0 lo fa

Inizio

t:= t + 1; (minuti)

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

v:= v*2; (virus)

FINE;

a:= t div 1440;

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

c:= t – a - b;

Scrivere ("La colonia cesserà di esistere tra ",a, "giorni", b, "ore", c, "minuti");

FINE.

Compito 4.

Dato un rettangolo di lati A e B, dove A e B sono numeri naturali. Iniziamo a tagliare i quadrati da esso (Fig. 1). Quanti quadrati di questo tipo possono essere tagliati se ogni volta viene tagliato il quadrato più grande?

Algoritmo di soluzione:

1 modo.

Per risolvere questo problema abbiamo bisogno di funzioni MASSIMO e MINIMO , per definirli utilizziamo subroutine di funzioni.

Inseriamo:

variabili ausiliarie X e Y (Y>=X) , corrispondenti ai lati decrescenti del rettangolo;
variabile ausiliaria D , che determina la riduzione delle dimensioni del rettangolo dopo il successivo taglio del quadrato più grande, il cui lato si trova come X:=MIN(D,X).

Organizziamo un ciclo in cui il lato Y diminuisce ogni volta di MINIMO(D,X) fino a quando rimane l'ultima casella o Y non diventerà più piccolo X. In quest'ultimo caso, rinominare i lati del rettangolo rimanente come Y:=MAX(D,X) e X:=MIN(D,X) e continuare il ciclo.

Programma nel linguaggio di programmazione Pascal.

var a, b, d, k, x, y: intero;

funzione min(i, j: intero): intero;

inizio

se io

altrimenti min:=j

FINE;

funzione max(i, j: intero): intero;

inizio

se io

altrimenti max:=i

FINE;

inizio

ripetere

Writeln("vvedite dva naturalnix chisla");

Readln(a, b);

fino a (a>0) e (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

mentre x y lo fanno

inizio

k:=k+1;

d:=yx;

y:=massimo(d,x);

x:=min(d,x);

FINE;

Writeln ("iskomoe chislo kvadratov:", k)

FINE.

Metodo 2.

Il problema può essere risolto utilizzando le funzioni standard PASCAL: Y DIV X e Y MOD X, utilizzando l'algoritmo euclideo.

Algoritmo di soluzione:

Organizziamo un ciclo in cui formiamo i resti della divisione r 0 , r 1 , r 2 ,..., r n , r n+1 finché uno di questi resti diventa zero rn+i =0 . Pertanto, costruiamo una funzione per generare il resto della divisione r n+i = r n mod r n-i, dove r 0 = A e r i = B . Per lo stesso sistema di residui, possiamo contare quante volte il resto combacia r n-i a r n .

(Algoritmo euclideo)

var A, B, R0, R, R1, K: intero;

inizio

ripetere

Write("INSERISCI IL NUMERO NATURALE A = ");

Leggi(A);

Write("INSERISCI UN NUMERO NATURALE IN

Leggi(B);

fino a (B > 0) e (A > 0) e (A >=B);

R0:=A;

R1:=V;

K:= R0 div R1;

mentre R0 mod R1 0 lo fanno

inizio

R:= R0 mod R1;

R0:= R1;

R1:=R;

K:= K + R0 div R1

FINE;

Writeln("CERCA NUMERO DEL QUADRATO K = ",K);

Articolo del docente del JIVT Lyceum No. 8 Pangina N.N. dalla rivista “Computer Tools in Education”, N1, 2000

Preparare gli studenti alle Olimpiadi dell'informatica.

Le Olimpiadi dell’informatica sono essenzialmente Olimpiadi della programmazione. Risolvere i problemi delle Olimpiadi è una sezione educativa completamente indipendente con ampie parti teoriche e pratiche.

Da sei anni, presso il liceo scolastico n. 8 di Sosnovy Bor, gli scolari si preparano per le Olimpiadi di vari livelli. Per cinque anni, gli studenti del liceo sono stati vincitori delle Olimpiadi di programmazione regionale, partecipanti e vincitori delle Olimpiadi panrusse.

Le soluzioni ai problemi delle Olimpiadi in quasi tutte le fasi delle Olimpiadi, dal livello regionale a quello internazionale, si basano su algoritmi ben definiti, ampiamente conosciuti in matematica e informatica. E per risolvere con successo i problemi delle Olimpiadi, devi prima di tutto padroneggiare questi algoritmi, vederli e applicarli abilmente nei compiti proposti e, se non lo sai, essere in grado di inventarli, inventarli. Ma la conoscenza di questi algoritmi avviene molto spesso solo in un'università, e questo è abbastanza comprensibile, poiché la padronanza di questi algoritmi richiede la conoscenza di alcuni rami della matematica superiore.

Domanda 1. Quindi è possibile preparare gli scolari per le Olimpiadi?

È possibile, ma non nell'ambito del programma di base.

Inoltre, è quasi una condizione necessaria che questi studenti studino matematica aggiuntiva (è meglio se si tratta di lezioni con uno studio approfondito della matematica). Non è un caso che i nostri eccezionali scolari russi nel campo dell'informatica abbiano avuto altrettanto successo in matematica:

Viktor Bargachev, 2 volte campione del mondo assoluto di informatica tra gli scolari, è il vincitore delle Olimpiadi internazionali di matematica (medaglia d'argento);

Nikolay Durov, 4 volte vincitore delle Olimpiadi Internazionali di Informatica (3 medaglie d'argento e una d'oro), è il proprietario di due medaglie d'oro delle Olimpiadi Internazionali di Matematica;

Vladimir Martyanov di Nizhny Novgorod (2 volte campione del mondo assoluto di informatica) è stato il vincitore delle Olimpiadi zonali russe di matematica e fisica.

Nella regione di Leningrado si possono citare esempi di Alexey Stratonnikov, Alexey Potapov, Artem Ananyev, Andrey Pangin.

Domanda 2 . A che età dovresti iniziare a preparare gli scolari?

Prima è, meglio è, ma entro limiti ragionevoli.

Per livello

È sufficiente iniziare le Olimpiadi regionali dal 7° all’8° grado;

Si consiglia di iniziare le Olimpiadi russe nelle classi 5–6.

Esempio: il campione di Mosca nella programmazione tra gli scolari nel 1998, Petr Mitrichev, è uno studente di 7a elementare, è stato anche il partecipante più giovane alla 9a Olimpiade tutta russa per scolari di informatica e un partecipante ai campi di addestramento per preparare i russi squadra per le Olimpiadi Internazionali.

Domanda 3 . In quale forma dovrebbero essere condotte le lezioni per prepararsi alle Olimpiadi?

Sotto forma di corsi opzionali o speciali.

Per la buona preparazione di uno studente, per usare una frase nota, è importante innanzitutto “non solo riempire la coppa della conoscenza, ma anche accendere la fiaccola”. In altre parole: instilla interesse!

Secondo l'esperienza del nostro liceo, a ciò contribuiscono:

Le connessioni interdisciplinari svolgono un ruolo importante.

Da cinque anni il Liceo organizza il corso speciale “Matematica sui computer” per le classi 5–6. Gli studenti vengono introdotti ai concetti matematici in forma visiva (ad esempio, un cubo animato, un piano di coordinate con una griglia di numeri interi) e imparano ad avvicinarsi in modo creativo alla risoluzione di problemi standard (ad esempio, utilizzando rappresentazioni grafiche di problemi di colata e pesatura su un computer ).

Lo sviluppo dell'interesse è facilitato dalle lezioni sull'argomento "Modellazione del movimento" dal movimento più semplice di una palla da biliardo al quadro complesso delle linee di intensità del campo elettrico di due cariche. Particolarmente impressionante è la simulazione al computer del “volo di un aeroplano di carta” e la dimostrazione di questo volo nella realtà. Interessante è anche il compito di modellare il movimento di un satellite e determinare la prima, la seconda velocità di fuga e il tempo di volo del razzo Vostok con Yuri Gagarin attorno alla Terra (tutti dovrebbero conoscere questo evento!).

Tali lezioni si svolgono differenziate a seconda del livello di preparazione degli studenti.

Per le classi 7–8, durante le prime due o tre settimane delle vacanze estive, viene organizzato il campo scolastico “Intelligence”, dove i bambini studiano informatica secondo un programma speciale.

Ad esempio, il programma Labyrinth include i seguenti argomenti:

costruzione di un labirinto (un interessante algoritmo per generare un labirinto casuale di varia complessità);

muoversi nel labirinto utilizzando i tasti di controllo;

trovare una via d'uscita dal labirinto, iniziando da quella più semplice secondo la regola della mano sinistra (restare su un lato del labirinto);

trovare la strada più breve in un labirinto.

Questo programma incoraggia gli studenti a sviluppare i propri giochi di camminata e tiro. La cosa principale è rendersi conto che loro stessi possono crearlo!

Per 10 gradi, la formazione pratica estiva viene organizzata presso varie imprese di Sosnovy Bor per un mese. Gli studenti acquisiscono competenze nella risoluzione di problemi pratici, consolidano la conoscenza del lavoro con database, applicazioni di ufficio contabile, creano autonomamente programmi secondo le istruzioni dei curatori e acquisiscono ulteriori conoscenze (ad esempio, quando si lavora con reti di computer, il sistema operativo Unix). Una lodevole recensione da parte di un'impresa è un risultato comune di tale lavoro.

I ragazzi dimostrano i propri programmi alla tradizionale conferenza scolastica di informatica “Noi e il computer”, che quest'anno è stata la sesta. I ragazzi presentano ogni anno i migliori sviluppi software alla Conferenza internazionale “Informatica scolastica e problemi di sviluppo sostenibile”, tenutasi a San Pietroburgo, dove il lavoro dei bambini viene valutato con diplomi di 1° e 2° grado.

Alcuni programmi vengono utilizzati come materiale didattico.

Per un gruppo di "appassionati di computer" in senso buono, e non nel senso, ad esempio, di giochi per computer, vengono condotti corsi opzionali e speciali appositamente mirati su argomenti: apprendimento di un linguaggio di programmazione aggiuntivo, algoritmizzazione di problemi non standard, problemi delle Olimpiadi, teoria dei grafi, ecc.

Domanda 4 . Quante persone dovrebbero partecipare agli elettivi appositamente orientati?

Gruppi da 6 – 12 persone.

Quando si lavora per un risultato specifico (ovvero la preparazione per le Olimpiadi cittadine, regionali o russe), dovrebbe esserci un gruppo da 3 a 6 persone. Queste classi sono già in fase di formazione e qui l'insegnante agisce più come allenatore che come insegnante. Come sta andando la lezione?

L'argomento si chiama.

Vengono elencate le attività su questo argomento.

Viene selezionata una delle attività più popolari o interessanti.

L'algoritmo risolutivo viene discusso oralmente con i bambini.

I ragazzi scrivono un programma, l'insegnante registra il tempo, valuta l'implementazione delle soluzioni, aiuta a trovare errori e sottolinea le carenze di efficienza (numero di operazioni, utilizzo della RAM, tempo di soluzione).

Domanda 5 . Quali argomenti dovrebbero essere studiati nelle lezioni per prepararsi alle Olimpiadi?

È impossibile fornire tutto, ma si possono distinguere i seguenti gruppi di algoritmi:

Algoritmi su numeri interi.

Ricorsione.

Ordinamento.

Problemi di ricerca.

Problemi geometrici.

Metodi numerici.

Modellazione statistica.

Grafici e alberi.

Trasformazioni del testo.

Consideriamo più in dettaglio gli argomenti necessari per studiare in preparazione alle Olimpiadi. Le lezioni teoriche dovrebbero includere definizioni e affermazioni (in alcuni casi, necessariamente con prove).

Algoritmi su numeri interi

Divisibilità

Quando si studia questo argomento, è necessario fornire le definizioni di divisore, numeri multipli, primi e coprimi, fornire affermazioni con prove sulla divisibilità della somma e della differenza di due numeri, sulla divisibilità di un prodotto.

Prima modifica dell'algoritmo euclideo (con sottrazione)

Diminuendo successivamente i numeri (sostituendo a quelli più grandi la differenza di numeri) fino a renderli uguali, arriviamo al massimo comun divisore di questi numeri.

Compiti che devono essere affrontati quando si studia questo argomento:

Determina se più numeri sono coprimi

Ridurre una frazione (vengono inseriti il numeratore e il denominatore della frazione)

Scrivere un programma di calcolatrice in frazioni semplici

La seconda modifica dell'algoritmo euclideo, utilizzando la divisione con resto

Dove R – resto quando si divide un numero maggiore per un numero minore.

Pertanto, riducendo i numeri, otteniamo il massimo comun divisore come ultimo resto diverso da zero.

Problema da risolvere: un rettangolo con lati aeb, dove aeb sono numeri naturali, tagliato in quadrati di area massima. Determina la dimensione dei quadrati e il loro numero totale.

Equazioni diofantee

Usando l'affermazione sulla rappresentazione del massimo comun divisore di due numeri come combinazione lineare di questi numeri, arriviamo all'affermazione sulla risolubilità in numeri interi di un'equazione della forma ascia + by = c(Equazione diofantea).

Compiti che devono essere considerati quando si studia questo argomento:

Problemi relativi allo scambio di denaro con monete di un determinato valore.

Compiti trasfusionali.

Quando si studia l'algoritmo per risolvere il problema della trasfusione, sembra utile utilizzare il programma dimostrativo e di formazione ausiliario “Perlivayka”, con l'aiuto del quale gli studenti possono applicare nella pratica l'algoritmo studiato. È necessario correggere questo algoritmo per trovare almeno una soluzione all'equazione diofantea. Quindi viene fornito un algoritmo generale per risolvere l'equazione diofantea con formule per trovare l'intero insieme di soluzioni.

numeri primi

Esistono molti problemi delle Olimpiadi di diversi livelli associati ai numeri primi. Il metodo classico per trovare i numeri primi è il crivello di Eratostene. A questo algoritmo sono associate le seguenti soluzioni: compiti:

Numeri gemelli;

Numeri perfetti;

Tovaglia Ulama;

Numeri amichevoli, ecc.

Aritmetica "lunga".

I problemi che coinvolgono l'aritmetica "lunga" sorgono quando non è possibile memorizzare il risultato in tipi di dati standard (interi o interi lunghi), poiché è così grande. In questo caso, viene utilizzata la tecnica di memorizzazione di numeri lunghi sotto forma di una matrice di cifre e per eseguire operazioni aritmetiche con tali numeri è necessario scrivere procedure speciali per aggiungere, moltiplicare e dividere numeri lunghi.

Problemi tipici: trova il numero N! (N-fattoriale), determinare il periodo della frazione.

Ricorsione

Quasi tutti i libri sulla programmazione toccano la ricorsione e le procedure e le funzioni ricorsive. Ma sono pochissimi i libri in cui il tema della ricorsione viene trattato in dettaglio. Tradizionalmente, la considerazione di una funzione ricorsiva inizia con la ricerca del fattoriale di un numero. Una breve funzione in una riga, ma non è chiaro il motivo per cui il fattoriale dovrebbe essere calcolato in modo ricorsivo se è già calcolato semplicemente in un ciclo con un parametro.

Più gli studenti sono giovani, più importanti sono per loro i principi di chiarezza e semplicità. Un'introduzione alla ricorsione può iniziare con la famosa filastrocca sui “10 piccoli indiani”.

La fase successiva sono i disegni ricorsivi. Iniziamo con i disegni più semplici, ad esempio disegnando una "bambola matrioska" semplificata.

fiocchi di neve che cadono su tutto lo schermo;

rami di diversi colori, diversa morbidezza e dimensioni diverse (una componente casuale viene aggiunta alla lunghezza del ramo).

I set frattali sono di grande interesse per i bambini: il tovagliolo e la tovaglia di Sierpinski, il modello del polmone umano di Mandelbrot, il frattale di Harter-Haithway (noto a noi come la linea spezzata del drago), le curve di Hilbert, il fiocco di neve di Koch. La ricorsione qui è così naturale che nessuno si chiede se sia possibile farne a meno. E solo ora, quando il fascino e la bellezza della ricorsione non lasciano dubbi, possiamo passare a compiti che, per loro definizione, sono ricorsivi. Questi sono i seguenti problemi: fattoriale di un numero, N-esima potenza di un numero, mcd( UN, B), funzione di Ackermann, numeri di Fibonacci, conversione dei numeri dal 10° sistema di numerazione al 2°, ricerca del massimo e del minimo in un array. Si scopre che molte attività possono essere eseguite utilizzando la ricorsione. La cosa principale è che una visione della ricorsione appare in problemi precedentemente risolti in modo non ricorsivo. A scopo di novità, ad esempio, nel problema di tagliare un rettangolo in quadrati di area massima, si propone di realizzare un supporto grafico visivo utilizzando la ricorsione. Ed è assolutamente “cattivo” senza ricorsione quando si risolvono problemi come la “Torre di Hanoi”. In questo caso, il programma dimostrativo e di formazione “Torre di Hanoi” aiuta a realizzarlo e a padroneggiare praticamente l'algoritmo ricorsivo per risolvere questo problema.

Ordinamento

Senza la conoscenza degli algoritmi di ordinamento, non è possibile sentirsi a proprio agio alle Olimpiadi di vari livelli. I problemi possono essere formulati esplicitamente con un riferimento all'algoritmo di ordinamento, oppure implicando l'uso di un algoritmo di ordinamento all'interno della soluzione. I due algoritmi più semplici che devi conoscere sono il bubble sort e l'exchange sort (cercando minimi successivi). Per piccole quantità di dati questi due metodi sono abbastanza sufficienti, ma quando si lavora con dati misurati in decine e centinaia di kilobyte è necessaria la conoscenza di uno degli ordinamenti rapidi. Si può dare preferenza all'ordinamento rapido Hoare, che viene implementato in modo ricorsivo. È inoltre necessario conoscere alcuni trucchi quando si organizzano i dati in file di grandi dimensioni. L'intero file è diviso in una serie di pezzi, che possono essere ordinati utilizzando QSORT, quindi i file ordinati possono essere uniti senza un programma di ordinamento (a proposito, questo è un compito molto utile da un punto di vista tecnico, che richiede precisione e buone tecniche di programmazione).

Enumerazione delle opzioni

I problemi di enumerazione costituiscono una vasta classe di problemi delle Olimpiadi. La ricerca inizia con una semplice ricerca del minimo e del massimo in un array unidimensionale o con la ricerca di un elemento con le proprietà specificate. Poi viene la ricerca di coppie di elementi utilizzando un ciclo annidato, quindi la ricerca di triplette di elementi utilizzando un ciclo triplo (come, ad esempio, nel problema di trovare tre punti su un piano tra i dati N punti che formano un triangolo con l'area massima). E se esegui combinazioni di 4, 5, 6, ecc. elementi? Quanti cicli sono necessari? Si scopre che esistono algoritmi che riducono significativamente la ricerca.

Abbastanza lungo nel tempo di esecuzione, ma uno degli algoritmi di forza bruta più universali è la forza bruta con ritorno o “backtracking”. Programmato in modo ricorsivo. Meglio spiegato utilizzando i seguenti problemi:

Muovi il cavallo sulla scacchiera N*M;

Posiziona 8 regine su una scacchiera di dimensione 8*8 in modo che non si minaccino a vicenda;

Trovare una via d'uscita dal labirinto, ecc.

È inoltre necessario spiegare agli studenti che se il programma impiega troppo tempo per essere completato, è necessario limitare i backtracking. Ad esempio, in un problema sugli scacchi, con una dimensione della scacchiera di 8*8, il programma è in esecuzione da molto tempo. Puoi e devi anche usare la simmetria e l'immagine speculare quando esegui un'attività per metà o un quarto della scacchiera.

Il classico problema del “backtracking” è il problema dello “zaino”, quindi possiamo considerare i derivati di questo problema:

Dividi N numeri in due sottoinsiemi che sono più vicini in somma;

Da un dato insieme di parole, seleziona la sottosequenza massima di parole nell'ordine del dizionario.

Anche i problemi combinatori sono associati all'enumerazione. È necessario padroneggiare gli algoritmi per creare un ordinamento lessicografico.

Problemi di geometria

Il minimo richiesto che devi sapere quando risolvi i problemi di geometria include quanto segue:

Essere in grado di ridurre alla forma l'equazione di una retta passante per due punti

Ascia + Per + C = 0;

Essere in grado di determinare se un punto appartiene ad una linea o ad un segmento;

Essere in grado di determinare se due rette si intersecano e, se si intersecano, determinare il loro punto di intersezione (per fare ciò, calcolare il determinante del 2° ordine);

Essere in grado di scrivere l'equazione di una retta perpendicolare o determinare se una retta è perpendicolare ad un'altra (utilizzando la proprietà che il prodotto scalare di vettori perpendicolari è uguale a zero);

Essere in grado di calcolare la distanza da un punto ad una linea.

Oltre a questo, per risolvere problemi a livello regionale e panrusso, è richiesta la conoscenza di un corso iniziale di geometria analitica: il prodotto scalare e incrociato dei vettori, la loro espressione attraverso le coordinate. Il prodotto scalare viene utilizzato per trovare l'angolo (o il coseno di un angolo) quando si costruisce, ad esempio, l'inviluppo convesso di determinati punti. Il prodotto vettoriale di due vettori viene utilizzato, in primo luogo, per calcolare le aree dei poligoni e, in secondo luogo, per determinare la direzione nei problemi correlati. Questa conoscenza è necessaria anche per risolvere un classico problema delle Olimpiadi, come se un punto sia contenuto all'interno di un poligono arbitrario.

È necessario attirare l'attenzione degli studenti sull'ambiguità dei concetti che possono essere utilizzati in vari compiti. Ad esempio, per il concetto di prodotto vettoriale

il modulo del valore numerico determina l'area del parallelogramma costruito su determinati vettori;

valore zero - parallelismo dei vettori;

il segno significa che un vettore si trova “a sinistra” o “a destra” rispetto all'altro;

il vettore risultante definisce la normale al piano dei vettori dati.

Metodi numerici

Metodo della dicotomia

Per cercare i dati in un insieme ordinato, viene utilizzato il metodo della dicotomia (o dimezzamento), seguito dal controllo delle proprietà desiderate. Questo metodo, più comune per trovare valori approssimativi delle radici di equazioni non lineari, può essere utilizzato per cercare attraverso “enormi” quantità di dati. In questo caso utilizzeremo il termine “ricerca binaria”. Un compito tipico è trovare una determinata parola in un dizionario.

In generale, questo metodo è ottimale.

Risoluzione di sistemi di equazioni lineari: metodo di Cramer, metodo di Gauss.

Metodi classici. Di solito il numero di equazioni nei problemi non è superiore a tre. Ma la conoscenza del caso generale probabilmente tornerà utile.

Problema dalle Olimpiadi regionali del 1994.

L'equazione di una reazione chimica viene inserita sotto forma di una linea: è necessario equalizzare, cioè impostare i coefficienti.

Modellazione statistica (metodo Monte Carlo).

La conoscenza di questo metodo è molto utile:

per modellare situazioni di gioco probabilistiche (lanciare una moneta, un dado, camminare). È la formulazione “giocasca” o legata a qualcosa di familiare (conosciuto, “quotidiano”) del problema che aiuta a comprendere il metodo, il concetto di probabilità. Puoi offrire agli studenti compiti interessanti:

Cosa c'è di più: frazioni riducibili o irriducibili? (Formulazione matematica: stimare la probabilità che una frazione scelta a caso sia irriducibile);

la soluzione migliore per i sempliciotti (“Quantum” n. 5, 1987);

problemi combinatori.

Determinare le aree delle figure quando le soluzioni analitiche sono difficili.

Pertanto, nel problema (Olimpiadi regionali '99) di trovare l'area di intersezione di tre cerchi, il metodo Monte Carlo può essere utilizzato come alternativa al metodo analitico diretto, poiché è molto difficile ricavare una soluzione utilizzando la trigonometria relazioni. Il modo migliore è “usare la geometria” per analizzare casi speciali (quando non c’è intersezione, quando l’intersezione è in un punto, un cerchio dentro un altro) e il metodo Monte Carlo per il caso generale.

Programmazione dinamica.

Ci sono momenti in cui è impossibile risolvere il problema con una ricerca completa di opzioni a causa del loro numero enorme. Ma se ad ogni passo il problema può essere diviso in problemi più semplici e la soluzione ottimale può essere trovata senza considerare tutte le soluzioni al problema generale, e poi le soluzioni trovate possono essere applicate ai passi successivi, allora ciò significa che il In questo caso si applica il principio della programmazione dinamica.

Questo principio è più facilmente comprensibile in compiti specifici. Ma la sua spiegazione può iniziare con una storia divertente sulla scala d'oro del Faraone (pubblicata nella rivista "Kvant" n. 10, 1991), per poi passare ai seguenti compiti:

Il problema classico di trovare il percorso più breve in una matrice numerica A di dimensione NxN da A(1,1) a A(n,n), in cui la somma delle cifre nelle celle era minima o massima.

Trovare una sottostringa comune di lunghezza massima (un problema sorto da un moderno problema di vita reale in biologia molecolare sull'informazione genetica comune nelle molecole di DNA).

Grafici e alberi.

Un argomento molto importante. Quasi nessuna Olimpiade a livello russo è completa senza l'uso di una sorta di algoritmo grafico. È necessario introdurre il concetto di grafo attraverso vertici e spigoli, il concetto di grafo orientato o non orientato e analizzare i metodi per rappresentare i grafi sotto forma di matrice, adiacenza, matrice di incidenza e lista di connessioni.

Analizzare i principali algoritmi su grafici:

ricerca approfondita (in altre parole, “backtracking” o ricerca a forza bruta);

ricerca in ampiezza (o metodo di riempimento);

Algoritmo di Dijkstra per trovare i percorsi più brevi in un grafico da un dato vertice a tutti gli altri;

Algoritmo di Floyd per trovare i percorsi più brevi in un grafico tra tutte le coppie di vertici.

Trasformazioni del testo

Le attività in cui è necessario analizzare una stringa a volte implicano anche il lavoro con file, costruzioni grafiche (simili ai comandi di un editor di testo o grafica) o l'uso di alcune tecniche di programmazione (ad esempio, rappresentare uno "stack" come un carattere string nel problema dell'espressione parentetica corretta per diversi tipi di parentesi).

Viene presentata una serie ampia, ma lungi dall'essere completa, di argomenti trattati dai compiti delle Olimpiadi. Ciò dipende in gran parte dalle preferenze degli organizzatori delle Olimpiadi a vari livelli (turni teorici, compiti che utilizzano strategie di gioco, natura applicata "d'ufficio").

Domanda 6 . Che consigli puoi dare quando risolvi i problemi alle Olimpiadi?

Supponendo che la teoria degli algoritmi sia stata “studiata” e che le basi della programmazione siano state padroneggiate, si può consigliare al partecipante al concorso di fare quanto segue:

Fornisci in riserva una certa serie di punti "garantiti" (secondo te) su compiti semplici. Ciò non significa lasciare i compiti difficili fino all'ultimo minuto. Riflettendo sulla soluzione si può trovare un algoritmo “buono” e una percentuale di punti corrispondentemente più alta sarà considerata un successo.

Se il problema è difficile per te o non hai abbastanza tempo per risolverlo, programma semplici casi speciali ( Forse alcuni test verranno superati) o utilizzare un algoritmo non ottimale, ad esempio un algoritmo di forza bruta.

Se un problema ha un limite di tempo per risolverlo e il tuo algoritmo di ricerca esaustiva non rientra in questo tempo, inserisci un timer nell'algoritmo che, quando si avvicina al momento critico, termina il problema e visualizza la migliore opzione di ricerca esaustiva trovata (potrebbe essere corretto).

La scelta del linguaggio algoritmico è importante, ad esempio in un programma Basic è più semplice lavorare con la grafica, mentre in un programma Pascal ha il vantaggio della velocità.

Segui rigorosamente i formati di input/output specificati nella dichiarazione dell'attività: l'"autotester" potrebbe fraintendere lo spazio extra o i test di origine contengono una virgola in cui hai fornito uno spazio nell'input dell'attività (caratteristiche degli operatori di input Pascal e Basic) .

Fondamentalmente, qualsiasi programma ha la struttura:

Inserimento dati

Blocco di calcolo

Uscita del risultato

Progettare e garantire che l'input/output sia corretto (con possibile analisi di dati errati) prima di programmare il blocco di calcolo.

Imposta le opzioni del compilatore per gestire tutti i tipi di errori (utili per il debug) e prima di inviare l'attività, disabilita queste opzioni (per consentire al compilatore di ignorare possibili errori di test che non influiscono sulla soluzione).

Testare il problema per i vincoli massimi dati (ad esempio, se dato n  1000, testare per n = 1000). Tieni d'occhio il tipo di variabili che dichiari (è preferibile utilizzare il tipo “long integer” per dichiarare variabili intere).

Usa l'appello con saggezza. Potrebbe esserci ambiguità nella comprensione del compito. Anche la giuria è composta da persone e puoi difendere la tua posizione e convincerli ad aggiungerti i punti desiderati.

Come ultima risorsa, se sei un "cool hacker" (uno specialista di sistemi cool), esegui il programma del "vicino" come se fosse il tuo (nessuno se ne accorgerà).

Puoi avere i tuoi foglietti illustrativi (non in formato elettronico) o approfittare del tempo "libero" per studiare la letteratura di riferimento.

Alcuni dei suggerimenti elencati sono “dannosi” e corrispondono al principio “forse, forse, in qualche modo”. Per favore, prendeteli in modo critico, ma sono vitali.

Domanda 7 . Quale letteratura dovresti usare quando ti prepari per le Olimpiadi?

Questo articolo e le seguenti fonti.

A. Shen. Programmazione: teoremi e problemi, M. MTsNMO, 1995.

AL Brudno, LI Kaplan. Olimpiadi di Mosca nella programmazione, M: scienza, 1990.

V.A.Dagene, G.K.Grigas. 100 problemi di programmazione, M: Prosveshchenie, 1993.

V.M. Bondarev, V.I. Rublinetsky, E.G. Kachko. Fondamenti di programmazione, Kharkov: Folio, 1997.

V.M.Kiryukhin, A.V.Lapunov, S.M.Okulov. Problemi in informatica. Olimpiadi Internazionali. M: ABF, 1996.

N.M. Badin, S.G. Volchenkov, NL Dashnits. Olimpiadi di Yaroslavl dell'informatica. Yaroslavl, 1995.

S.M.Okulov. Appunti per le lezioni di informatica (algoritmi grafici). Kirov, 1996.

A.V. Alekseev. Olimpiadi per gli scolari di informatica. Casa editrice di libri Krasnoyarsk, 1995.

A.S. Sipin, A.I. Dunaev. Olimpiadi regionali di informatica. Vologda, 1994.

V. Pinaev. Olimpiadi cittadine nella programmazione. Rybinsk, 1998.

SA Abramov. Costruzioni matematiche e programmazione. 1987.

Domanda 1. Come imparare a risolvere i problemi delle Olimpiadi in informatica?

Per imparare a risolvere i problemi delle Olimpiadi in informatica, è necessario risolvere problemi in informatica... Naturalmente, guardando la letteratura pertinente.

Domanda 2. Quanti problemi devi risolvere per ottenere buoni risultati alle Olimpiadi dell'informatica?

La domanda, ovviamente, non è stata posta correttamente e forse è difficilmente possibile rispondere, ma vale la pena spendere qualche parola al riguardo. Come mi ha detto Mikhail Medvedev, uno specialista nel campo della preparazione per le Olimpiadi ACM, creare un problema olimpico fondamentalmente nuovo non è così semplice come potrebbe sembrare a prima vista. Per questo motivo i responsabili delle Olimpiadi si limitano a prendere i problemi degli anni precedenti e a presentarli con una “nuova salsa”. Accade spesso che i problemi delle Olimpiadi regionali e zonali dell'informatica vengano “derubati” senza alcuna modifica dai siti dedicati alla programmazione delle Olimpiadi.

Quindi, poiché molti problemi sono molto, molto simili, è necessario imparare a risolvere problemi dell'intera gamma: ordinamento, programmazione dinamica, aritmetica lunga, ecc.

Domanda 3. È possibile preparare gli scolari alle Olimpiadi di informatica come parte del curriculum scolastico?

Penso che questo non sia realistico. Tutti sanno da tempo che un corso di informatica scolastica è una cosa, ma le Olimpiadi dell'informatica sono qualcosa di completamente diverso. Sì, nel programma approssimativo di informatica del 9 ° grado, un numero abbastanza elevato di ore è dedicato allo studio della programmazione. Nel libro di testo di Semakin per la nona elementare, l'istruzione di programmazione si basa sul linguaggio Pascal, mentre Ugrinovich fornisce esempi in relazione a Visual Basic. Ma, anche se applichiamo un approccio differenziato all’insegnamento agli scolari, è improbabile che queste ore siano sufficienti per preparare da zero i singoli scolari alle Olimpiadi.

Domanda 4. Se le ore del programma non sono sufficienti per preparare gli scolari alle Olimpiadi, come dovrebbero prepararsi?

Nelle prime due opzioni tutto è chiaro, ma ci deve essere comprensione da parte della direzione scolastica. Spesso c'è una "battaglia per l'orologio" tra gli insegnanti e potrebbe non esserci abbastanza spazio per una lezione o un corso facoltativo sulla programmazione dell'orologio.

L'entusiasmo personale portato all'estremo è secondo me un fenomeno molto dannoso. L’educazione russa non dovrebbe basarsi sull’entusiasmo. Altrimenti si scopre che finché c’è entusiasmo le cose vanno bene, la miccia si scarica e tutto crolla. Non durerai a lungo con l'entusiasmo, ma a volte vale la pena dimostrarlo nella speranza che le cose decolleranno.

Domanda 5. Ho 25 (26, 30...) ore di carico di lavoro principale, è ancora possibile coinvolgere gli studenti in un gruppo di programmazione?

Mi sembra che con un tale carico di lavoro sia più realistico impazzire che preparare gli studenti per le Olimpiadi. Sono sinceramente solidale con tutti gli insegnanti con un carico di lavoro pesante. Capisco che assumere tante ore non sia una bella vita, ma non capisco come si possa lavorare in tali condizioni.

Domanda 6. Gli scolari possono prepararsi per le Olimpiadi al di fuori dell'orario scolastico e, in tal caso, come organizzare al meglio la preparazione?

Possono, ma come minimo devono avere un computer di casa. Idealmente dovrebbe esserci anche Internet. Se disponi di un PC e di Internet, puoi risolvere i problemi su uno dei siti specializzati con verifica automatizzata delle soluzioni, ad esempio sul sito web della Programmer School.

Domanda 7. Cosa è richiesto a un insegnante per preparare adeguatamente gli scolari alle Olimpiadi?

Capacità di apprendimento. Dopotutto, si dà il caso che una persona si sia laureata in un istituto scolastico ed è qui che a volte finisce il suo sviluppo in termini di ottenimento di informazioni. Sembra essere sufficiente per il lavoro scolastico, quindi perché preoccuparsi ancora...
Rimani sempre in contatto. Il tuo studente potrebbe avere una domanda in qualsiasi momento; dopo tutto, c'è chi risolve i problemi di notte. Se non riesci a dormire, perché no, se possibile, rispondigli utilizzando lo stesso ICQ o Skype.

Metodi di preparazione alle Olimpiadi dell'informatica

Pertinenza dell'argomento

In connessione con l'aggiornamento e l'intensificazione del movimento delle Olimpiadi, il problema della preparazione degli studenti a partecipare alle Olimpiadi sta diventando sempre più acuto. La preparazione di uno “studente olimpico” inizia con la preparazione di un insegnante.

Problemi che deve affrontare l'insegnante:

1. Studio di nuove forme di svolgimento delle Olimpiadi.

2. Conoscenza degli algoritmi per la risoluzione dei problemi delle Olimpiadi.

3. La presenza dei compiti stessi.

4. Conoscenza dei linguaggi di programmazione.

5. Tempo per studiare, eseguire il debug e verificare le attività.

6. Insegnare agli studenti come organizzare correttamente le attività alle Olimpiadi.

Nonostante il fatto che la gamma di problemi considerati alle Olimpiadi di programmazione sia limitata, risolvere il problema può essere difficile non solo per lo studente, ma anche per l'insegnante, poiché alcuni problemi richiedono la conoscenza della matematica superiore. La verifica delle soluzioni e la preparazione dei test richiedono solitamente molto tempo.

Eccotene alcune Caratteristiche della preparazione degli scolari alla programmazione delle Olimpiadi :

· Non esiste una materia di “programmazione” e nemmeno una sezione del genere nel curriculum scolastico. Cioè, lo studente deve avere una propria motivazione abbastanza forte.

· Esiste una limitazione secondo cui durante la risoluzione dei problemi è consigliabile utilizzare solo uno dei linguaggi di programmazione (SI o PASCAL).

· L'allenamento costante è quasi a livello sportivo.

· Grandi quantità di tempo, la durata delle Olimpiadi con analisi supera spesso le 6 ore.

· Gli algoritmi e le formule utilizzate per risolvere la maggior parte dei problemi vengono studiati solo nelle università.

Ovviamente Anche per gli insegnanti è necessaria una formazione di livello superiore per lavorare con studenti dotati che partecipano a concorsi di programmazione:

· Possibile istruzione secondaria, università specializzata in programmazione.

· IPK degli insegnanti, corsi sull'apprendimento dei linguaggi di programmazione, sulla programmazione delle Olimpiadi.

· Auto-preparazione utilizzando materiali provenienti da fonti aggiuntive.

Ma anche una buona conoscenza del linguaggio di programmazione non fornisce una garanzia al 100% che uno studente vincerà anche alle Olimpiadi scolastiche o distrettuali.

Idea pedagogica

Il principale incentivo per uno studente a partecipare alle Olimpiadi è la motivazione. Questa non è solo un'opportunità per migliorare il proprio voto, ma anche un'opportunità per dimostrare conoscenza ed erudizione sul problema da risolvere, capacità organizzative e dare l'opportunità di “guadagnare un voto” ad altri studenti (anche quelli che non partecipano al Olimpiade).

Il desiderio di leadership e di dimostrazione dei propri risultati da parte dello studente è una delle condizioni fondamentali per la partecipazione al movimento delle Olimpiadi. Certo, con tale motivazione ci sono abbastanza persone disposte a lavorare, ma durante il lavoro c'è una rotazione parziale e questo è inevitabile visto l'attuale carico di lavoro degli scolari. Per lo più rimangono i bambini laboriosi, quegli studenti che non hanno paura della sconfitta e si fissano obiettivi specifici.

Una delle principali forze guida per la partecipazione degli studenti alle competizioni di programmazione è il desiderio e l'interesse dell'insegnante, così come l'aiuto, la pazienza e la fiducia dei genitori.

Nel 1964 V. Vroom propose la “teoria delle aspettative”. Ci credeva incentivi per un lavoro efficiente e di alta qualità dipende da una combinazione di tre fattori: aspettative umane:

1. Aspettativa che lo sforzo porti al risultato desiderato.

2. L'aspettativa che i risultati portino a ricompense.

3. Aspettativa che la ricompensa sia di valore sufficiente.

Quanto maggiore è la convinzione di una persona che tutte queste aspettative saranno soddisfatte, tanto più forte sarà l’incentivo all’attività. Se cambiamo leggermente la formulazione di V. Vroom in un contesto educativo, allora ecco cosa succede:

· La teoria dell'aspettativa indica cosa dovrebbero fare gli insegnanti per garantire che gli studenti abbiano forti incentivi ad apprendere:

o Insegnare agli studenti ad ottenere i risultati richiesti e creare tutte le condizioni necessarie per questo;

o Stabilire un collegamento diretto tra i risultati del lavoro e la valutazione degli studenti;

o Studiare le esigenze degli studenti per sapere quali premi sono preziosi per loro.

Sulla base di ciò, i meccanismi di motivazione e i principali fattori di efficacia degli incentivi possono essere espressi come:

o Conoscenza da parte degli insegnanti dei bisogni, degli interessi e dei bisogni degli studenti.

o Stabilire un collegamento equo e diretto tra risultati e ricompensa.

o Immediatezza della ricompensa.

o Grado di soddisfazione delle aspettative.

Per prepararti alla programmazione delle Olimpiadi, puoi applicare una metodologia utilizzando un sistema di test "NSUTS" , sviluppato sulla base di NSU, che consente di risolvere rapidamente molti di questi punti.

Tecnologia di utilizzo del sistema "NSUTS »

Il sistema si trova a https://olimpico. *****/nsuts-test/nsuts_new_login. cgi. Cliccando su questo link verrai indirizzato alla pagina di autorizzazione, dove potrai accedere al sistema inserendo nome utente e password.

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

In questo caso scegliamo, ad esempio, Formazione scolastica, dopodiché verrai indirizzato alla pagina “ Pagina di registrazione per la formazione scolastica", dove la registrazione è semplice e diretta. Devi solo tenere presente che i dati inseriti devono essere affidabili.

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

Sul " Aiuto» Puoi leggere brevi istruzioni su come utilizzare il sistema. Diamo un'occhiata al contenuto di questa pagina.

Sistema di test NSUTS. Descrizione molto breve.

Ti trovi nel sistema di test automatico NSUTS per condurre e testare concorsi di programmazione. La sezione corrente viene visualizzata nella parte superiore dello schermo. Nell'angolo in alto a destra - il nome delle Olimpiadi attuali, il nome della tua squadra e un pulsante per terminare di lavorare con il sistema - " Esci».

Nel capitolo " Tour» è possibile selezionare il turno attuale delle Olimpiadi.

Nel capitolo " Notizia» puoi leggere i comunicati ei commenti della giuria e del comitato organizzatore delle Olimpiadi. E scopri anche l'ora di inizio e di fine delle Olimpiadi. Dopo l'inizio delle Olimpiadi, in questa pagina vengono visualizzati i collegamenti alle condizioni delle attività.

Nel capitolo " Passaggio» le attività vengono inviate per il test. Per sottoporre un problema al test, indicare la lingua in cui è scritta la soluzione e il numero del problema. Incolla il testo della soluzione nel campo di input e fai clic su " Inviare" Oppure seleziona un file utilizzando la barra di selezione file, quindi fai clic su " Inviare" La tua soluzione verrà visualizzata nell'elenco delle attività inviate nella sezione " risultati».

Le tue soluzioni devono leggere le informazioni di input da un file ingresso. TXT e genera il risultato in un file produzione. TXT . È vietato leggere dallo standard input, scrivere sullo standard output o sullo standard error. Il programma partecipante non deve aprire, leggere o modificare file diversi dagli input. txt e output. txt o altri specificati nelle condizioni dell'attività. È vietato l'accesso al file system e ad altre risorse diverse da quelle elencate nella dichiarazione del problema. La violazione di questo requisito può essere motivo di squalifica della squadra. Il limite della dimensione del codice sorgente è di 100 kilobyte. Il formato di output deve soddisfare esattamente i requisiti descritti nella dichiarazione del compito.

Il partecipante può utilizzare qualsiasi compilatore elencato nella sezione " Passaggio».

Opzioni di compilazione:

VisualC++ 6.0
Visual C++ 2005	cl. attività exe /EHsc /Ox. cpp /link /STACK:
MinGW 5.1.4 (GCC 3.4.5)	c++.exe - Wall - Wl,--stack= - Attività O2. cpp
Freepascal 2.2.0	ppc386.exe - O2 - Attività Cs. passato
Java 1.6.0_07	javac. exe. Giava
LancioGiava	java - Xmx480m - Xss32m - Djava. sicurezza. direttore - Duser. lingua=en_US Compito
Borland Delfi 2006

Nella sezione " risultati» puoi visualizzare lo stato del test e i risultati del test delle attività inviate. In linea " Tempo"Viene indicata l'ora al momento dell'invio della soluzione, il linguaggio di programmazione specificato al momento dell'invio di questa soluzione. Collegamento " Vvista fonte» mostrerà il testo della soluzione inviata.

In linea " Risultato» viene visualizzato il risultato del test:

In coda: la soluzione è in coda per il test.

Test... - in fase di test proprio in questo momento.

Limite del codice sorgente superato: il limite del codice sorgente del programma è stato superato.

Errore di compilazione: compilazione non riuscita (è indicato il motivo).

Quando la soluzione viene testata, lo stato assume uno dei seguenti valori:

ACCETTATO! - la soluzione è considerata corretta.

Risposta sbagliata: risposta sbagliata al test.

Limite di tempo superato: la soluzione non rientrava nel tempo del processore assegnato.

Timeout: la soluzione non rientrava nel tempo assegnato.

Errore di runtime: la soluzione ha restituito un codice di errore diverso da zero.

Limite di memoria superato: la soluzione non ha raggiunto il limite di memoria allocata.

Nessun file di output: non esiste alcun file di output. TXT.

Violazione della sicurezza: la decisione ha commesso un'azione vietata dalle regole.

In questo caso viene indicato il numero della prova in cui si è verificato l'errore (per le Olimpiadi ACM).

Una breve regola per costruire una valutazione per le Olimpiadi ACM è la seguente: di due squadre, quella che ha risolto un numero maggiore di problemi sarà più alta nella classifica; Se il numero di problemi è lo stesso, la squadra con il minor tempo di penalità sarà più alta. Se il numero di compiti e il tempo di penalità sono gli stessi per più squadre, queste squadre occupano più posti consecutivi.

Il tempo di penalità è la somma del tempo di penalità per tutte le attività. Il tempo di penalità per un'attività è 0 se l'attività non viene inviata. Se l'attività viene superata, il tempo di penalità viene calcolato secondo la formula:

tempo_per_passare_la_soluzione_corretta + (numero_di_tentativi_non_riusciti * 20).

Sezione " Domande e risposte» è destinato alla comunicazione con la Giuria delle Olimpiadi. È possibile porre domande alla giuria sui termini dei compiti o segnalare inesattezze nella formulazione dei compiti.

Inoltre, qualora la Giuria ritenga necessario apportare eventuali modifiche alle condizioni delle prove, le modifiche verranno pubblicate in questa sezione o nelle news.

Ora che abbiamo familiarità con le basi del funzionamento del sistema, diamo un'occhiata Come posso ottenere un incarico per le Olimpiadi?.

Nella scheda "Tour", seleziona il tour olimpico di cui abbiamo bisogno, ad esempio " Preparazione per le Olimpiadi panrusse del 21.03.2010 (Geometria) ». Successivamente, vai alla scheda "Novità" e utilizzando il collegamento "Condizioni del tour", scarica il file MS Office Word, che contiene le attività presentate per la soluzione in questo tour.

Risolto il problema, nella scheda “Invia” lo inviamo per la verifica, impostando tutti i parametri necessari (lingua, testo del programma o file con il programma). I risultati del test sono disponibili nella scheda "Risultati".

Principali classi di problemi candidati alle Olimpiadi dell'informatica

Per completare con successo non solo le Olimpiadi, ma anche le attività intracurriculari, è necessario quanto segue:

1. Essere fluente nel linguaggio e nell'ambiente di programmazione (nel nostro caso, Free Pascal), essere in grado di costruire e implementare vari algoritmi utilizzando questo linguaggio.

2. Possedere l'apparato matematico necessario.

3. Conoscere gli algoritmi per la risoluzione delle principali classi di problemi e la loro ottimizzazione.

I problemi di programmazione delle Olimpiadi coprono una gamma molto ampia di conoscenze, ma i più frequenti e i più difficili sono i seguenti:

1. Attività che utilizzano strutture di dati complesse come array, code, stack, elenchi collegati e alberi.

2. Grafici come insieme di oggetti con molte connessioni.

3. Problemi che utilizzano la geometria analitica e basati sul concetto di “vettore”.

4. Problemi di programmazione dinamica.

Consideriamo queste classi di problemi più in dettaglio.

Attività che utilizzano strutture di dati complesse come array, code, stack, elenchi collegati e alberi.

I programmi sono costituiti da algoritmi e strutture dati. I buoni programmi sfruttano entrambi. Selezionare e progettare la struttura dei dati è importante quanto progettare la procedura che la manipola. L'organizzazione delle informazioni e i metodi per accedervi sono generalmente determinati dalla natura del compito che deve affrontare il programmatore. Pertanto, ogni programmatore deve avere nel suo “bagaglio” metodi adeguati per la presentazione e il recupero dei dati che possano essere applicati in ogni situazione specifica.

Infatti, le strutture dati nei computer sono costruite sulla base di tipi di dati di base, come “char”, “integer”, “real”. Al livello successivo ci sono gli array, che sono raccolte di tipi di dati di base. Poi ci sono i record, che sono gruppi di tipi di dati a cui accede uno dei dati, e all'ultimo livello, quando gli aspetti fisici della rappresentazione dei dati non vengono più considerati, l'attenzione si rivolge all'ordine in cui i dati sono archiviati e in cui viene cercato. Essenzialmente i dati fisici sono associati a una "macchina dati" che controlla il modo in cui si accede alle informazioni nel programma. Esistono quattro “macchine” di questo tipo:

1. coda;

3. elenco collegato;

4. albero binario.

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

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

4) T.Kormen. Algoritmi. Costruzione e analisi. 2a ed. Pagina 255

5) Problemi e soluzioni http://*****/olimp/str_prb. php.

I grafici sono come un insieme di oggetti con molte connessioni.

Un grafico è un oggetto matematico astratto. È costituito da vertici e bordi. Ogni bordo collega una coppia di vertici. Se la stessa coppia di vertici è collegata da più bordi, questi bordi sono chiamati multipli. Uno spigolo che collega un vertice a se stesso si chiama cappa. Puoi camminare lungo i bordi del grafico, spostandoti da un vertice all'altro. A seconda che sia possibile camminare lungo uno spigolo in entrambe le direzioni o in una sola direzione, si distinguono rispettivamente grafi non orientati e grafi diretti. Gli spigoli orientati sono chiamati archi. Se tutti gli spigoli di un grafico hanno un peso (cioè un certo numero che corrisponde univocamente a un dato spigolo), allora il grafico viene detto pesato. I vertici collegati da uno spigolo si dicono adiacenti. Per un grafo non orientato, il grado di un vertice è il numero di archi inclusi in esso. Per un grafo orientato, viene fatta una distinzione tra il grado lungo gli archi entranti e il grado lungo gli archi uscenti. Un grafo si dice completo se esiste un arco tra qualsiasi coppia di vertici distinti.

Un grafico è un oggetto astratto e possiamo interpretarlo in diversi modi, a seconda del compito specifico. Diamo un'occhiata a un esempio. Lascia che i vertici del grafico siano le città e i bordi le strade che le collegano. Se le strade hanno traffico a senso unico il grafico è orientato, altrimenti non è orientato. Se è previsto un pedaggio sulle strade, il grafico viene ponderato.

È conveniente rappresentare un grafico su carta rappresentando i vertici come punti e i bordi come linee che collegano coppie di punti. Se il grafico è orientato è necessario disegnare una freccia sulle linee per indicare la direzione; se il grafico è ponderato, su ciascun bordo devi anche scrivere un numero: il peso del bordo.

Esistono diversi modi per rappresentare un grafico nella memoria del computer. Ulteriori informazioni sulla teoria possono essere trovate ai seguenti link:

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

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

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

4. http://libro. *****/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 e soluzioni http://*****/olimp/gra_prb. php

Problemi nell’uso della geometria analitica e nel fare affidamento sul concetto di “vettore”

La geometria computazionale è una branca dell'informatica che studia algoritmi per la risoluzione di problemi geometrici. Tali problemi sorgono nella grafica del computer, nella progettazione di circuiti integrati, dispositivi tecnici, ecc. I dati iniziali in tali problemi possono essere un insieme di punti, un insieme di segmenti, un poligono, ecc. Il risultato può essere una risposta ad alcune domande (come “intersecare se queste sono linee rette”), o qualche oggetto geometrico (ad esempio, il più piccolo poligono convesso contenente determinati punti).

In "Informatica" n. 14 è stato pubblicato un articolo di uno degli autori sui problemi di geometria computazionale nelle Olimpiadi dell'informatica. In particolare, lì sono stati formulati una serie di sottoproblemi elementari, sui quali si basa la soluzione della maggior parte dei problemi di geometria computazionale. Tuttavia, le lezioni anche con studenti delle scuole superiori matematicamente ben preparati hanno dimostrato che la risoluzione di tali sottoproblemi causa loro grandi difficoltà. Il compito o li confonde, oppure il metodo di soluzione “frontale” scelto è così complesso che gli studenti non possono completarlo senza commettere errori. L'analisi dei risultati della risoluzione dei problemi “geometrici” alle Olimpiadi panrusse di informatica porta alle stesse conclusioni. Utilizzando i collegamenti sottostanti, puoi studiare approcci alla risoluzione di problemi geometrici sul piano, che ti consentono di ottenere rapidamente e facilmente soluzioni alla maggior parte dei sottoproblemi elementari.

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

2) http://*****/articolo. aspide? id_sec=1&id_testo=1332.

3) Problemi e soluzioni http://*****/olimp/geo_prb. php

Problemi di programmazione dinamica.

Molti problemi delle Olimpiadi, così come problemi pratici di programmazione, sono problemi di enumerazione delle opzioni e di scelta tra queste opzioni quella accettabile o la migliore secondo l'uno o l'altro criterio. Tuttavia, a causa del loro numero estremamente elevato, spesso non è possibile considerare tutte le opzioni.

Fortunatamente, per una serie di problemi simili nella formulazione a problemi che richiedono effettivamente una ricerca completa di opzioni, è possibile trovare una soluzione molto più efficace. Molto spesso, in questi casi, la soluzione si riduce a trovare soluzioni a sottoproblemi di dimensione più piccola, che vengono memorizzati in una tabella e mai ricalcolati, e i sottoproblemi di dimensione più grande utilizzano queste soluzioni già trovate. Questo metodo è chiamato programmazione dinamica, detto anche metodo tabulare. In termini generali, la programmazione dinamica è intesa come un processo di soluzione passo passo di un problema di ottimizzazione, in cui ad ogni passo viene selezionata una da un insieme di soluzioni ammissibili che ottimizza una determinata funzione obiettivo o criterio. A volte, invece dell'ottimizzazione, lo stesso metodo viene utilizzato per risolvere il problema del conteggio del numero di soluzioni fattibili. In questo caso, ad ogni passaggio, invece di scegliere la soluzione ottimale, vengono riassunte le soluzioni dei sottoproblemi di dimensione inferiore e la loro formulazione non sempre coincide completamente con il problema originale (esempi corrispondenti verranno discussi di seguito). In entrambi i casi, la soluzione trovata nel passaggio corrente viene solitamente inserita in una tabella. Di norma, la connessione tra compiti e sottocompiti è formulata sotto forma di un "principio di ottimalità" ed è espressa da un sistema di equazioni (relazioni ricorrenti).

Le basi della teoria della programmazione dinamica furono gettate da R. Bellman. Si noti che la parola programmazione nel titolo sopra (programmazione dinamica), così come in “programmazione lineare”, non significa compilare programmi per un computer.

Per risolvere un problema di ottimizzazione in cui è necessario costruire una soluzione con il valore massimo o minimo (ottimale) di qualche parametro, un algoritmo basato sulla programmazione dinamica può essere formulato come segue:

1) identificare e descrivere i sottocompiti attraverso la cui soluzione verrà espressa la soluzione desiderata,

2) annotare le relazioni ricorrenti (equazioni) che collegano i valori dei parametri ottimali per le sottoattività,

3) calcolare il valore del parametro ottimale per tutte le sottoattività,

4) costruire la soluzione ottimale utilizzando le informazioni ricevute.

Se siamo interessati solo al valore del parametro, il passaggio 4 dell'algoritmo non è necessario (questa situazione è tipica, ad esempio, per problemi di conteggio del numero di opzioni fattibili o di alcune configurazioni, comprese quelle combinatorie). Tuttavia, se è necessario costruire la soluzione ottimale, a volte è necessario ottenere e memorizzare informazioni aggiuntive durante il passaggio 3 dell'algoritmo. Spesso è il passaggio 4 a rivelarsi il più difficile quando si implementano tali algoritmi.

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

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

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

4) Problemi e soluzioni http://*****/olimp/rec_prb. php

ISTITUZIONE EDUCATIVA COMUNALE - SCUOLA SECONDARIA DI MUZHEVSKAYA IN NOME A N.V. ARKHANGELSKY

“Olimpiadi dell’informatica: metodi di preparazione”

Materiale preparato da:

Insegnante di informatica

Galitskaya Irina Viktorovna

Problemi che deve affrontare l'insegnante:

· Studio di nuove forme di svolgimento delle Olimpiadi.

· Conoscenza degli algoritmi per la risoluzione dei problemi delle Olimpiadi.

· Disponibilità dei compiti stessi.

· Conoscenza dei linguaggi di programmazione.

· Tempo per studiare, eseguire il debug e verificare le attività.

· Insegnare agli studenti come organizzare correttamente le attività alle Olimpiadi.

La maggior parte degli insegnanti non può farlo. La soluzione più corretta a questa situazione è aumentare i collegamenti tra scuola e università.

Ecco alcune caratteristiche della preparazione degli scolari alla programmazione delle olimpiadi:

1. Nel curriculum scolastico non esiste una materia come la “programmazione”. Quelli. lo studente deve avere una propria motivazione abbastanza forte.

2. Esiste una limitazione secondo cui quando si risolvono i problemi è consigliabile utilizzare solo uno dei linguaggi di programmazione (SI o PASCAL).

3. L'allenamento costante è quasi a livello sportivo.

4. Viene impiegato molto tempo, la durata delle Olimpiadi con l'analisi spesso supera le 6 ore.

5. Gli algoritmi e le formule utilizzate per risolvere la maggior parte dei problemi vengono studiati solo nelle università.

Naturalmente, è necessaria anche una formazione di livello superiore affinché gli insegnanti possano lavorare con studenti dotati che partecipano a concorsi di programmazione:

· Possibile istruzione secondaria, università specializzata in programmazione.

· Corsi sull'apprendimento dei linguaggi di programmazione e della programmazione olimpica.

· Auto-preparazione utilizzando materiali provenienti da fonti aggiuntive.

Ma anche una buona conoscenza del linguaggio di programmazione non fornisce una garanzia al 100% che uno studente vincerà anche alle Olimpiadi scolastiche o distrettuali.

Idea pedagogica dell'esperienza

Il principale incentivo per uno studente a partecipare alle Olimpiadi è la motivazione. Un'occasione per dimostrare conoscenza ed erudizione sul problema da risolvere.

Nel 1964 V. Vroom propose la “teoria delle aspettative”. Credeva che l’incentivo per un lavoro efficace e di alta qualità dipendesse da una combinazione di tre fattori: le aspettative di una persona:

1. Aspettativa che lo sforzo porti al risultato desiderato.

2. L'aspettativa che i risultati portino a ricompense.

3. Aspettativa che la ricompensa sia di valore sufficiente.

Quanto maggiore è la convinzione di una persona che tutte queste aspettative saranno soddisfatte, tanto più forte sarà l’incentivo all’attività. Ho leggermente modificato la formulazione di V. Vroom in un contesto educativo, e questo è quello che è successo.

La teoria dell’aspettativa delinea cosa dovrebbero fare gli insegnanti per garantire che gli studenti abbiano forti incentivi ad apprendere:

· Insegnare agli studenti ad ottenere i risultati richiesti e creare tutte le condizioni necessarie per questo.

· Stabilire un collegamento diretto tra i risultati del lavoro e la valutazione degli studenti.

· Studiare le esigenze degli studenti per sapere quali premi sono preziosi per loro.

Sulla base di ciò, i meccanismi di motivazione e i principali fattori di efficacia degli incentivi possono essere espressi come:

1. Conoscenza da parte degli insegnanti dei bisogni, degli interessi e dei bisogni degli studenti.

2. Stabilire un collegamento equo e diretto tra risultati e ricompensa.

3. Immediatezza della ricompensa.

4. Grado di soddisfazione delle aspettative.

Tecnologia di utilizzo dell'esperienza

Naturalmente, la preparazione per le Olimpiadi è un processo lungo e laborioso.

L'utilizzo del principio "Ciò che guadagni è ciò che ottieni" consente di creare la necessità di aumentare l'attività cognitiva degli studenti, la loro autoespressione e l'interesse per attività educative produttive e il desiderio di dimostrare i propri risultati.

Implementazione dell'esperienza

L'interesse per la “programmazione delle Olimpiadi” può essere suscitato in diversi modi. Il modo migliore è espandere la conoscenza dei computer, dell'informatica, introdurre costruzioni algoritmiche nelle lezioni di informatica e successiva integrazione con una soluzione più specifica dei problemi in uno specifico linguaggio di programmazione.

Primo passo. Preparatorio. Le lezioni si svolgono in modo giocoso. Viene gradualmente introdotta una serie di comandi che consentono di coinvolgere strumenti informatici nella risoluzione dei problemi. In questo caso è sufficiente una descrizione dell'algoritmo in un qualsiasi linguaggio di programmazione.

Secondo passo. All'inizio della programmazione e durante le lezioni successive vengono introdotti vari metodi di risoluzione dei problemi utilizzando algoritmi standard implementati in un linguaggio di programmazione. Viene introdotto il concetto di “debug del programma”. È consigliabile considerare diversi percorsi di soluzione al fine di insegnare agli studenti gli elementi di una ricerca ottimale.

Terzo passo. "Insegnare la riflessione". Lo studente insegna la risoluzione dei problemi agli altri. Questo di solito accade quando si analizzano i problemi. Questo aiuta lo studente a identificare i segni di ottimalità (brevità, chiarezza), imparare a tracciare e spiegare chiaramente il funzionamento del programma.

Quarto passo. Dal secondo e dal terzo segue con la successiva complicazione dei problemi e degli strumenti per risolverli. In questa fase, è particolarmente importante coinvolgere insegnanti universitari o cercare tu stesso compiti più complessi che contribuiscano allo sviluppo del pensiero logico e fantasioso e sviluppino capacità combinatorie.

Quinto passo. "Riflessione creativa". Elaborazione da parte dello studente di problemi con soluzione dell'autore, con prove, requisiti di input e output.

Il massimo risultato di eccellenza: la creazione e l'applicazione di tecnologie educative inventate dagli studenti stessi per insegnare agli altri.

Efficienza

La metodologia per la preparazione alla programmazione delle olimpiadi può essere utilizzata per risolvere i problemi che devono affrontare gli insegnanti di informatica che preparano i partecipanti alle olimpiadi e gli studenti che partecipano alle olimpiadi. La metodologia proposta non è una panacea, ma aiuterà non solo nella preparazione delle Olimpiadi regionali, ma anche delle Olimpiadi di livello superiore.

Esistono molti programmi e test su Internet che svolgono funzioni di apprendimento a distanza e gli insegnanti li utilizzano per preparare gli studenti alle Olimpiadi. Ma! A volte, a causa della velocità e della qualità della comunicazione, è impossibile partecipare a concorsi di programmazione online. Spesso lo studente non conosce lo standard dell'interfaccia per l'invio dei compiti e, per eseguire il debug dell'attività e ottenere il risultato, deve accedere nuovamente al sito web delle Olimpiadi. La verifica e l'analisi dettagliata dei risultati richiedono tempo aggiuntivo. L'installazione di un sistema server di questo tipo in un'aula richiede molto lavoro. E sul computer di casa di uno studente al momento è praticamente impossibile. Non tutti gli insegnanti di informatica conoscono le regole per l'immissione e l'output dei dati tramite un file di testo durante l'invio e la presa di decisioni su Internet.

Attualmente sono stati sviluppati molti metodi per insegnare l'informatica. Ma, nonostante il fatto che programmazione e algoritmizzazione possano essere combinati quando si studia l'informatica, la risoluzione dei problemi di programmazione delle Olimpiadi richiede un approccio completamente diverso.

Quando si lavora con gli studenti per prepararsi alle Olimpiadi, al fine di consolidare le competenze, è necessaria la risoluzione ripetuta di problemi di un certo tipo. In questo caso, l'insegnante può consegnare il compito agli studenti a casa in formato elettronico (link al sito, in archivio), e gli studenti, dopo aver risolto i problemi, portano la loro soluzione su supporto e la sottopongono a verifica. Successivamente, i problemi vengono analizzati in gruppo e gli studenti spiegano come risolverli.

Nelle fasi successive del lavoro, i compiti diventano più complessi.

Il problema del sovraccarico psicologico e fisico

Gli studenti che partecipano alle Olimpiadi si distinguono per l'elevata capacità lavorativa e talvolta gli insegnanti, vedendolo, iniziano ad alzare gradualmente il livello dei requisiti e dei voti. Ma quando si preparano per le Olimpiadi a qualsiasi livello, non solo nella programmazione, gli studenti devono lavorare molto e con tenacia a casa, nelle lezioni e nelle attività extrascolastiche, anche nelle fasi iniziali. Uno studente apprende molti argomenti delle materie accademiche a livello base ad un ritmo accelerato solo attraverso la diligenza, una grande capacità lavorativa e con l'aiuto di insegnanti e genitori. Il compito degli insegnanti e dell'amministrazione è quello di non superare l'asticella in altre materie durante il periodo di preparazione. Pertanto, sono richiesti controllo e sostegno non solo da parte dei genitori, ma anche da parte degli insegnanti, e talvolta aiuto e comprensione da parte dell'amministrazione.

Un piano, un ordine di argomenti da studiare, che ti aiuterà a imparare come risolvere i problemi delle Olimpiadi o a trovare lacune nelle tue conoscenze.

Sezione 1. Fondamenti matematici della programmazione

Sezione 2. Tecniche di programmazione

1. Nozioni di base sul linguaggio di programmazione (Pascal, C) Variabili e tipi di dato semplici, dimensioni dei tipi. Programmi lineari. Dichiarazioni condizionali. Cicli. Procedure e funzioni. Tipi di dati complessi (array, stringhe, record, puntatori, file).

2. Array Array unidimensionali. Array bidimensionali (matrici). Array multidimensionali.

3. Linee. Elementi di parsing lessicale e sintattico Operazioni sulle stringhe. Gettoni, conteggio gettoni di vario tipo. Estrazione di numeri da una stringa.

4. Lavorare con i file Leggere e scrivere su un file di testo. Conversione dei dati ottenuti da un file in una struttura conveniente. Lavorare con file digitati. File non tipizzati. Buffer di ingresso.

5. Ricorsione Funzioni matematiche specificate ricorsivamente. Esempi di subroutine ricorsive. Il problema di fermare la ricorsione. Sostituzione della ricorsione con l'iterazione.

6. Aritmetica “lunga” Memorizzazione di numeri in un programma che non rientrano nei tipi standard. Operazioni aritmetiche su numeri "lunghi". Numeri "lunghi" con una parte decimale. Estrazione della radice con una determinata precisione.

7. Memorizzazione delle informazioni nella memoria dinamica. Memorizzazione di un insieme di dati in elenchi lineari. Inserimento in una lista, rimozione da una lista, ricerca di un elemento in una lista. Elenchi doppiamente collegati. Concetti di strutture dati stack, ad anello, a coda, a deque; la loro implementazione utilizzando la memoria dinamica. Alberi binari. Alberi con un numero indefinito di discendenti. Memorizzazione di array di grandi dimensioni.

Sezione 3. Algoritmi, metodi e principi per la risoluzione dei problemi.

1. Il concetto di complessità dell'algoritmo. Definizione di complessità.

2. Algoritmi di ricerca e ordinamento Cerca un elemento in un array non ordinato. Ricerca binaria per chiave in un array ordinato (dicotomia). Ricerca di Fibonacci. Ricerca di un array ordinato n-dimensionale. Trovare il k-esimo elemento più grande dell'array. Metodi di ordinamento semplici (bolla, selezione, inserimento, conteggio). Metodi veloci ("fast", "merge", "pyramid"), bilanciamento di alberi binari. Ordinamento utilizzando il metodo scoop.

3. Risoluzione di problemi utilizzando il metodo di enumerazione delle opzioni Utilizzo della ricorsione per l'enumerazione. Generazione di combinazioni, posizionamenti, permutazioni e insiemi booleani. Completamente eccessivo. Eliminare le opzioni (euristica). Metodo del branch e del bound.

4. Geometria computazionale e metodi numerici Lunghezza di un segmento. Equazione di una retta. Prodotto scalare e vettoriale. Il punto di intersezione dei segmenti. Appartenenza di un punto ad una figura su un piano (ad esempio: un triangolo). Area di un poligono convesso. Involucro convesso di un insieme di punti: Graham, Jarvis, algoritmi divide et impera. La coppia di punti più vicina. Metodo di Gauss per la risoluzione di un sistema di equazioni lineari. Trovare una soluzione all'equazione.

5. Il principio della programmazione dinamica Concetto, applicabilità. Confronto con la forza bruta.

6. Algoritmi greedy Concetto, applicabilità. Confronto con la forza bruta e la programmazione dinamica.

7. Teoria dei grafi. Algoritmi sui grafici Il concetto di grafico. Definizioni di teoria dei grafi. Strutture dati per rappresentare un grafico in un programma. Algoritmi per l'attraversamento dei grafi (ricerche in ampiezza e in profondità). Labirinto (metodo delle onde). Ciclo di Eulero. Cammino minimo in un grafo pesato (algoritmi di Dijkstra e Minty). Chiusura transitiva di un grafo (algoritmo di Floyd-Warshill). Albero di copertura minimo (algoritmi Prim e Kruskal). Ordinamento topologico di un grafo. Flussi nelle reti (algoritmo di Ford-Fulkerson). Matching in un grafo bipartito (metodo della catena estesa, soluzione di flusso). Problema di assegnazione, assegnazioni collo di bottiglia (algoritmo ungherese). Giochi sui grafici. Libro da colorare grafico. Tracciare un grafico su un piano. Grafico fortemente connesso e biconnesso. Isomorfismo del grafico. K-cricca. Ciclo di Hamilton.

8. Analisi lessicale e sintattica Compito "Calcolatrice". Diagrammi di sintassi. Forme di Backus-Naur. Modello di analisi stack e ricorsivo. Macchine a stati finiti. Grammatici.

9. Problemi con una svolta

Sezione 4. Olimpiadi dell'informatica

1. Norme per lo svolgimento dei concorsi di programmazione

2. Errori tipici e debug del programma

3. Tecniche olimpiche

Secondo me, il valore più grande sono le sezioni 2 e 3. Se non dovresti avere difficoltà nell'apprendimento di un linguaggio di programmazione (ci sono moltissimi libri su questo argomento), allora con gli algoritmi sarà più difficile. Ci sono anche molti libri su questo argomento, ma molto spesso sono troppo sovraccarichi di teoria e alle Olimpiadi è necessaria solo la pratica. Dalle fonti elettroniche sugli algoritmi, posso consigliare il libro di S.M. Okulov e il sito algolist.manual.ru, che è meno mirato allo studio dell'informatica delle Olimpiadi rispetto al libro di Okulov, ma contiene un gran numero di algoritmi che non sono presenti libri, ma quali fossero belli mi piacerebbe sapere. Abituati a lavorare nella modalità: scrittura + debug in Borland Pascal/Borland C++ e compilazione (con modifiche preliminari alle costanti) in Free Pascal/GNU C. I nuovi compilatori a 32 bit non hanno un limite di memoria rigido e funzionano molto più velocemente (la differenza nella velocità di esecuzione dei programmi a 16 e 32 bit su P4). Questa tattica astuta è spiegata dalla mancanza di un debugger decente nelle nuove piattaforme e dalla loro quasi completa compatibilità con i compilatori Borland (in FP, non dimenticare di chiudere il file di output).

Preparare gli studenti alle Olimpiadi dell'Informatica. Programma di preparazione individuale per la fase municipale delle Olimpiadi panrusse per gli scolari nella materia "Informatica e TIC" Piano di preparazione per le Olimpiadi dell'informatica

Articolo del docente del JIVT Lyceum No. 8 Pangina N.N. dalla rivista “Computer Tools in Education”, N1, 2000

Preparare gli studenti alle Olimpiadi dell'informatica.

Questo articolo e le seguenti fonti.

I migliori articoli sull'argomento