Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Прошли те времена, когда булыжник был самым весомым политическим оружием, пробивающим не только человеческий затылок, но и действующий режим. На его ...полностью>>
'Литература'
Анисимов А.Л., Пак Б.Б. «Корейский вопрос» и русская дипломатия в период разграничения на Тумангане и возникновение русско-корейских отношений Взаи...полностью>>
'Пояснительная записка'
М.А.Ассанович, заведующий кафедрой медицинской психологии и психотерапии Учреждения образования «Гродненский государственный медицинский университет»...полностью>>
'Программа дисциплины'
Государственный университет – Высшая школа экономикиПрограмма дисциплины «Связи с общественностью» для специальности 080507.65 Менеджмент организации ...полностью>>

Программа курса «Олимпиадное программирование. Дискретная математика» для учащихся 9 10 классов Срок реализации: 3 недели (летняя компьютерная школа)

Главная > Программа курса
Сохрани ссылку в одной из сетей:

Государственное бюджетное образовательное учреждение

дополнительного образования детей

«Центр творческого развития и гуманитарного образования

для одаренных детей «Поиск»

ПРОГРАММА КУРСА

«Олимпиадное программирование. Дискретная математика»
108 часов

г. Ставрополь, 2012 г.

Одобрена методической службой Государственного бюджетного образовательного учреждения дополнительного образования детей «Центр творческого развития и гуманитарного образования для одаренных детей «Поиск»

Составлена в соответствии с требованиями к подготовке к Всероссийским олимпиадам по программированию

Председатель методического совета__________________________ Толстопятова О.А.

ПРОГРАММА КУРСА
«Олимпиадное программирование. Дискретная математика»

для учащихся 9 - 10 классов

Срок реализации: 3 недели (летняя компьютерная школа)

Автор: методист по информатике Круглов Е.Ю.

Статус документа

Программа курса «Олимпиадное программирование. Дискретная математика» составлена на основе образовательной программы по информатике Центра «Поиск».

Программа курса дополняет содержание отдельных модулей образовательной программы Центра, а именно «Язык программирования Pascal» и «Язык программирования С++», дает примерное распределение учебных часов по темам курса и возможную последовательность изучения тем с учетом логики учебного процесса, определяет минимальный набор теоретического материала и упражнений, необходимых для формирования компетентности учащихся в области дискретной математики применительно к олимпиадному программированию.

Программа курса является ориентиром для обучения в летней компьютерной школе учащихся 9-10 классов Ставропольского края, испытывающих определенный информационный голод в области олимпиадного программирования.

Структура документа

Программа курса «Олимпиадное программирование. Дискретная математика» включает следующие разделы: пояснительную записку; основное содержание с примерным распределением учебных часов по темам курса и возможной последовательностью изучения тем; требования к уровню подготовки ученика по данному курсу, включая мероприятия по контролю эффективности; систему оценки учебной деятельности и список используемой литературы.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Общая характеристика курса

Информатика – это наука о закономерностях протекания информационных процессов в системах различной природы, о методах, средствах и технологиях автоматизации информационных процессов.

До недавнего времени программирование составляло основной, а изначально – единственный раздел информатики. Совершенствование технологических и программных средств привело к снижению количества часов, отводимых для изучения темы «Алгоритмизация и программирование» в Программе среднего (полного) общего образования по информатике. А вопросы дискретной математики в школьной программе не рассматриваются вообще. Современные визуальные, а тем более – мультимедийные пользовательские среды являются теми конкурентами, которые вытесняют разработку программ из сферы интересов школьников. Для работы за компьютером, для поиска информации в сети пользователь имеет простые красивые инструменты, не требующие мыслительных усилий при применении.

Кроме того, в ряде школ вопросы алгоритмизации и программирования заменяются изучением офисных технологий, которые сводятся в большинстве своем к работе с офисными приложениями. Это вызвано появлением в школах современных компьютеров и специалистами, имеющими различные уровни профессиональной подготовки, различное базовое образование и опыт работы в школе.

