Подготовка к олимпиаде по информатике методика. Олимпиады по информатике: методика подготовки
В статье представлены обоснование роли систем задач при подготовке школьников к олимпиадам по информатике, описания содержательной составляющей систем задач, используемых при подготовке, и требования, которые учитываются при конструировании систем задач; авторская этапная модель процесса конструирования систем задач и пример системы задач. Методика подготовки школьников к олимпиадам по информатике на основе использования систем задач и авторская стадийная модель формирования одаренности в условиях подготовки школьников к олимпиадам по информатике прошли длительную экспериментальную апробацию. Теоретическая значимость результатов исследования обусловлена вкладом в теорию формирования одаренности и формирования готовности к участию в олимпиадах по информатике. В ходе исследования обосновано, что результаты подготовки к олимпиадам обусловливают специфику процесса формирования одаренности у школьников.
системы задач
олимпиады школьников
конструирование систем задач
методика подготовки к олимпиадам
одаренность
1. Балл, Г.А. Теория учебных задач: психолого-педагогический аспект. – М.: Педагогика, 1990. – 184 с.
2. Кирюхин, В.М., Окулов, С.М. Методика решения задач по информатике. Международные олимпиады. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.
3. Педагогика профессионального образования: перспективы развития: монография. Кн. 3 / О.В. Алексеева, Н.А. Бурмистрова, В.Д. Васильева, Н.Н. Головина, О.Н. Кравченко, Е.С. Павлова и др.; под ред. С.С. Чернова; Центр развития научного сотрудничества. – Новосибирск: Изд-во «СИБПРИНТ», 2010. – 245 с.
4. Рабочая концепция одаренности / Д.Б. Богоявленская, В.Д. Шадриков, Ю.Б. Бабаева, А.В. Брушлинский, В.Н. Дружинин, и др. – М.: ИЧП Изд-во «Магистр», 2003.
5. Смыковская, Т.К. Олимпиады по программированию как фактор развития одарённости студентов и школьников / Т.К. Смыковская, Е.С. Павлова // Вестник Волгоградской академии МВД России. – 2010. – № 1. – C. 125–127.
В настоящее время для учащихся старшего школьного возраста одним из наиболее эффективных средств выявления способностей и уровней одаренности, а также развития интеллектуальных и творческих способностей являются подготовка и участие в предметных олимпиадах . Среди всех школьных предметов можно выделить информатику как наиболее динамичный предмет, т.к. содержание олимпиадных задач по информатике постоянно изменяется. Следует отметить, что областные и региональные олимпиады по информатике традиционно являются олимпиадами по программированию, а школьные, а иногда и городские олимпиады - это олимпиады по ИКТ.
Проведенные нами опросы учителей информатики школ Волгоградской области показывают, что главную роль при подготовке школьников к олимпиадам по данному предмету занимают задачи. Анализ задач для олимпиад по информатике (программированию) в контексте содержания показал, что они включают задачи по сортировке и перебору данных, динамическому программированию, моделированию, оптимизации, длинной арифметике, линейному и двоичному поиску, жадным алгоритмам, рекурсии, теории графов, комбинаторике и по работе с данными строкового и файлового типов .
Многолетний опыт подготовки школьников к олимпиадам по программированию в Волгоградской области показывает, что в качестве основы для проведения занятий целесообразно использовать не отдельные задачи, а комплексные системы задач. Разнообразные наборы задач, входящих в системы задач для подготовки к олимпиадам по информатике, позволяют:
1) постепенно усложнять изучаемый материал;
2) поэтапно увеличивать объем работы;
3) повышать уровень самостоятельности учащихся;
4) привлекать элементы теории для решения познавательных задач;
5) обучать способам рассуждения (как по образцу, так и самостоятельно) с учетом принципа вариативности задач;
6) формировать важнейшие характеристики творческих способностей: беглость мысли (количество идей, возникающих за единицу времени), гибкость ума (способность переключаться с одной мысли на другую), оригинальность (способность находить решения, отличающиеся от общепринятых); любознательность (чувствительность к проблемам в окружающем мире), умение выдвигать и разрабатывать гипотезы.
При построении систем задач мы учитываем требования, определяющие педагогическую целесообразность их использования : дидактические, отражающие соответствующие традиционные и специфические принципы обучения; и методические, учитывающие особенности информатики как учебного предмета и науки. При подготовке к олимпиадам по информатике мы выделили следующие требования к системам задач:
1) ключевая задача (наличие задач, сгруппированных в узлы вокруг объединяющих центров - задач, в которых рассматриваются факты или способы деятельности, применяемые при решении других задач и имеющие принципиальное значение для усвоения предметного содержания);
2) связность (возможность графически представить совокупность задач связным графом, в узлах которого ключевые задачи, выше них - подготовительные и вспомогательные, ниже - следствия, обобщения и так далее);
3) целевая достаточность (наличие достаточного количества задач для тренировки в классе и дома, аналогичных задач для закрепления метода решения, задач для индивидуальных и групповых заданий разной направленности, задач для самостоятельной (в том числе исследовательской) деятельности учащихся, задач для текущего и итогового контроля с учетом запасных вариантов и так далее);
4) психологическая комфортность (система задач учитывает наличие разных темпераментов, типов мышления, видов памяти).
На первых этапах подготовки к олимпиадам по информатике мы конструировали системы задач эмпирическим путем, но в дальнейшем мы пришли к тому, что процесс создания систем задач должен включать в себя следующие этапы: аналитический (анализ содержания учебного материала и требований стандарта, формулирование целей и установление их взаимного соответствия, отбор содержания), проектировочный (выбор методов и методических приемов, определение форм представления учебного материала, способов его подачи) и технологический (техническое создание систем задач в соответствии с предъявляемыми требованиями).
По теме «Техника программирования» нами разработаны системы задач по программированию разветвляющихся и циклических вычислительных процессов, системы задач для работы с одномерными и двумерными массивами, для обработки строк символов, для изучения рекуррентных алгоритмов, алгоритмов длинной арифметики и динамических структур данных, а по теме «Алгоритмы, методы и принципы решения задач» − системы задач для изучения алгоритмов линейного и двоичного (бинарного) поиска, алгоритмов сортировки информации, перебора (перестановки) данных, динамического программирования, алгоритмов работы с графами.
Приведем пример системы задач для изучения алгоритмов поиска информации, которая состоит из задач, построенных путем модификации условия или требования ключевых задач. При описании системы используются следующие обозначения : У (условие) - задан массив переменной длины, Б (базис) - умение просматривать весь массив (с первого до последнего элемента), Т (требование) - найти элементы массива по заданным условиям, С (способ) - просмотреть весь массив и отпечатать элементы, удовлетворяющие заданному условию.
Задача 1. В одномерном массиве A(N) (N≤100) найти все положительные элементы (ограничение условия).
Задача 2. В одномерном массиве A(N) (N ≤ 100) найти все четные элементы (ограничение условия).
Задача 3. В одномерном массиве A(N) (N ≤ 100) найти все четные положительные элементы (получена из предыдущей добавлением в условие).
Задача 4. В одномерном массиве A(N) (N≤100) найти все четные положительные элементы с индексами, кратными 3 (получена из предыдущей добавлением в условие).
Задача 5. В одномерном массиве A(N) (N ≤ 100) увеличить в два раза все четные положительные элементы (получена из задачи 4 путем изменения требования).
Задача 6. В одномерном массиве A(N) (N ≤ 100) возвести в квадрат все элементы, попадающие в интервал от -2 до 5 (получена из задачи 4 путем изменения требования).
В процессе апробации разработанных нами систем задач была создана методика подготовки к олимпиадам по информатике на основе использования систем задач, которая построена с учетом специфик целевого (система целей - обучение с использованием системы задач), содержательного (дидактические единицы содержания, требующие отображения в системах задач) и процессуального (информации, определение видов, форм и способов подачи учебной информации в соответствии с особенностями методического стиля педагога) компонентов методической системы учителя информатики, реализуемых в системах задач.
Данная методика используется преподавателями Лицея при факультете довузовской подготовки ФГБОУ ВПО «Волгоградский государственный технический университет» при подготовке школьников к олимпиадам по информатике с 2003 и по настоящее время.
Многолетние наблюдения за школьниками, участвующими в процессе подготовки к олимпиадам по информатике показали, что использование систем задач, кроме подготовки к олимпиадам, еще влияет на развитие одаренности . Поэтому в процессе педагогического исследования нами была разработана трехстадийная модель формирования одаренности в условиях подготовки школьников к олимпиадам по информатике, при построении которой мы ориентировались на то, что на каждой из стадий подготовки к олимпиадам учащиеся непосредственно участвуют в процессе формирования своей одаренности. Первая стадия является стадией самоопределения (самоидентификации одаренности) школьника, вторая - стадией определения границ своей одаренности, на третьей стадии происходит осознание, каким образом можно самостоятельно участвовать в процессе формирования своей одаренности. Данная модель является теоретической основой для проведения нами дальнейшей методической работы.
Эта стадийная модель внесла коррективы в содержательный и процессуальный компоненты разработанной нами методики подготовки к олимпиадам по информатике на основе использования систем задач. Сконструированные системы задач становятся основой для разработки индивидуальных образовательных траекторий для каждого ученика, что приводит к формированию одаренности учащихся путем развития способностей учащихся и реализации их личностного творческого потенциала. Методика стала стадийной, обеспечивая таким образом разноуровневость индивидуальных образовательных траекторий и трехэтапность процесса подготовки к олимпиадам по информатике и формирования одаренности при использовании комплексов систем задач и сочетании очной и дистанционной форм обучения.
Рецензенты:
Смыковская Т.К., д.п.н., профессор кафедры теории и методики обучения математике и информатике, ФГОУ ВПО «Волгоградский социально-педагогический университет», г. Волгоград;
Петрова Т.М., д.п.н., профессор кафедры теории и методики обучения математике и информатике, ФГОУ ВПО «Волгоградский социально-педагогический университет», г. Волгоград.
Работа поступила в редакцию 08.10.2013.
Библиографическая ссылка
Павлова Е.С. МЕТОДИКА ФОРМИРОВАНИЯ ОДАРЕННОСТИ ПРИ ПОДГОТОВКЕ К ОЛИМПИАДАМ ПО ИНФОРМАТИКЕ // Фундаментальные исследования. – 2013. – № 10-6. – С. 1360-1362;URL: http://fundamental-research.ru/ru/article/view?id=32547 (дата обращения: 05.01.2020). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
Методика подготовки к олимпиадам по информатике
Актуальность темы
В связи с актуализацией и активизацией олимпиадного движения все острее встает проблема подготовки учащихся к участию в олимпиадах. Подготовка «ученика-олимпиадника» начинается с подготовки учителя.
Проблемы, встающие перед учителем:
1. Изучение новых форм проведения олимпиад.
2. Знание алгоритмов решения олимпиадных задач.
3. Наличие самих задач.
4. Знание языков программирования.
5. Время на изучение, отладку и проверку задач.
6. Обучение учащихся правильной организации деятельности на олимпиаде.
Несмотря на то, что круг задач рассматриваемых на олимпиаде по программированию ограничен, решение задачи может быть сложным не только для ученика, но и для учителя, так как некоторые задачи требуют знания высшей математики. Проверка решений и подготовка тестов обычно занимает много времени.
Вот некоторые особенности подготовки школьников к олимпиадному программированию :
· В школьной программе нет такого предмета «программирование» и даже такого раздела. То есть, обучаемый должен иметь собственную, довольно сильную мотивацию.
· Действует ограничение, что при решении задач желательно использовать только один из языков программирования (СИ или ПАСКАЛЬ).
· Постоянные тренировки идут почти на спортивном уровне.
· Большие затраты времени, длительность олимпиады с разбором часто превышает 6 часов.
· Алгоритмы и формулы, применяемые при решении большинства задач, изучаются только в ВУЗах.
Разумеется, подготовка более высокого уровня необходима и учителям для работы с одаренными учащимися, участвующими в олимпиадах по программированию:
· Возможно второе образование, профильный ВУЗ по программированию.
· ИПК учителей, курсы по изучению языков программирования, по олимпиадному программированию.
· Самостоятельная подготовка с использованием материалов из дополнительных источников.
Но даже хорошее знание языка программирования не дает стопроцентную гарантию, что учащийся победит даже на школьной или районной олимпиаде.
Педагогическая идея
Основным стимулом к участию в олимпиадах для школьника является мотивация. Это не только возможность улучшить свою отметку, но и возможность показать знания и эрудицию по решаемой проблеме, свои организаторские способности, дать возможность «заработать отметку» другим учащимся (даже не участвующим в олимпиаде).
Стремление школьника к лидерству, демонстрации собственных достижений является одним из основополагающих условий для участия в олимпиадном движении. Разумеется, при такой мотивации желающих работать достаточно, но в ходе работы происходит частичная ротация и это неизбежно при современной загруженности школьников. В основном остаются трудолюбивые дети, те учащиеся, которые не боятся поражений и ставят перед собой конкретные цели.
Одними из основных направляющих сил участия учащегося в олимпиадах по программированию являются желание и заинтересованность учителя, а также помощь, терпение и доверие родителей.
В 1964 г. В. Врум предложил «теорию ожиданий». Он считал, что стимул к эффективному и качественному труду зависит от сочетания трех факторов - ожиданий человека:
1. Ожидание того, что усилия приведут к желаемому результату.
2. Ожидание того, что результаты повлекут за собой вознаграждение.
3. Ожидание того, что вознаграждение будет иметь достаточную ценность.
Чем больше вера человека, что все эти ожидания оправдаются, тем более сильным будет стимул к деятельности. Если немного изменить формулировки В. Врума в образовательном контексте, то вот что получится:
· Теория ожидания указывает на то, что должны делать учителя, чтобы стимулы к учебе у учеников были сильными:
o Учить учеников получать требуемые результаты и создавать для этого все необходимые условия;
o Устанавливать непосредственную связь между результатами труда и оценкой учеников;
o Изучать потребности учеников, чтобы знать, какие вознаграждения имеют для них ценности.
· Исходя из этого, механизмы мотивации и основные факторы эффективности стимулирования можно выразить как:
o Знание учителями потребностей, интересов, нужд учеников.
o Установление справедливой непосредственной связи между результатами и вознаграждением.
o Безотлагательность вознаграждения.
o Степень удовлетворения ожиданий.
Для подготовки к олимпиадам по программированию можно применить методику с использованием системы тестирования «NSUTS» , разработанной на базе НГУ, которая позволяет оперативно решать многие из этих пунктов.
Технология использования системы « NSUTS »
Система находится по адресу https://olympic. *****/nsuts-test/nsuts_new_login. cgi . При переходе по этой ссылке попадаем на страницу авторизации , где, введя свой логин и пароль, можно войти в систему.
https://pandia.ru/text/78/392/images/image002_97.jpg" width="623" height="258 src=">
В данном случае выберем, например, Школьные тренировки , после чего вы попадёте на страницу «Страница регистрации на Школьные тренировки », где регистрация проста и понятна. Только нужно учесть, что данные, вводимые вами, должны быть достоверными.
https://pandia.ru/text/78/392/images/image004_80.jpg" width="623" height="306">
На вкладке «Help » можно прочесть краткую инструкцию по работе в системе. Рассмотрим содержимое этой страницы.
Система тестирования NSUTS. Очень краткое Описание.
Вы находитесь в автоматической системе тестирования NSUTS для проведения и проверки олимпиад по программированию. В верхней части экрана отображается текущий раздел. В правом верхнем углу - название текущей олимпиады, название вашей команды и кнопка завершения работы с системой - «Выйти ».
В разделе «Тур » вы можете выбрать текущий тур олимпиады.
В разделе «Новости » вы можете прочитать объявления и комментарии от жюри и оргкомитета олимпиады. А так же узнать время начала и конца олимпиады. После начала олимпиады на этой странице появляются ссылки на условия задач.
В разделе «Сдать » осуществляется отправка задач на тестирование. Для того чтобы отправить задачу на тестирование, укажите язык, на котором написано решение, и номер задачи. Вставьте текст решения в поле ввода и нажмите кнопку «Отправить ». Или выберите файл, пользуясь строкой выбора файла, а затем нажмите кнопку «Отправить ». Ваше решение появится в списке отправленных задач в секции «Результаты ».
Ваши решения должны считывать входную информацию из файла input. txt и выдавать результат в файл output. txt . Запрещено читать из стандартного потока ввода, писать в стандартный поток вывода, стандартный поток ошибок. Программа участника не должна открывать, читать и модифицировать файлы, кроме input. txt и output. txt или иных, указанных в условии задачи. Доступ к файловой системе и другим ресурсам, кроме перечисленных в формулировке задачи, запрещен. Нарушение этого требования может быть основанием для дисквалификации команды. Ограничение на размер исходного кода - 100 килобайт. Формат вывода должен точно соответствовать требованиям, описанным в условии задачи.
Участник может использовать любой компилятор из перечисленных в разделе «Сдать ».
Опции компиляции:
Visual C++ 6.0 | |
Visual C++ 2005 | cl. exe /EHsc /Ox task. cpp /link /STACK: |
MinGW 5.1.4 (GCC 3.4.5) | c++.exe - Wall - Wl,--stack= - O2 task. cpp |
Freepascal 2.2.0 | ppc386.exe - O2 - Cs task. pas |
Java 1.6.0_07 | javac. exe Task. java |
Запуск Java | java - Xmx480m - Xss32m - Djava. security. manager - Duser. language=en_US Task |
Borland Delphi 2006 |
В секции «Результаты » вы можете просмотреть статус тестирования и результаты тестирования отправленных вами задач. В строке «Время » указано время на момент сдачи решения, язык программирования который вы указали, сдавая это решение. Ссылка «V iew source » покажет текст сданного решения.
В строке «Результат » отображается результат тестирования:
Queued - решение стоит в очереди на тестирование.
Testing... - тестируется прямо в этот момент.
Source code limit exceeded - превышено ограничение на исходный код программы.
Compile Error - не удалось скомпилировать (причина указывается).
Когда решение протестировано, статус принимает одно из следующих значений:
ACCEPTED! - решение засчитано как верное.
Wrong Answer - неверный ответ на тесте.
Time limit exceeded - решение не уложилось в отведенное процессорное время.
Timeout - решение не уложилось в отведенное время.
Run-time Error - решение вернуло код ошибки, отличный от нуля.
Memory limit exceeded - решение не уложилось в отведенное ограничение по памяти.
No output file - отсутствует файл output. txt.
Security violation - решение совершило действие запрещенное правилами.
При этом указывается номер теста, на котором произошла ошибка (для олимпиад ACM).
Краткое правило построения рейтинга для олимпиад ACM таково: из двух команд, та будет выше в рейтинге, у которой решено большее число задач; если число задач одинаково, то выше оказывается команда, имеющая меньшее штрафное время. Если число задач и штрафное время одинаково у нескольких команд, то эти команды занимают несколько подряд идущих мест.
Штрафное время - это сумма штрафного времени по всем задачам. Штрафное время для одной задачи равно 0, если задача не сдана. Если же задача сдана, то её штрафное время считается по формуле:
время_сдачи_правильного_решения + (количество_неудачных_попыток * 20).
Cекция «Вопросы и ответы » предназначена для общения с Жюри олимпиады. Вы можете задать жюри вопросы по условиям задач или указать на неточность формулировки задач.
Кроме того, если Жюри считает необходимым внести какие-либо изменения в условия задач, поправки будут опубликованы в этой секции либо в новостях.
Теперь, когда мы познакомились с основами работы в системе, рассмотрим, как можно получить задание для олимпиады .
На вкладке «Тур» выбираем необходимый нам тур по олимпиаде, например, «Подготовка к Всероссийской олимпиаде 2010.03.21 (Геометрия) » . После этого переходим на вкладку «Новости» и по ссылке «Условие тура» скачиваем файл формата MS Office Word, в котором находятся задачи, представленные к решению на данном туре.
Решив задачу, на вкладке «Сдать» отправляем её на проверку, выставив все необходимые параметры (язык, текст программы либо файл с программой). Результаты проверки можно узнать на вкладке «Результаты».
Основные классы задач, выдвигаемых на олимпиады по информатике
Для успешного выполнения не только олимпиадных, но и внутриурочных задач, требуется:
1. В совершенстве владеть языком и средой программирования (в нашем случае - это Free Pascal), уметь строить и воплощать с помощью этого языка различные алгоритмы.
2. Владеть необходимым математическим аппаратом.
3. Знать алгоритмы решения основных классов задач, их оптимизацию.
Задачи олимпиадного программирования охватывают очень большой спектр знаний, но наиболее часто встречаемые и вызывающие наибольшую сложность - это следующие:
1. Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
2. Графы, как множество объектов с множеством связей.
3. Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор».
4. Задачи динамического программирования.
Рассмотрим данные классы задач подробнее.
Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, которая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем «багаже» соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как «char», «integer», «real». На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с «машиной данных», которая управляет способом доступа к информации в вашей программе. Имеется четыре такие «машины»:
1. очередь;
3. связанный список;
4. двоичное дерево.
1) http://ru. wikipedia. org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85.
2) http://valera. *****/delphi/struct/ocher. html.
3) http://www. *****/informatika/pascal/struktury_dannyh.
4) Т. Кормен. Алгоритмы. Построение и анализ. 2-е изд. Стр.255
5) Задачи и решения http://*****/olimp/str_prb. php.
Графы, как множество объектов с множеством связей.
Граф – это абстрактный математический объект. Он состоит из вершин и ребер. Каждое ребро соединяет пару вершин. Если одну и ту же пару вершин соединяют несколько ребер, то эти ребра называются кратными. Ребро, соединяющее вершину с ней самой, называется петлей. По ребрам графа можно ходить, перемещаясь из одной вершины в другую. В зависимости от того, можно ли по ребру ходить в обе стороны, или только в одну, различают неориентированные и ориентированные графы соответственно. Ориентированные ребра называются дугами. Если у всех ребер графа есть вес (т. е. некоторое число, однозначно соответствующее данному ребру), то граф называется взвешенным. Вершины, соединенные ребром, называются соседними. Для неориентированного графа степень вершины – число входящих в нее ребер. Для ориентированного графа различают степень по входящим и степень по исходящим ребрам. Граф называется полным, если между любой парой различных вершин есть ребро.
Граф – объект абстрактный, и интерпретировать его мы можем по-разному, в зависимости от конкретой задачи. Рассмотрим пример. Пусть вершины графа - города, а ребра - дороги, их соединяющие. Если дороги имеют одностороннее движение, то граф ориентированный, иначе неориентированный. Если проезд по дорогам платный, то граф взвешенный.
На бумаге граф удобно представлять, изображая вершины точками, а ребра - линиями, соединяющими пары точек. Если граф ориентированный, на линиях нужно рисовать стрелочку, задающую направление; если граф взвешенный, то на каждом ребре необходимо еще надписывать число - вес ребра.
Есть несколько способов представления графа в памяти компьютера. Далее с теорией можно ознакомиться по ссылкам:
1. http://*****/sng/index. shtml
2. http://*****/sng/4/index. shtml
3. https://sites. /site/vzsitgnovosibirsk/distancionnye-kursy/distancionnyj-kurs-graf
4. http://book. *****/10/grap1021.htm
5. http://ru. wikipedia. org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2
6. Задачи и решения http://*****/olimp/gra_prb. php
Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор»
Вычислительная геометрия - это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольник и т. п. Результатом может быть либо ответ на какой-то вопрос (типа «пересекаются ли эти прямые»), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, содержащий заданные точки).
В «Информатике» № 14 была опубликована статья одного из авторов, посвященная задачам вычислительной геометрии в олимпиадах по информатике. В частности, там был сформулирован ряд элементарных подзадач, на которые опирается решение большинства задач вычислительной геометрии. Однако занятия даже с математически хорошо подготовленными учащимися старших классов показали, что решение таких подзадач вызывает у них большое затруднение. Задача либо ставит их в тупик, либо выбранный «лобовой» способ решения настолько сложен, что довести его до конца без ошибок учащиеся не могут. Анализ результатов решения «геометрических» задач на всероссийских олимпиадах по информатике приводит к тем же выводам. По ссылкам ниже вы сможете изучить подходы к решению геометрических задач на плоскости, которые позволяют достаточно быстро и максимально просто получать решения большинства элементарных подзадач.
1) http://*****/?page=lib_viewarticle&article_id=12.
2) http://*****/article. asp? id_sec=1&id_text=1332.
3) Задачи и решения http://*****/olimp/geo_prb. php
Задачи динамического программирования.
Многие олимпиадные задачи, а также задачи практического программирования, являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным.
К счастью, для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение. Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения. Такой метод называется динамическим программированием, еще его называют табличным методом. В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию. Иногда, вместо оптимизационной, тем же методом решается задача подсчета количества допустимых решений. В этом случае на каждом шаге вместо выбора оптимального решения производится суммирование решений подзадач меньшей размерности, причем они по формулировке не всегда полностью совпадают с исходной задачей (соответствующие примеры будут рассмотрены ниже). В обоих случаях найденное на текущем шаге решение обычно заносится в таблицу. Как правило, связь задач и подзадач формулируется в виде некоторого “принципа оптимальности” и выражается системой уравнений (рекуррентных соотношений).
Основы теории динамического программирования были заложены Р. Беллманом. Заметим, что слово программирование в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера.
Для решения задачи оптимизации, в которой требуется построить решение с максимальным или минимальным (оптимальным) значением некоторого параметра, алгоритм, основанный на динамическом программировании, можно сформулировать так:
1) выделить и описать подзадачи, через решение которых будет выражаться искомое решение,
2) выписать рекуррентные соотношения (уравнения), связывающие оптимальные значения параметра для подзадач,
3) вычислить оптимальное значение параметра для всех подзадач,
4) построить самое оптимальное решение, используя полученную информацию.
Если нас интересует только значение параметра, то шаг 4 в алгоритме не нужен (такая ситуация характерна, например, для задач подсчета количеств допустимых вариантов или некоторых конфигураций, в том числе и комбинаторных). Однако, в случае необходимости построения самого оптимального решения иногда приходится в процессе выполнения шага 3 алгоритма получать и хранить дополнительную информацию. Зачастую именно шаг 4 оказывается самым сложным при реализации подобных алгоритмов.
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) Задачи и решения http://*****/olimp/rec_prb. php
Разбор задач олимпиадного характера.
Методика подготовки к районному этапу Всероссийской олимпиады школьников по информатике.
Материалы мастер-класса (презентация)
на РМО учителей информатики.
учителя информатики и ИКТ
МОУ «Лицей №23»
Шуваловой Светланы Юрьевны.
В данной работе обобщены материалы, представленные мною на РМО учителей информатики в 2011, 2012 годах по итогам школьных этапов Всероссийской олимпиады школьников по информатике.
Число участников олимпиады школьников по программированию с каждым годом уменьшается, это связано с уменьшением доли часов по содержательной линии «Алгоритмизация и программирование» в учебной программе школьного курса информатики. Олимпиады предназначены выявлять наиболее одаренных в области информатики школьников, развивать их способности, повышать интерес к предмету. Они дают возможность школьникам получить раннюю профориентацию, что способствует становлению в дальнейшем российских специалистов в области информатики, вычислительной техники и программирования. Но хорошее знание школьного курса информатики не гарантирует успешного выступления на олимпиадах, необходимо заниматься с учащимися во внеурочное время.
Слайд 1.
Цель олимпиады по информатике - способствовать поиску наиболее одаренных школьников .
Важной особенностью задач, используемых при проведении школьного и муниципального этапов, является ориентация их на проверку развития у учащихся теоретического мышления, логики, а также творческих способностей и интуиции.
Задачи школьного этапа олимпиады должны быть такой сложности, чтобы не отпугнуть учащихся, а дать им возможность продемонстрировать свои лучшие качества.
Слайд 2.
Основные критерии отбора олимпиадных задач для проведения школьного и муниципального этапов Всероссийской олимпиады школьников по информатике:
- оригинальная формулировка задачи (или идея ее решения);
- в тексте условия задачи не должны встречаться термины и понятия, выходящие за пределы изучаемых в рамках базового учебного плана предметов;
- задача должна быть однозначно определена;
- задача не должна требовать для своего решения специальных знаний;
- формулировка задачи должна предполагать наличие этапа формализации при ее решении;
- задача должна быть разумной сложности и трудоемкости.
Слайд 3.
Олимпиадные задачи для школьного и муниципального этапов олимпиады по информатике отличаются тематическим разнообразием.
Из опыта олимпиад можно выделить наиболее часто встречающиеся разделы информатики, к которым с можно отнести тематику задач:
- комбинаторика;
- сортировка и поиск;
- обработка последовательностей;
- алгоритмы на графах;
- элементы вычислительной геометрии.
- перебор вариантов и методы его сокращения;
- динамическое программирование.
Слайд 4.
Этапы решения олимпиадных задач:
- Разбор условия задачи.
- Формализация условия задачи.
- Разработка алгоритма решения задачи.
- Программная реализация алгоритма.
- Отладка и тестирование программы.
- Отправка решения на проверку.
Слайд 5.
Важно отметить, что текст задачи нужно всегда внимательно читать от начала и до конца, поскольку ключевое условие может быть спрятано, например, в формате входных или выходных данных, а также в приведенных примерах файлов входных и выходных данных.
При разработке программы следует также обратить особое внимание на описание формата входных и выходных данных , приведенное в условии задачи. Имена входного и выходного файлов также описаны в условии задачи, и неправильное их написание в программе считается ошибкой.
Необходимо помнить при написании программы, - это сохранение редактируемых файлов во время тура.
Полученная программа должна соответствовать заданной размерности входных данных и удовлетворять ограничениям на память и время работы , заданные в условии задачи.
Слайд 6.
Часто встречающиеся ошибки:
- Не соответствует формат ввода-вывода данных условию задачи
- Рассмотрены не все возможные случаи
- Не правильно задан тип данных (размерность)
- Потеря редактируемых файлов во время тура
Слайд 7.
Минимальная база знаний для олимпиады по информатике.
Язык программирования:
- базовые алгоритмические конструкции,
- стандартные математические функции,
- процедуры и функции для обработки строковых переменных,
- процедуры и функции для работы с массивами.
Типовые алгоритмы.
Слайд 8.
Задачи на олимпиадах по информатике не всегда соответствуют «Стандарту основного и среднего (полного) общего образования по информатике и ИКТ». Более того, в качестве решения этих задач на олимпиаде требуется предъявить отлаженные программы, написанные на языке программирования высокого уровня, а не описания алгоритмов.
Поэтому по результатам олимпиад не корректно оценивать работу конкретного учителя информатики, так как программа школьного курса информатики не может охватить все темы, изучение которых могло бы улучшить результаты выступления школьников на олимпиадах.
Слайд 9.
Интернет-ресурсы для подготовки к олимпиадам по информатике:
http://algolist.manual.ru/
Разбор задач школьного тура олимпиады 2011 года.
Задача №1 «Запись музыки» (15 баллов)
Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.
Алгоритм решения:
Использование расчетной формулы и условного оператора
Задача №2 «Кодовый замок сейфа» (20 баллов)
Из 10 букв нужно набрать 3. Повторение букв допустимо. Подсчитать количество возможных комбинаций кодов.
Алгоритм решения:
Задача на комбинаторику. Для решения необходимо применить типовой алгоритм формирования групп размещения с повторениями. Используются вложенные циклы.
Задача №3 «Прямоугольник» (30 баллов)
На плоскости изображено N прямоугольников. Каждый прямоугольник задан координатами левой нижней и правой верхней вершин. Определить, имеют ли прямоугольники общую площадь
Алгоритм решения:
Если максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то общая площадь есть.
Используется типовой алгоритм нахождения максимального (минимального) элемента массива.
Задача №4 «Магический квадрат» (35 баллов)
В квадрате размером 3x3 клетки поставить числа 1, 2, ... ,9 так, чтобы суммы чисел, стоящих в каждом ряду, столбце, в каждой диагонали, были равны.
Алгоритм решения. Задача на способ заполнения двумерного массива.
(индийский способ):
- В середине верхней строки ставим 1 , в последней строке соседнего справа столбца 2 .
- Следующие числа ставят в диагональном направлении.
- Дойдя до правого края квадрата, переходят к крайней левой клетке ближайшей вышележащей строки.
- Дойдя до верхнего края квадрата, переходят к самой нижней клетке соседнего справа столбика. Примечание. Дойдя до правой верхней угловой клетки, переходят к левой нижней.
- Дойдя до уже занятой клетки, переходят к клетке, лежащей непосредственно под последней заполненной клеткой.
- Если последняя заполненная клетка находится в нижнем ряду квадрата, переходят к самой верхней клетке в том же столбце.
Разбор задач школьного тура олимпиады 2012 года.
Задача 1.
Напечатать все трехзначные десятичные числа, сумма цифр которых равна данному числу.
Алгоритм решения:
Один из вариантов решения перебором:
var a,b,c,n,k:integer;
begin
write("n="); readln (n);
for a:=1 to 9 do
For b:=0 to 9 do
For c:=0 to 9 do
If a+b+c=n then
begin
writeln (a,b,c," ");
k:=k+1;
end;
Writeln;
Writeln ("k=",k) ;
Writeln;
end.
Второй вариант решения перебором:
Var a,b,c,n,k,m: integer;
begin
write("n="); readln(n);
for m:=100 to 999 do
begin
c:=m mod 10;
b:= m div 10 mod 10;
a:= m div 100;
if a+b+c=n then
begin
write(m:5);
k:=k+1;
end;
end;
writeln("k=",k)
end.
Задача 2. «Малыш и Карлсон».
Малыш и Карлсон живут в прямоугольной комнате размером А х В . Как им посчитать, сколько понадобится квадратных ковриков со стороной С , чтобы полностью покрыть пол комнаты? (Малыш и Карлсон не умеют ни делить, ни умножать.) Напишите программу для решения этой задачи.
Алгоритм решения:
Во внешнем цикле по одной из сторон комнаты (while p) резервируем место для ряда (р:=р+с ), затем во внутреннем цикле по другой стороне (while m) проверяем, сколькими ковриками можно закрыть ряд, оператор m:=m+с резервирует место для коврика, а оператор kovrik:=kovrik+1 подсчитывает общее количество уложенных ковриков.
var a, b, с, kovrik, m, p: integer;
begin
readln(a, b, с);
kovrik:= 0;
p:= 0;
while p
begin
p:= p + c;
m:= 0;
while m
begin
m:= m + c;
kovrik:= kovrik + 1
end;
writeln (kovrik)
end.
Задача 3. «Бактерии».
Колония состояла из n бактерий (не более 30000). В нее попал вирус, который в первую минуту уничтожил одну бактерию, а затем разделился на два новых вируса. Одновременно каждая из оставшихся бактерий тоже разделилась на две новые. В следующую минуту возникшие два вируса уничтожили две бактерии, а затем все вирусы и бактерии снова разделились и так далее. Будет ли эта колония жить бесконечно долго или вымрет?
Ваша программа должна:
- Запросить число бактерий n ;
- Выяснить и сообщить: через сколько суток, часов и минут колония бактерий прекратит свое существование или выдать сообщение, что колония вечна.
Пример ответа: Для n=A. Ответ – B суток C часов D минут (где A, B, C, D – числовые значения).
Алгоритм решения:
Программа на языке программирования Паскаль.
Var a, b, c: shortint;
t, n, v: longint;
begin
Write (‘Начальная численность колонии -"); readln (n);
v:=1;
while n>0 do
Begin
t:= t + 1; { минуты}
n:= (n - v) * 2; { бактерии}
v:= v * 2; { вирусы}
end;
a:= t div 1440;
b:= (t – a * 1440) div 60;
c:= t – a - b;
Write ("Колония прекратит существование через ",a, " суток ", b, " часов ", c , " минут");
end.
Задача 4.
Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты (рис.1). Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?
Алгоритм решения:
1 способ.
Для решения этой задачи нам нужны функции МАХ и MIN , для их определения используем подпрограммы-функции.
Введем:
- вспомогательные переменные X и Y (Y>=X) , соответствующие уменьшающимся сторонам прямоугольника;
- вспомогательную переменную D , которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как X:=MIN(D,X).
Организуем цикл, в котором сторона Y уменьшается каждый раз на MIN(D,X) до тех пор, пока не останется последний квадрат или Y не станет меньше X. В последнем случае переименовываем стороны оставшегося прямоугольника как Y:=MAX(D,X) и X:=MIN(D,X) и продолжаем цикл.
Программа на языке программирования Паскаль.
var a, b, d, k, x, y: integer;
function min (i, j: integer): integer;
begin
if i
else min:=j
end;
function max (i, j: integer): integer;
begin
if i
else max:=i
end;
begin
repeat
Writeln ("vvedite dva naturalnix chisla");
Readln (a, b);
until (a>0) and (b>0);
k:=1;
x:=min(a,b);
y:=max(a,b);
while x y do
begin
k:=k+1;
d:=y-x;
y:=max(d,x);
x:=min(d,x);
end;
Writeln ("iskomoe chislo kvadratov:", k)
end.
2 способ.
Задачу можно решить с помощью стандартных функций PASCAL : Y DIV X и Y MOD X, используя алгоритм Евклида.
Алгоритм решения:
Организуем цикл, в котором формируем остатки от деления r 0 , r 1 , r 2 ,..., r n , r n+1 до тех пор, пока один из этих остатков не станет равен нулю r n+i =0 . Таким образом, мы строим функцию порождения остатка от деления r n+i = r n mod r n-i , где r 0 = А и r i =В . Для той же самой системы остатков мы можем посчитать, сколько раз нацело укладывается остаток r n-i в r n .
{алгоритм Евклида}
var А, В, R0, R, R1, K: integer;
begin
repeat
Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО А = ");
Readln (А);
Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО В
Readln (В);
until (В > 0) and (А > 0) and (А >=В);
R0:= А;
R1:= В;
К:= R0 div R1;
while R0 mod R1 0 do
begin
R:= R0 mod R1;
R0:= R1;
R1:= R;
К:= К + R0 div R1
end;
Writeln ("ИСКОМОЕ ЧИСЛО КВАДРАТОВ К = ",К);
Муниципальное бюджетное общеобразовательное учреждение
основная общеобразовательная школа №2 р.п. Солнечный
Солнечного муниципального района Хабаровского края
Рассмотрено: Утверждаю:
Руководитель МО директор МБОУ ООШ № 2
________(Л.Т.Климова) р.п. Солнечный
Протокол № _1_ от 30 .08.2015г _________(О.В.Зверева)
приказ от31.08.2015 № 121.
ПРОГРАММА
индивидуальной подготовки
к муниципальному этапу Всероссийской олимпиады школьников
по предмету «Информатика и ИКТ»
для ученицы 7 «А» класса
Составила:
Молчанова Светлана Николаевна,
учитель информатики, ВКК
2015– 2016 учебный год
п. Солнечный
Пояснительная записка:
Необходимость создания индивидуальной программы по информатики ученицы 7 класса обусловлена имеющимися результатами ученика в образовательной деятельности: отличная учёба, участия в конкурсах школьного уровня, олимпиадах, высокая познавательная активность, нестандартность мышления и т.д.
Изменения, которые происходят сегодня в обществе, коренным образом влияют на задачи школы. Приоритет ученика, формирование базовых компетентностей современного человека заставляют взглянуть на проблему развития одаренности школьников. Ведь одаренность – это не только данные природой качества и способности, это, прежде всего, целенаправленная работа по развитию природного дара.
Информатика в нашей школе изучается с 7 по 9 классы 1 час в неделю на базовом уровне, что явно недостаточно для подготовки к олимпиаде по информатике. Так как олимпиада по информатике является, по сути, своей олимпиадой по программированию. Решение олимпиадных задач представляет собой самостоятельный учебный раздел с обширными теоретическими и практическими частями.
Решения олимпиадных задач, базируются на определенных алгоритмах, широко известных в математике и информатике. И чтобы успешно решать олимпиадные задачи, необходимо, прежде всего, освоить эти алгоритмы, уметь видеть их, применить в предлагаемых заданиях, а уж если не знаешь, то суметь их придумать, изобрести. Но знакомство с этими алгоритмами чаще всего происходит только в вузе, и это вполне объяснимо, так как освоение этих алгоритмов требует знания некоторых разделов математики.
Данная образовательная программа направлена на подготовку учащихся к участию в муниципальном этапе Всероссийской олимпиады школьников. Изучение данной программы позволит учащимся более глубоко изучить данный предмет, расширить кругозор, научиться применять полученные знания для решения задач.
Цель обучение, развитие, воспитание и поддержка ученика при создание условий для оптимального развития ученика выработки у учащихся навыков быстрого решения задач по программированию в нестандартной постановке, типичных для олимпиад.
Задачи программы:
на этапе входной диагностики выявить уровень творческих и индивидуальных возможностей учащихся;
определить и использовать при организации образовательного процесса методы и приемы, способствующие развитию возможностей ученика;
организовать мероприятия для повышения социального статуса ученика;
обучить учащихся реализации как стандартных, так нестандартных алгоритмов;
развивать у учащихся навыки решения олимпиадных задач;
привить учащимся навыки исследовательской работы;
расширение кругозора учащихся и совместно с родителями поддерживать ученика в реализации его интересов в школе и семье;
развитие рефлексивных умений.
Данная программа отличается от существующих школьных программ более углубленным изучением материала.
Образовательная направленность, в рамках которой реализуется программа - социально-педагогическая. Возраст обучающихся школьников - 7 класс основной общеобразовательной школы. Срок реализации программы составляет 1 месяц.
Ожидаемый результат: готовность учащегося к участию в муниципальном этапе Всероссийской олимпиады школьников по информатике.
Используемая литература:
Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. - М. : БИНОМ. Лаб. знаний,2007
Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. - М. : БИНОМ. Лаб. знаний,2009
Программирование в алгоритмах: учебное пособие / С.М.Окулов. - М. : БИНОМ. Лаб. знаний, 2004. - 341, с.
Задачник по программированию / А.Г. Юркин. – СПб.: Питер, 2002. – 192 с.
http://olymp.ifmo.ru/rus/11-12/inf-it/
Интернет Олимпиады для школьников 7-11 классов.
http://www.olympiads.ru
Олимпиадная информатика. События, задачи, тесты, решения, комментарии.
http://olympiads.win.tue.nl/ioi/
Архивы всех международных олимпиад школьников по информатике.
Карта достижений Фиц Маргариты:
| Учебный год | Уровень участия в олимпиадах | Результат |
| Школьный этап | ||
| Школьный этап | Участник |
|
| Школьный этап | Победитель |
График занятий :
| Тема | Изучаемые вопросы |
|
| Целочисленная арифметика | 1.Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 2. Определение простоты числа. 3. Нахождение всех простых чисел из промежутка (a,b). 4. Разложение данного натурального числа на простые множители. 5. Дано разложение данного натурального числа на простые множители. Найти все делители этого числа. 6. Нахождение всех делителей натурального числа. 7. Нахождение цифрового корня натурального числа. 8. Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 9. Длинная арифметика: a) Считывание длинного числа из файла. b) Запись длинного числа в файл. c) Сложение двух длинных чисел d) Умножение длинного числа на короткое в системе счисления с основанием 1000. e) Умножение длинного числа на длинное. f) Деление длинного на короткое g) Вычисление n! и степени an при маленьких и больших значениях a и n, рекурсивная и нерекурсивная реализация. h) Индийский алгоритм вычисления an i) Дано натуральное число N. Найти последнюю ненулевую цифру суммы a1+a2+…+ak, где N=p1a1*p2a2*…*pkak. j) Дано натуральное число N. Найти последнюю ненулевую цифру числа N! k) Даны натуральные числа N и M. Найти последнюю ненулевую цифру числа сочетаний C из N по M. 10) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M. 1 11) Найти все натуральные числа, не превосходящие данного натурального N, десятичная запись которых есть строго убывающая или строго возрастающая числовая последовательность. (длинная арифметика). |
|
| Алгоритмы над целыми числами |
||
| Одномерные массивы | 1. Объявление и использование массивов. 2. Создание массивов:.вручную, по формуле, генератором случайных чисел, чтение из файла 3. Виды сортировок. Внешняя и внутренняя сортировка 4. Сортировка выбором. 5. Сортировка "пузырьком". 6. Сортировка Шелла. 7. Сортировка слиянием. 8. Внешняя сортировка слиянием. 9. Кучи. Сортировка с помощью кучи. 10. Сортировка подсчётом. 11. Хэширующая сортировка. 12. Цифровая сортировка 13. Сквозной поиск элемента в массиве. 14. Бинарный поиск элемента в массиве. 15. Извлечение корня n-ой степени из данного натурального числа. 16. Вычисление значения многочлена по схеме Горнера. |
|
| Двумерные массивы | Создание двумерных массивов. Задачи на двумерные массивы: 1 Нахождение максимального и минимального элементов массива. 2 Сортировка массива по возрастанию и убыванию в строках и столбцах. 3 Поменять местами первую и последнюю строки (столбцы). 4 Отобразить массив симметрично относительно горизонтальной оси. 5 Отобразить массив симметрично относительно вертикальной оси. 6 Отобразить массив n*n симметрично относительно главной диагонали 7 Отобразить массив n*n симметрично относительно побочной диагонали 8 Повернуть массив n*n против часовой стрелки на 90 градусов. 9 На шахматной доске стоит слон и еще несколько фигур. Сколько клеток контролирует слон? |
|
| Рекурсия. Комбинаторные объекты | 1. Понятие "комбинаторных" алгоритмов. 2. Получение комбинаторных объектов. 3. Задачи: Сгенерировать все последовательности длины n из чисел от 1 до k. Сгенерировать все подмножества n-элементного множества. Сгенерировать все перестановки чисел от 1 до N. Сгенерировать все k-элементные подмножества n-элементного множества. Сгенерировать все представления числа N в виде суммы натуральных чисел. Код Грея и сходные задачи. Генерация перестановок методом транспозиции соседних элементов. Числа Каталана. Расстановка скобок. |
|
| Сортировка |
||
| Переборные задачи |
||
| Геометрические задачи | 1. Логические функции сравнения вещественных чисел. 2. Площадь ориентированного треугольника (многоугольника). 3. Уравнение прямой проходящей через две точки 4. Общего вида ax+by+c=0 5. Каноническое (x-x1)/(x2-x1)=(y-y1)/(y2-y1) 6. параметрическое x:=x1+t(x2-x1); 7. Уравнение прямой перпендикулярной данной ax+by+c=0 и проходящей через данную точку (x0,y0). 8. Длина отрезка 9. Функция принадлежности точки отрезку |
|
| Численные методы | 1. Элементарная структура данных - запись. Линейный список. 2. Специальные структуры данных: стек, очередь, дек. 3. Деревья. Упорядоченные деревья. 4. Обходы деревьев. 5. Двоичные деревья, деревья поиска. 6. Обходы двоичных деревьев. 7. Поиск элемента в дереве поиска. 8. Добавление/удаление элемента. 9. Характеристики кучи. 1. Способы представления графа. 2. Обход в глубину. 3. Обход в ширину. 4. Кратчайшие пути. 1 Алгоритм Форда-Беллмана. 2 Алгортим Флойда. 3 Алгоритм Дейкстры 5. Поиск Эйлерова цикла 6. Поиск Гамильтонова цикла 7. Поиск компонент сильной связности 8. Поиск мостов 9. Поиск точек сочленения 10. Поиск максимального потока 11. Топологическая сортировка. |
|
| Статистическое моделирование |
||
| Динамическое программирование |
||
| Графы и деревья |
||
| Текстовые преобразования | 1.Процедуры и функции обработки текста на Паскале 2. Функции eof и eoln. 3. Функции seekeof и seekeoln. 4. Посимвольная обработка текста. 5. Отличие процедур read и readln. 5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура. 7. Использование хэш-функции для поиска произвольной подстроки в строке. 8. Рекурсивный синтаксический анализ скобочных выражений. Динамическое программирование Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов. |
|
| Решение олимпиадных задач | 1. Перебор и его значение в программировании. 2. Методы оптимизации перебора. 3. Задача о расстановке ферзей. 4. Задача об обходе конём шахматной доски. 5. Задача комивояжора. |
|
| Решение олимпиадных задач |
Итак, если Вы начинающий учитель информатики (а может и со стажем), желающий попытаться подготовить своих учеников к районной олимпиаде по информатике - эта страница для Вас.
В этом разделе будет размещаться информация, которая поможет Вам сделать первые шаги, вместе с автором сайта, на пути подготовки школьников к районным олимпиадам по информатике. Почему не к республиканским? Да потому, что помочь в этом, на данный момент, я не могу.
Решение попробовать подготовить учащихся 9-11 классов к районной олимпиаде по информатике, я принял сразу после того, как стал учителем информатики (4 года назад). Ознакомившись с заданиями за прошлые годы, я понял, что не могу решить ни одного из них. На этом можно было бы и остановиться, но я решил все-таки попробовать.
Что имеется на данный момент? С одной стороны начинающий учитель информатики, с другой стороны учащиеся знакомые лишь с основами программирования. Но, есть главное - обоюдное желание учиться.
Как вы понимаете, хорошее знание школьного курса информатики абсолютно не гарантирует успешного выступления на олимпиадах. Соответственно, заниматься с учащимися необходимо во внеурочное время. Лично мне не пришлось долго убеждать директора школы в необходимости организации кружка по программированию.
Что касается домашних компьютеров, то ситуация улучшается год от года. Однако, во многих сельских школах нашего района, у подавляющего большинства учащихся нет домашних компьютеров. Это звучит дико в 2009 году, но таковы реалии сельской жизни. В такой ситуации приходиться заниматься в школьном кабинете информатики.
Для начала рекомендую приобрести несколько хороших книг, я их размещаю в порядка возрастания сложности материала. Если книг нет в книжных магазинах, то можно заказать книги пройдя по прямым ссылкам расположенным ниже. Ссылки ведут в интернет-магазин books.ru , в котором я неоднократно заказывал книги для себя. Нареканий по качеству обслуживания у меня нет. Срок доставки книг составляет 10-14 дней.
Программирование на Pascal.Автор Сэм Аболрус. Если вы решили преподавать в школе язык программирования Pascal, но программирование ваша "ахиллесова пята", то эта книга для вас. Оригинальное название книги в переводе с английского - "Изучаем Паскаль за три дня". Действительно, освоить азы программирования на Паскале, при помощи это книги можно за пару дней. Автор работает программистом в корпорации Майкрософт. Настоятельно рекомендую ее приобрести. Моя оценка этой книги 5(отлично). |
Основы программированияОкулов С. Это книга, которую необходимо иметь каждому, кто решил научиться решать олимпиадные задачи по информатике. Пожалуй, это лучшая книга, которая мне попадалась по этой тематике. Повествование начинается от изучения среды программирования Turbo Pascal , а заканчивается решением задач на графах. Настоятельно рекомендую приобрести эту книгу. Моя оценка этой книги 5(отлично). |
Программирование в алгоритмахОчередной бестселлер Сергея Окулова. Кое-какая информация повторяется из книги расположенной выше, но в основном эта книга содержит уже более сложный материал чем предыдущая. Подробно рассмотрены такие темы как "Комбинаторное программирование", "Перебор и методы его сокращения", "Алгоритмы на графах" и т.д. В связи с тем, что ни одна олимпиада по информатике не обходится без сложных задач, к которым несомненно относятся и задачи на графах, то не плохо иметь эту книгу в арсенале. Моя оценка этой книги 5 (отлично). |
Олимпиадные задачи по программированию (+CD)Федор Меньшиков. Книга предназначена для пользователей уже знакомых с решением простых задач по программированию. Рассмотрены типовые задачи встречающиеся на различных олимпиадах для школьников и студентов. На прилагаемом к книге диске есть дополнительный материал, а также тестирующая система для компьютерной проверки решения задач. Моя оценка этой книги 5(отлично). /p> |
Кое-что полезное вы найдете и на этом сайте:
- Программирование на языке Turbo Pascal. Материалы к урокам. Довольно качественный материал, настоятельно рекомендую скачать в архиве ZIP(224Кб)
- Книга по решению олимпиадных задач на графах. Эту книгу, в электронном варианте, я нашел на сайте небезызвестного Михаила Густокашина (его статьи можно найти в журнале "Мир ПК" и газете "Информатика "). Пожалуй, этот материал один из лучших посвященных решению задач по программированию на графах. Привязка материала идет к языку Pascal . Рекомендую скачать эту книгу всем учителям информатики которые занимаются подготовкой школьников к олимпиадам по информатике. Скачать книгу Окулова в архиве RAR (724 Кб).
Видеоуроки по программированию
