At present, the problem of preparing schoolchildren for Olympiads in Informatics at various levels is of particular relevance. The main distinguishing feature of these olympiads is that they are actually programming olympiads and the level of tasks does not correspond much to the content of the school course in computer science and ICT.
In the lyceum of the city of Fryazino, this problem is solved in a comprehensive manner:
In profile mathematical 8th grades, in addition to the program, one hour per week is allocated for the subject of computer science
· Programming is singled out as a separate subject in specialized classes of high school
· Since 2007, we have an institution of additional education, the School "Young Programmer", which does not replace, but complements the school course of computer science
In practice, familiarity with the rules for holding Olympiads and “fighting” with typical errors when debugging programs is carried out practically when submitting tasks to an automated testing system. In practical work with students in preparation for the Olympiads, in order to consolidate skills, it is required to repeatedly solve problems of a certain type. Therefore, each "Olympiad" student receives his own, individual homework on the distance learning website, the analysis of unsolved problems is carried out in a group, in the classroom at a computer school. The preparation of a student for the Olympics consists of constant training and most of all resembles the preparation of an athlete for competitions. It should be borne in mind that the duration of the Olympiads with the analysis of problems is at least 6 hours, so psychological preparation is of particular importance. The task of teachers and administration is not to exceed the bar in other subjects for the period of preparation. It requires control and support not only from parents and teachers, but sometimes help and understanding from the administration.
In the last 6 years, students of the Lyceum have repeatedly become winners and prize-winners of Olympiads of various levels: the Final Stage of the All-Russian Olympiad, the Moscow Regional Olympiad, the Open Olympiad "Information Technologies", the Olympiad for schoolchildren "Lomonosov", the Open Olympiad for Schoolchildren in Informatics and Programming, Municipal Olympiads, Moscow Programming Olympiad, All-Russian competition KIT and others.
How to prepare for Olympiads in Informatics in such conditions?
Find talented students and get them excited about programming
Keep from the "temptations" of on-line life
Become their friend and form a team of them
· Work closely with parents, administration, class teachers and subject teachers
Be prepared for the fact that at some stage one of them outgrows you
So, if you are a novice computer science teacher (or maybe with experience), who wants to try to prepare his students for the regional computer science olympiad - this page is for you.
This section will contain information that will help you make first steps, together with the author of the site, on the way of preparing schoolchildren for regional olympiads in informatics. Why not to the Republicans? Yes, because I can not help with this, at the moment.
The decision to try to prepare students in grades 9-11 for the regional Olympiad in Informatics, I made right after I became a teacher of computer science (4 years ago). After reviewing the tasks for the past years, I realized that I could not solve any of them. I could stop there, but I decided to give it a try anyway.
What is currently available? On the one hand, a novice computer science teacher, on the other hand, students are familiar only with the basics of programming. But, there is the main thing - the mutual desire to learn.
As you understand, a good knowledge of the school computer science course absolutely does not guarantee successful performance at the Olympiads. Accordingly, it is necessary to engage with students outside of school hours. Personally, I did not have to convince the headmaster of the need to organize a programming circle for a long time.
As for home computers, the situation is improving year by year. However, in many rural schools in our area, the vast majority of students do not have home computers. It sounds crazy in 2009, but that's the reality of rural life. In such a situation, you have to study in the school computer science office.
To begin with, I recommend purchasing a few good books, I place them in order of increasing complexity of the material. If books are not available in bookstores, then you can order books by clicking on the direct links below. Links lead to the online store books.ru, in which I have repeatedly ordered books for myself. I have no complaints about the quality of service. Delivery time for books is 10-14 days.
Programming in Pascal.Written by Sam Abolrus. If you decide to teach the Pascal programming language at school, but programming is your "Achilles' heel", then this book is for you. The original title of the book, translated from English, is "Learning Pascal in Three Days". Indeed, you can learn the basics of programming in Pascal with the help of this book in a couple of days. The author is a programmer at Microsoft. I strongly recommend purchasing it. My rating for this book is 5 (excellent). |
Basics of programmingOkulov S. This is a book that everyone who decides to learn how to solve olympiad problems in computer science should have. This is probably the best book I have come across on this subject. The story begins with the study of the Turbo Pascal programming environment, and ends with solving problems on graphs. I strongly recommend purchasing this book. My rating for this book is 5 (excellent). |
Programming in algorithmsAnother bestseller by Sergei Okulov. Some information is repeated from the book above, but basically this book contains more complex material than the previous one. Such topics as "Combinatorial programming", "Search and methods of its reduction", "Algorithms on graphs", etc. are considered in detail. Due to the fact that not a single Olympiad in Informatics is complete without complex problems, which undoubtedly include problems on graphs, it is not bad to have this book in your arsenal. My rating for this book is 5 (excellent). |
Olympiad problems in programming (+CD)Fedor Menshikov. The book is intended for users who are already familiar with solving simple programming problems. Typical tasks encountered at various Olympiads for schoolchildren and students are considered. The disk attached to the book contains additional material, as well as a testing system for computer verification of problem solving. My rating for this book is 5 (excellent). /p> |
You will also find something useful on this site:
- Programming in Turbo Pascal. Materials for lessons. Pretty high-quality material, I strongly recommend downloading in the ZIP archive (224Kb)
- A book on solving Olympiad problems on graphs. I found this book, in electronic form, on the website of the notorious Mikhail Gustokashin (his articles can be found in the PC World magazine and the Informatics newspaper). Perhaps, this material is one of the best dedicated to solving graph programming problems. The material binding goes to the Pascal language. I recommend downloading this book to all computer science teachers who are preparing students for Olympiads in computer science. Download Okulov's book in RAR archive (724 Kb).
Video tutorials on programming
Preparing schoolchildren for the Olympiad
It's no secret to anyone that only success helps a person to believe in himself and strive to overcome new heights. To successfully participate in the programming Olympiad, a student must:
Proficiency in a programming language (Pascal or C/C++)
1. invent and implement algorithms for solving problems;
2. estimate the time of their work;
3. test;
4. debug your programs.
Know the following algorithms:
Integer arithmetic algorithms
1. Search for divisors of a number. Prime numbers 2. Decomposing a number into prime factors 3. Finding the greatest common divisor (GCD) and least common multiple (LCM) 4. Representing numbers. Selection of digits of a number 5. Translation of numbers from one number system to another 6. Divisibility of numbers 7. Operations with multi-valued (large) numbers
Recurrent equations and dynamic programming
1. Concept of task and subtask
2. The concept of a recurrence relation
Problems of combinatorics
1. Permutations
2. Combinations
3. Accommodations
4. Subsets
5. Implementation of enumeration of options. Reducing enumeration
10-11 grade
Data Structures
1. Queues
graph theory
1. Basic concepts of graph theory
2. Adjacency and incidence
3. Representation of graphs
4. Routes
5. Routes in columns
6. Breadth first search
7. Depth-first search
8. Exhaustive backtracking
9. Algorithm for constructing the shortest paths
10. Euler graphs
11. The main theorem on the Euler graph
12. Algorithm for constructing the Euler cycle
Sorting
1. The concept of sorting
2. Sort by simple exchange
3. Quadratic algorithms
4. Algorithms of order n log n
5. Linear search
6. Binary search
Geometry
2. Triangle
3. Area of an arbitrary triangle
4. Wonderful lines and triangle points
5. Polygon
6. Convex polygon
7. Area of a simple flat polygon
recursion
1. Examples of recursive programs.
2. Recursive processing of trees
When preparing your students for the tournament, do not forget to give them a few tips:
1. If you are participating in a tournament for the first time, look in advance for examples of the proposed tournament problems, for example, in the Olympiad archives, presented on the sites.
2. All solutions are checked automatically, and if the output file contains extraneous information or if its format does not match the one described in the condition, it will be considered incorrect.
3. Your program should not display anything on the screen (unless it is specifically stated in the problem statement), and also wait for any user input.
4. A common mistake is the situation when, after the end of the program, the program waits for a key to be pressed. During automatic testing, no one will press this key, and the program will be considered to have exceeded the time limit (that is, hung or inefficient).
5. First of all, you must be able to work with text files (read and write information).
6. It's best to try working with files before you come to the olympiad, it's not difficult - most likely you can easily figure out how to do it by looking at the example below
And while the teacher is preparing schoolchildren for the tournament, one must not forget: everyone can make mistakes. Therefore, it is better to warn them than the student will make these mistakes during the tournament. You can do this simply: disassemble some tasks step by step, going through those stages of solving the problem, at which most people usually make mistakes.
Consider a task that, on the one hand, does not require deep knowledge of the programming language, and on the other hand, can serve as a useful example.
Task. Given integers A and B, modulo not exceeding 32000. Find their sum.
It would seem that there is nothing difficult, but this task is not in vain given almost every year at the qualifying rounds of various team programming Olympiads.
The point is the restriction on integer types in the programming systems Borland Pascal and Borland C ++, which are quite often used by schoolchildren.
Problem solving (with analysis of errors).
The input file a.in contains two natural numbers, each of which does not exceed 32000. The numbers in the input file are separated by spaces and (or) newlines. Output the sum of these two numbers to the output file a.out.
It seems that any schoolchild familiar with programming can easily write her solution:
Problem A: Sum of two numbers
Input file name: a.in
Output file name: a.out
Time limit: 1 sec
Memory Limit: 64MB
Let's use standard file variables: Input and Output.
They are automatically closed after the program is running.
The variable Input is by default associated with the keyboard, and Output is associated with the display screen
Since only numbers are written in the input file, we will use the read command for reading - it itself skips spaces and newlines
Using the ASSIGN procedure, we reassign the I/O identifiers INPUT and OUTPUT and specify the name of the input and output file:
ASSIGN(INPUT, "a.in"); RESET(INPUT);
ASSIGN(OUTPUT, "a.out"); REWRITE(OUTPUT);
1. On drive C, create a folder C: OLIMPIAD
var a,b,c:integer;
assign(input,"a.in"); (Establishing a link to the a.in file)
reset(Input); (Open file for reading)
read(Input,a,b); (Reading data from a file)
assign(Output,"a.out"); (Establish a link to the a.out file)
rewrite(Output); (Open file for writing)
writeln(output,c); (Write data to file)
2. Save the source C in it: OLIMPIAD a.pas (Figure 2)
Figure 2. Saving the source file
3. Open notepad.
4. Enter the initial data through a space (Figure 3)
Figure 3. Entering initial data
5. Save the file with the initial data in the OLIMPIAD folder under the name a. in
6. There are two files in the OLIMPIAD folder: (Figure 4)
Figure 4. View of folder No. 1 OLIMPIAD
7. Run the program for execution (Figure 5)
Figure 5. Launching the program for execution
8. In the OLIMPIAD folder, the third file (Figure 6):
Figure 6. Folder view №2 OLIMPIAD
9. Let's see the result (Figure 7)
Figure 7. View of the window with the result
Looks like the problem is solved
We send the work for verification, and we get an unexpected result.
Several tests passed. On some tests, an error occurs during execution
So what are the mistakes? Once again, carefully read the condition and dwell on the restrictions
1. Natural numbers not exceeding 32000.
2. We declared variables of type integer, the range of values of variables of this type is from -32768 to 32767, so everything seems to be correct here.
3. However, the test satisfies the condition, in which both numbers are equal to 32000.
4. Of course, both numbers are included in the integer type, which cannot be said about their sum!
5. Changing the integer type to the longint type in our program, we get a really complete solution to the problem
6. If you make the variable type c - longint, and leave a and b as integer, then the program will not work anyway - think about why.
var a,b,c:longint;
assign(input, "a.in");
assign(output, "a.out");
rewrite(output);
About the methodology for solving Olympiad problems
The popularity of major competitions in computer science and programming is growing rapidly. Their sponsors are such large corporations as AT&T, Microsoft, IBM, Google. Naturally, there were studies on how to effectively participate in competitions, prepare for them, numerous tips and eyewitness accounts.
The need for a methodology for preparing for programming olympiads arose long ago. Various approaches have appeared for teaching solving Olympiad problems and complex systems for preparing for Olympiads using Internet information resources. Sites with interactive task archives began to appear. Not only is the text of the problem available in them, as in libraries, but it is also possible to send a solution for verification. The student registers on the site, chooses the Olympiad and solves it within a certain time. After that, he sends to the site solutions to problems (in the form of source codes), which are automatically checked.
In March 2011, the first distance Olympiad (see above, paragraph 2.5) was held in Kazakhstan according to this type.
Conclusions. The organization and holding of tournaments in informatics, programming at all levels must be subject to uniform requirements. Only in such a situation, a student, having come to participate in the next round (district, city, regional, republican, international olympiads), will be able to show the acquired knowledge, skills and abilities at a high level. And therefore, every computer science teacher who prepares his pupils for participation in tournaments must know these rules and teach them to the children.
The site, maintained by the Moscow Center for Continuing Mathematical Education, contains a large number of programming tasks of various levels. Ideal for those who are taking their first steps in programming: many sections have links to theoretical material on the relevant topic, most of the tasks are accompanied by a detailed analysis. Automated decision checking is available for all tasks.
Olympics All-Russian Olympiad in Informatics The regional stage will be held on January 16 and 18, 2020
Competition for schoolchildren of 5-11 grades. Winners and prize-winners of the final receive benefits when entering universities
Informatics
codeforces.com. A portal that unites a huge number of participants in programming competitions around the world. The site regularly hosts online competitions for schoolchildren of various levels: from beginners to multiple world champions. Many well-known companies, including VKontakte, Mail.Ru, Tinkoff Bank and AIM Tech, hold official competitions on the platform.
In addition, everything related to programming is discussed on the portal, starting from just published articles about data structures and ending with emotions about a recent competition. The site also contains a large archive of tasks available for automated verification.
Wiki abstracts. Encyclopedia of Discrete Mathematics and Theory of Algorithms compiled by ITMO students. It describes most of the algorithms used in programming olympiads. Many articles contain examples of problems and pseudocodes of the above algorithms. The notes are very detailed and well written. This is one of the few resources in Russian on this topic.
Maximal. A mini-encyclopedia containing the most popular algorithms in computer science Olympiads, most of which have implementations and examples of use. The site has a slightly more informal style of presentation (which can sometimes affect the quality of articles or the correctness of algorithms), but it makes it easier to perceive information. The site contains links to useful books for a more detailed study of the above algorithms, as well as some specific problems of particular interest.
Olympiad in Informatics. A site dedicated to the Olympiads for schoolchildren in programming in St. Petersburg, the official site of the All-Russian Team Olympiad for Schoolchildren (VKOSHP), the Individual Olympiad for Schoolchildren in Informatics and Programming (IOIP). One of the main advantages of this site is a very rich archive of events held in Russia, including the All-Russian Olympiad: the site contains presentations with a breakdown of tasks and competition results. Also, individual and team competitions for schoolchildren are regularly held here.
Olympiads.ru. A site dedicated to the Olympiads in programming for schoolchildren in Moscow, the official website of the Open Olympiad for schoolchildren in programming, the tasks on which are not inferior in complexity to the tasks of the All-Russian, and sometimes more elegant and interesting. In addition, the Olympiad includes a correspondence round, the tasks of which often require the study of new algorithms during the competition. The site contains materials from past competitions, as well as links to information about upcoming events.Books
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms. Construction and analysis. This book is a classic textbook with a detailed description of algorithms and data structures, as well as the basic knowledge of discrete mathematics that every programmer needs. In addition, the book contains a huge number of exercises of varying complexity, which will be of interest to the most sophisticated reader. It has a very successful style of presentation, and although it is aimed at students, most of the material will be available to schoolchildren.
1The article presents the substantiation of the role of task systems in preparing schoolchildren for computer science olympiads, descriptions of the content component of task systems used in preparation, and the requirements that are taken into account when designing task systems; the author's step-by-step model of the process of designing systems of tasks and an example of a system of tasks. The methodology for preparing schoolchildren for Olympiads in Informatics based on the use of problem systems and the author's stage model of the formation of giftedness in the conditions of preparing schoolchildren for Olympiads in Informatics have undergone a long experimental approbation. The theoretical significance of the results of the study is due to the contribution to the theory of the formation of giftedness and the formation of readiness to participate in Olympiads in Informatics. In the course of the study, it was substantiated that the results of preparation for the Olympiads determine the specifics of the process of formation of giftedness in schoolchildren.
task systems
Olympiads for schoolchildren
task system design
methodology for preparing for the olympiads
giftedness
1. Ball, G.A. Theory of educational tasks: psychological and pedagogical aspect. - M .: Pedagogy, 1990. - 184 p.
2. Kiryukhin, V.M., Okulov, S.M. Methods for solving problems in informatics. International Olympiads. – M.: BINOM. Knowledge Laboratory, 2007. - 600 p.
3. Pedagogy of vocational education: development prospects: monograph. Book. 3 / O.V. Alekseeva, N.A. Burmistrova, V.D. Vasilyeva, N.N. Golovina, O.N. Kravchenko, E.S. Pavlova and others; ed. S.S. Chernov; Center for the Development of Scientific Cooperation. - Novosibirsk: SIBPRINT Publishing House, 2010. - 245 p.
4. Working concept of giftedness / D.B. Bogoyavlenskaya, V.D. Shadrikov, Yu.B. Babaeva, A.V. Brushlinsky, V.N. Druzhinin, etc. - M .: IChP Publishing house "Magister", 2003.
5. Smykovskaya, T.K. Olympiads in programming as a factor in the development of giftedness of students and schoolchildren / T.K. Smykovskaya, E.S. Pavlova // Bulletin of the Volgograd Academy of the Ministry of Internal Affairs of Russia. - 2010. - No. 1. - C. 125–127.
Currently, for students of senior school age, one of the most effective means of identifying abilities and levels of giftedness, as well as developing intellectual and creative abilities, is preparation and participation in subject Olympiads. Among all school subjects, computer science can be singled out as the most dynamic subject, because the content of Olympiad problems in informatics is constantly changing. It should be noted that regional and regional computer science olympiads are traditionally programming olympiads, while school and sometimes city olympiads are ICT olympiads.
Our surveys of computer science teachers in schools in the Volgograd region show that the main role in preparing schoolchildren for Olympiads in this subject is occupied by tasks. Analysis of tasks for olympiads in informatics (programming) in the context of content showed that they include tasks on data sorting and enumeration, dynamic programming, modeling, optimization, long arithmetic, linear and binary search, greedy algorithms, recursion, graph theory, combinatorics and working with data of string and file types .
Many years of experience in preparing schoolchildren for programming competitions in the Volgograd region shows that it is advisable to use complex systems of problems as a basis for conducting classes, not individual tasks. A variety of sets of tasks included in the task systems for preparing for Olympiads in Informatics allow you to:
1) gradually complicate the studied material;
2) gradually increase the amount of work;
3) increase the level of independence of students;
4) to involve elements of the theory for solving cognitive problems;
5) to teach methods of reasoning (both according to the model and independently) taking into account the principle of task variability;
6) to form the most important characteristics of creative abilities: fluency of thought (the number of ideas that arise per unit of time), mental flexibility (the ability to switch from one thought to another), originality (the ability to find solutions that differ from the generally accepted ones); curiosity (sensitivity to problems in the surrounding world), the ability to put forward and develop hypotheses.
When building systems of tasks, we take into account the requirements that determine the pedagogical expediency of their use: didactic, reflecting the corresponding traditional and specific principles of education; and methodical, taking into account the peculiarities of computer science as an academic subject and science. In preparation for the Olympiads in Informatics, we identified the following requirements for problem systems:
1) the key task (the presence of tasks grouped into nodes around unifying centers - tasks in which facts or methods of activity are considered that are used in solving other tasks and are of fundamental importance for mastering the subject content);
2) connectivity (the ability to graphically represent the set of tasks by a connected graph, in the nodes of which are the key tasks, above them - preparatory and auxiliary, below - consequences, generalizations, and so on);
3) target sufficiency (the presence of a sufficient number of tasks for training in the classroom and at home, similar tasks for fixing the solution method, tasks for individual and group tasks of different directions, tasks for independent (including research) activities of students, tasks for current and final control taking into account fallback options, and so on);
4) psychological comfort (the system of tasks takes into account the presence of different temperaments, types of thinking, types of memory).
At the first stages of preparation for Olympiads in Informatics, we designed problem systems empirically, but later we came to the conclusion that the process of creating problem systems should include the following steps: analytical (analysis of the content of the educational material and the requirements of the standard, formulating goals and setting them mutual correspondence, selection of content), design (selection of methods and methodological techniques, determination of the forms of presentation of educational material, methods of its presentation) and technological (technical creation of task systems in accordance with the requirements).
On the topic “Programming Techniques”, we have developed systems of tasks for programming branching and cyclic computational processes, systems of tasks for working with one-dimensional and two-dimensional arrays, for processing character strings, for studying recurrent algorithms, algorithms for long arithmetic and dynamic data structures, and on the topic “ Algorithms, methods and principles for solving problems” - systems of problems for studying linear and binary (binary) search algorithms, information sorting algorithms, enumeration (permutation) of data, dynamic programming, algorithms for working with graphs.
Let us give an example of a system of tasks for studying information retrieval algorithms, which consists of tasks constructed by modifying the condition or requirement of key tasks. When describing the system, the following notations are used: Y (condition) - an array of variable length is given, B (basis) - the ability to view the entire array (from the first to the last element), T (requirement) - find the elements of the array according to given conditions, C (method) - view the entire array and print the elements that meet the specified condition.
Task 1. Find all positive elements in a one-dimensional array A(N) (N≤100) (restriction condition).
Problem 2. Find all even elements in a one-dimensional array A(N) (N ≤ 100) (restriction condition).
Problem 3. In a one-dimensional array A(N) (N ≤ 100) find all even positive elements (obtained from the previous one by adding to the condition).
Task 4. In a one-dimensional array A(N) (N≤100) find all even positive elements with indices divisible by 3 (obtained from the previous one by adding to the condition).
Problem 5. In a one-dimensional array A(N) (N ≤ 100), double all even positive elements (obtained from Problem 4 by changing the requirement).
Problem 6. In a one-dimensional array A(N) (N ≤ 100), square all elements falling in the interval from -2 to 5 (obtained from Problem 4 by changing the requirement).
In the process of approbation of the systems of tasks developed by us, a methodology for preparing for Olympiads in Informatics was created based on the use of task systems, which was built taking into account the specifics of the target (system of goals - learning using a system of tasks), content (didactic content units that require display in task systems) and procedural (information, definition of types, forms and ways of presenting educational information in accordance with the features of the methodological style of the teacher) components of the methodological system of the computer science teacher, implemented in task systems.
This technique is used by the teachers of the Lyceum at the Faculty of Pre-University Training of the Volgograd State Technical University in preparing schoolchildren for Olympiads in Informatics from 2003 to the present.
Long-term observations of schoolchildren participating in the process of preparing for Olympiads in Informatics have shown that the use of task systems, in addition to preparing for Olympiads, still affects the development of giftedness. Therefore, in the process of pedagogical research, we developed a three-stage model of the formation of giftedness in the conditions of preparing schoolchildren for Olympiads in Informatics, while constructing which we focused on the fact that at each stage of preparation for Olympiads, students are directly involved in the process of forming their giftedness. The first stage is the stage of self-determination (self-identification of giftedness) of the student, the second - the stage of determining the boundaries of his giftedness, the third stage is the realization of how you can independently participate in the process of forming your giftedness. This model is the theoretical basis for our further methodological work.
This stage model has made adjustments to the content and procedural components of the methodology developed by us for preparing for Olympiads in Informatics based on the use of task systems. The constructed systems of tasks become the basis for the development of individual educational trajectories for each student, which leads to the formation of students' giftedness through the development of students' abilities and the realization of their personal creative potential. The methodology has become staged, thus ensuring the diversity of individual educational trajectories and the three-stage process of preparing for Olympiads in Informatics and the formation of giftedness using complexes of task systems and a combination of full-time and distance learning.
Reviewers:
Smykovskaya T.K., Doctor of Pediatric Sciences, Professor of the Department of Theory and Methods of Teaching Mathematics and Informatics, Volgograd Social and Pedagogical University, Volgograd;
Petrova T.M., Doctor of Pediatric Sciences, Professor of the Department of Theory and Methods of Teaching Mathematics and Informatics, Volgograd Social and Pedagogical University, Volgograd.
The work was received by the editors on 08.10.2013.
Bibliographic link
Pavlova E.S. METHODOLOGY OF FORMING GREAT PERSONS IN PREPARATION FOR OLYMPIADS IN COMPUTER SCIENCE // Fundamental Research. - 2013. - No. 10-6. - S. 1360-1362;URL: http://fundamental-research.ru/ru/article/view?id=32547 (date of access: 01/05/2020). We bring to your attention the journals published by the publishing house "Academy of Natural History"