Но в жизни человека алгоритмы встречаются повсеместно. Рассматривая алгоритмы как последовательность действий, можно выяснить причинно-следственные связи, и, таким образом, найти средства для достижения искомого результата. Часто именно алгоритм является методикой или технологией созидательного процесса. Многие языки программирования требуют однозначного описания последовательности операторов, то есть алгоритма. Между тем школьники, умеющие составить алгоритм и написать по нему программу, обычно значительно легче овладевают и пользовательскими навыками, так как понимают механизм управления компьютером. Они лучше успевают и по другим предметам, поскольку культура их мышления выше, а ассортимент методов выполнения различных работ богаче. В связи с этим представляется достаточно важным привить учащимся навыки алгоритмического мышления как можно более с раннего возраста.

Содержание курса «Олимпиадное программирование. Дискретная математика» способствует устойчивому и эффективному развитию системного и алгоритмического мышления учащихся.

Есть задача, проблема. Ученику требуется найти решение путем разработки соответствующей программы. Если решение известно, решались аналогичные задачи, то задействуется ассоциативная составляющая интеллекта, работа сводится к набору программы и ее отладке. Если решение неизвестно, то за постановкой задачи следует гипотеза и разработка первоначального варианта программы. Затем она подвергается исследованию, экспериментальной проверке с помощью системы тестов – сравнению ожидаемых результатов и полученных. Ученику мысленно следует предсказать, предвидеть результаты работы. Наступает фаза или экспериментального опровержения, или экспериментального подтверждения. Т.е. деятельность при разработке программ характеризуется контролируемостью, обоснованностью и целенаправленностью. Оценка своих действий – непременный атрибут программирования. На каждом шаге ученик имеет возможность осознать, насколько правильно принятое решение, насколько верен ход рассуждений, все ли факты учтены при принятии решения и т.д. Деятельность при программировании можно назвать направленной на получение желаемого результата. Она не просто активна, она сверхактивна, и мы видим возможность реализации концепции развивающего обучения в полном объеме.

Кроме того, исследователи в области психологии информационных технологий считают, что подлинно квалифицированная работа с компьютером способствует избав­лению ребенка от боязни допустить ошибку. Тем, кто обучался программированию, удается «избежать связи ошибки с неудачей». У учащихся появляется иное отношение к ошибкам: они перестают их бояться, поскольку, во-первых, в состоянии самостоятельно их устранить, и, во-вторых, могут установить их источник. Все это создает дополнительные стимулы для творческих поисков нешаблонных путей решения задач, что так необходимо при решении задач по программированию олимпиадного уровня.

Вышесказанное указывает на целесообразность рассмотрения этой темы в летней компьютерной школе, что даст возможность учащимся 8 – 11 классов, в том числе сельских школ, испытывающим информационный голод в области олимпиадного программирования, ознакомиться с его основами.

Цель программы – освоение и систематизация знаний, относящихся к построению и описанию объектов и процессов, позволяющих осуществить их компьютерное моделирование в соответствии с требованиями олимпиадного программирования Всероссийского уровня.

Задачи программы:

  • формирование целостного представления об олимпиадном программировании;

  • овладение умениями представлять исходную информацию в виде определенной структуры данных; выполнять последовательную структуризацию проблемы, определяя при этом особенности управления вычислительным процессом; описывать изменения отношений упорядоченности на множестве введенных структур, вплоть до получения конечного результата; оценивать реальность получения результата в обозримое время;

  • развитие настойчивости, гибкости; стиля мышления, адекватного требованиям современного информационного общества – структурного и алгоритмического;

  • воспитание умения планировать, готовности исправлять свои ошибки, культуры программирования;

  • приобретение опыта разработки алгоритмов и программ на языке программирования, удовлетворяющих заданному описанию сложной олимпиадной задачи; критического оценивания полученных результатов.

Место курса в учебном плане

Учебный план программы по информатике Центра «Поиск» в рамках летней компьютерной школы отводит 108 часов для изучения курса «Олимпиадное программирование. Дискретная математика» из расчета 6 учебных часов в день. Продолжительность курса – 3 недели.

Особенности программы

Курс представляет собой модуль, знакомящий учащихся с основами дискретной математики, требующий знания основ языков программирования Pascal или C.

Система оценки знаний учащихся осуществляется по международной шкале.

Материал курса предусматривает знакомство с материалом, который не включается в учебный план средних школ, предполагает повышенный уровень индивидуализации обучения как в вариативности содержания, так и в отношении разнообразных форм образовательного процесса, связанных с индивидуальными особенностями учащихся, стилями восприятия и интеллектуальной деятельности.

Общеучебные умения и навыки

Программа курса предусматривает формирование у учащихся общеучебных умений и навыков, универсальных способов деятельности и ключевых компетенций. В этом направлении приоритетными для учебного курса «Олимпиадное программирование. Дискретная математика» являются: основы и техника программирования и решения олимпиадных задач; реализация различных алгоритмов и умение применять их для решения вычислительных задач; алгоритмы быстрой сортировки; бинарный поиск; структуры данных (heap, очередь, список, стек); перебор и методы его сокращения; алгоритмы на графах (обход в ширину, глубину, кратчайшие пути, каркасы, топологическая сортировка); длинная арифметика; комбинаторика; динамическое программирование; алгоритмы вычислительной геометрии.

Результаты обучения

Обязательные результаты изучения курса «Олимпиадное программирование. Дискретная математика» приведены в разделе «Требования к уровню подготовки выпускника курса».

Рубрика «Знать/понимать» включает требования к учебному материалу, который усваивается и воспроизводится учащимися. Выпускники должны понимать смысл изучаемых понятий, принципов и закономерностей.

Рубрика «Уметь» включает требования, основанные на более сложных видах деятельности, в том числе творческой: создавать объекты, оперировать ими, оценивать числовые параметры процессов, приводить примеры практического использования полученных знаний, осуществлять самостоятельный поиск учебной информации.

Основным результатом обучения является пропаганда научных знаний и развитие у школьников интереса к научной деятельности, активизация работы спецкурсов, кружков, научных обществ учащихся, создание оптимальных условий для выявления одарённых и талантливых школьников, их дальнейшего интеллектуального роста и профессиональной ориентации.

По окончании курса учащийся получает Сертификат установленного Центром «Поиск» образца.

Основное содержание (108 часов)

Тема 1

Тема 2

Тема 3

Тема 4

Весь курс

Теоретический материал

8

12

4

10

34

Практический материал

6

12

4

10

32

Контроль

4

12

10

10

36

Итоговое тестирование

6

Итого:

18

36

18

30

108

Тема 1. Нестандартная обработка чисел

Этапы решения задач на компьютере. Сложность алгоритмов. Арифметика многоразрядных целых чисел. Алгоритмы реализации многоразрядных целых чисел. Динамическое программирование. Алгоритмы реализации динамического программирования. Практическая реализация задач нестандартной обработки чисел на высокоуровневых языках программирования.

Тема 2. Алгоритмы на графах

Свойства и типы графов. Графы. Представление графов в памяти компьютера. Поиск в графе. Поиск в глубину. Поиск в ширину. Деревья. Каркас минимального веса. Метод Краскала и Прима. Реализация алгоритмов Прима и Краскала. Бинарный поиск, слияние и сортировка. Кратчайшие пути. Алгоритмы Дейкстры и Флойда. Алгоритм Форда-Беллмана. Циклы. Гамильтонов и Эйлеров цикл. Обход графа. Раскраски. Реализация алгоритма минимальной раскраски вершин графа. Практическая реализация задач на высокоуровневых языках программирования.

Тема 3. Комбинаторные алгоритмы

Комбинаторика. Основные понятия и определения. Основные процедуры реализации комбинаторных объектов. Правильные скобочные последовательности. Практическая реализация комбинаторных задач на высокоуровневых языках программирования.

Тема 4. Алгоритмы вычислительной геометрии

Представление элементарных объектов, их пересечение, построение выпуклой оболочки, типичные ошибки. Алгоритм Джарвиса. Векторы. Операции над векторами. Скалярное и векторное произведение. Полярный угол. Взаимное расположение точек и фигур (принадлежность точки прямой, лучу, отрезку). Расстояние от точки до прямой. Пересечение двух отрезков. Уравнение прямой. Уравнение касательной к окружности, нахождение точек пересечения окружности и прямой, нахождение точек пересечения двух окружностей, уравнение биссектрисы угла). Многоугольники. Вычисление площади многоугольника. Определение выпуклости многоугольника. Определение нахождения точки внутри простого многоугольника. Построение выпуклой оболочки. Алгоритмы Грэхема и Джарвиса. Особые точки многоугольников и множеств N точек плоскости. Эффективный алгоритм нахождения ближайшей пары из N точек плоскости. Алгоритмы на строках (алгоритмы Бойера-Мура и Кнута-Мориса-Пратта). Перебор вариантов. Порождение подмножеств и последовательностей. Сокращение перебора. Жадные алгоритмы.

Тематическое планирование

Дата

Тема занятия

Кол-во часов

1

2.07.2012

понедельник

  1. Теоретический тур на выяснение уровня подготовки обучаемых.

  2. Сложность алгоритмов, практические рекомендации.

4

2

2

3.07.2012

вторник

  1. Арифметика многоразрядных целых чисел.

  2. Алгоритмы реализации многоразрядных целых чисел.

  3. Решение задач. Простые задачи на логику

2

2

2

3

4.07.2012

среда

  1. Лекция. Динамическое программирование.

  2. Алгоритмы реализации Динамического программирования.

  3. Решение задач. Простые задачки на логику, теория чисел.

2

2

2

4

5.07.2012

четверг

  1. Свойства и типы графов.

  2. Графы. Представление графов в памяти компьютера.

  3. Решение задач. Рекурсия. Быстрое возведение в степень.

2

2

2

5

6.07.2012

пятница

  1. Поиск в графе.

  2. Алгоритмизация. Поиск в глубину. Поиск в ширину.

  3. Решение задач. Нестандартная обработка чисел.

2

2

2

6

7.07.2012

суббота

  1. Деревья. Каркас минимального веса. Метод Краскала и Прима.

  2. Реализация алгоритмов Прима и Краскала.

  3. Решение задач. Бинарный поиск , слияние и сортировка.

2

2

2

7

8.07.2012

воскресенье

По плану выходного дня

8

9.07.2012

понедельник

  1. Лекция. Кратчайшие пути. Алгоритмы Дейкстры и Флойда.

  2. Реализация алгоритмов Дейкстры и Флойда.

  3. Решение задач. Поиск в графе.

2

2

2

9

10.07.2012

вторник

  1. Алгоритм Форда-Беллмана. Циклы. Гамильтонов и Эйлеров цикл.

  2. Реализация алгоритмов Форда-Беллмана.

  3. Решение задач. Обход графа.

2

2

2

10

11.07.2012

среда

  1. Лекция. Раскраски.

  2. Реализация алгоритма минимальной раскраски вершин графа.

  3. Решение задач. Графы.

2

2

2

11

12.07.2012

четверг

  1. Лекция. Комбинаторика. Основные понятия и определения.

  2. Алгоритмизация. Основные процедуры реализации комбинаторных объектов.

  3. Решение задач.

2

2

2

12

13.07.2012

пятница

  1. Лекция по комбинаторике. Правильные скобочные последовательности.

  2. Алгоритм реализации.

  3. Решение задач.

2

2

2

13

14.07.2012

суббота

Контест. Мини - олимпиада по пройденным темам.

6

14

15.07.2012

воскресенье

По плану выходного дня

15

16.07.2012

понедельник

  1. Лекция по аналитической геометрии ( представление элементарных объектов, их пересечение, построение выпуклой оболочки, типичные ошибки).

  2. Алгоритмы вычислительной геометрии. Алгоритм Джарвиса.

  3. Решение задач. Однопроходные алгоритмы.

2

2

2

16

17.07.2012

вторник

  1. Лекция. Вычислительная геометрия. Векторы. Операции над векторами. Скалярное и векторное произведение. Полярный угол. Взаимное расположение точек и фигур (принадлежность точки прямой, лучу, отрезку). Расстояние от точки до прямой. Пересечение двух отрезков. Уравнение прямой.

  2. Алгоритмизация. Решение стандартных геометрических задач (уравнение касательной к окружности, нахождение точек пересечения окружности и прямой, нахождение точек пересечения двух окружностей, уравнение биссектрисы угла).

  3. Решение задач. Динамическое программирование.

2

2

2

17

18.07.2012

среда

  1. Многоугольники. Вычисление площади многоугольника. Определение выпуклости многоугольника. Определение нахождения точки внутри простого многоугольника. Построение выпуклой оболочки. Алгоритмы Грэхема и Джарвиса. Особые точки многоугольников и множеств N точек плоскости. Эффективный алгоритм нахождения ближайшей пары из N точек плоскости.

  2. Алгоритмы на строках (алгоритмы Бойера-Мура и Кнута-Мориса-Пратта).

  3. Решение задач. Вычислительная геометрия.

2

2

2

18

19.07.2012

четверг

  1. Лекция. Перебор вариантов. Порождение подмножеств и последовательностей. Сокращение перебора.

  2. Алгоритмизация. Реализация переборных алгоритмов.

  3. Решение задач.

2

2

2

19

20.07.2012

пятница

  1. Лекция. Жадные алгоритмы.

  2. Алгоритмы реализации жадных алгоритмов.

  3. Решение задач.

2

2

2

20

21.07.2012

суббота

Итоговый контест «Дискретная математика»

6

 

Итого:

108

Уровень предъявления материала обеспечивает учащимся возможность получить представление о:

  • особенностях олимпиадного программирования;

  • оценки эффективности разрабатываемых задач;

  • основных разделах вычислительной математики, обеспечивающих решение сложных олимпиадных задач;

  • современных инструментальных средах разработки программ.

Учащиеся должны знать:

  • современные компиляторы для решения олимпиадных задач;

  • оценку сложности и методику тестирования программ;

  • методику составления математической модели вычислительного процесса;

  • базовые алгоритмы для решения сложных задач;

  • инструментальные средства поддержки разработки кода;

Учащиеся должны уметь:

  • настраивать и грамотно использовать редактор кода;

  • практически реализовывать математические модели на языке программирования;

  • составлять и грамотно тестировать программные коды;

  • пользоваться автоматизированными системами проверки программных кодов;

  • решать олимпиадные задачи повышенной сложности.

Формы занятий используемые при изучении данной темы:

  • традиционная;

  • лекция;

  • урок-консультация;

  • компьютерное тестирование.

Контроль эффективности

В процессе освоения учебного курса предусмотрена система контроля знаний и умений учащихся, а так же анкетирование учащихся, которые позволят определить эффективность обучения по программе, внести в дальнейшем изменения в учебный процесс.

Контроль уровня обученности представлен в трех видах:

  • самоконтроль по каждой теме, с последующим сравнением полученных результатов с ответами;

  • тестирование по каждой теме;

  • итоговое тестирование по курсу.

Система оценки учебной деятельности

Код

%

Оценка

А

95 –100

Отлично

А-

90 – 94

Отлично

В+

85 – 89

Отлично

В

80 – 84

Хорошо

В-

75 – 79

Хорошо

С+

70 – 74

Хорошо

С

65 – 69

Удовлетворительно

С-

60 – 64

Удовлетворительно

D+

55 – 59

Удовлетворительно

D

50 – 54

Неудовлетворительно

D-

45 – 49

Неудовлетворительно

F

0 – 44

Плохо

Список литературы

  1. Основы программирования /С. М. Окулов. – 2-е издю, испр. – М.:БИНОМ. Лаборатория знаний, 2005. – 440 с.: ил. ISBN 5-94774-217-9

  2. Программирование в алгоритмах /С. М. Окулов. – 2-е издю, испр. – М.:БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил. ISBN 5-94774-010 -9.

  3. Задачи по программированию / С.М. Окулов, Т.В. Ашихмина, Н.А. Бушмелева и др.; Под. Ред. С.М. Окулова. – М.: БИНОМ. Лаборатория знаний, 2006. – 820 с.; ил.

  4. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. – СПб.: ООО «ДиаСофтЮП», 2002. – 688 с.

  5. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с англ./Роберт Седжвик. – СПб.: ООО «ДиаСофтЮП», 2002. – 496с.

  6. Давыдов В.Г. Технологии программирования. С++. – СПб.: <{D-Gtnth,ehu? 2005/ - 672 c. ил.

  7. Фундаментальные алгоритмы и структуры данных в Delphi: Пер. с англ./Джулиан М. Бакнелл. – СПб: ООО. «ДиаСофтЮП», 2003. – 560 с..

  8. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач – М.: ООО «И.Д. Вильямс», 2007. – 480 с.: ил.

  9. Долинский М.С. Решение сложных и олимпиадных задач по программированию: Учебное пособие. Питер, 2006. – 366 с.: ил.

  10. Стивен Прата. Язык программирования С, Киев, 2000.

  11. Вирт Н. Алгоритмы и структуры данных: Пер. с анг. – М.: Мир, 1989. – 360 с.: ил.

  12. Культин Н.Б. Программирование в Turbo Pascal 7.0 и Delphi 5. СПб.: БХВ – Санкт-Петербург, 1999. 464 с.: ил.

  13. Рудаков П.И., Федотов М.А. Основы языка Pascal. – М.: Радио и связь, Горячая линия – Телеком, 1999. – 208 с.:ил

  14. Зеленяк О.П. Практикум программирования на Turbo Pascal. Задачи, алгоритмы и решения – К.: Издательство «ДиаСофт», 2001. – 320 с.

  15. Программирование на С и С++. Практикум: Учеб. Пособие для вузов/ А.В. Крячков, И.В. Сухинина, В.К. Томшин; Под ред. В.К. Томшина – 2-е изд., исправ. – М.: Горячая линия – Телеком, 2001. – 344 с.:ил.

  16. Подбельский В.В., Фомин С.С. Программирование на языке Си: Учеб. пособие. – 2-е доп.изд. – М.: Финансы и статистика, 2001. – 600 с.: ил.

  17. Язык программирования С. Лекции и упражнения. Учебник: Пер. с анг./ Стивен Прата – К.: Издательство «ДиаСофт», 2001. – 656 с.

  18. Язык программирования С++. Лекции и упражнения. Учебник: Пер. с анг./ Стивен Прата – К.: Издательство «ДиаСофт», 2001. – 656 с.

  19. Франка П. С++: Учебный курс. – СПб.: Питер, 2001. – 528 с.:ил.

  20. Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. – СПб.: Питер, 2005. – 237 с.: ил.

  21. Керниган, Брайан У., Пайк, Роб. Практика программирования.: Пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 288 с.: ил. Парал. тит. англ.



Скачать документ

Похожие документы:

  1. Чебоксары осуществляет свою деятельность в логике оказания индивидуальных образовательных услуг, услуг по индивидуальному заказу родителей и самих учащихся

    Документ
    МОУ «Гимназия №5» г. Чебоксары осуществляет свою деятельность в логике оказания индивидуальных образовательных услуг, услуг по индивидуальному заказу родителей и самих учащихся.
  2. Computer Using Educators, Inc., Usa центр новых педагогических технологий Московский областной общественный фонд новых технологий в образовании «Байтик» ано «ито» Материалы

    Документ
    Материалы XV Международной конференции «Применение новых технологий в образовании», 29 – 30 июня 2004г. г. Троицк, Московской области - МОО Фонд новых технологий в образовании «Байтик».
  3. Риалы VI международной научной конференции (2-3 марта 2006 г.) Белово 2006 ббк ч 214(2Рос-4Ке) 73я431 н 34

    Документ
    Н-34 Наука и образование: Материалы VI Международной научной конференции (2-3 марта 2006 г.): В 4 ч. / Кемеровский государственный университет. Беловский институт (филиал).
  4. Публичный отчет муниципального бюджетного общеобразовательного учреждения (2)

    Публичный отчет
    Муниципальное бюджетное общеобразовательное учреждение города Новосибирска «Средняя общеобразовательная школа № 202» находится в Октябрьском районе г.
  5. Основная образовательная программа высшего профессионального образования Направление подготовки (98)

    Основная образовательная программа
    - владением культурой мышления, способностью к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения владением культурой мышления,

Другие похожие документы..