имим ппмро. Язык программирования С
 Скачать 251 Kb.
|
1 2 Краевое государственное образовательное учреждение дополнительного образования детей «Красноярский краевой Дворец пионеров и школьников» УТВЕРЖДАЮ Директор КГОУ КДПиШ ___________ В.А. Евтушенко Авторская образовательная программа Язык программирования С++ Возраст детей: 12-17 лет Срок реализации: 3 года Автор программы: Беляев Сергей Николаевич, педагог дополнительного образования Красноярск – 2010 г. Пояснительная записка В настоящее время мы находимся на этапе бурного роста информационных технологий. Практически все сферы человеческой деятельности связаны с использованием вычислительной техники. При появлении новых технологий и сфер деятельности при использовании компьютера возникает потребность в новых программах для ЭВМ, а значит и в специалистах, которые должны реализовывать это программное обеспечение. С++ является одним из наиболее распространенных современных языков программирования. Язык С++ хорошо зарекомендовал себя эффективностью, лаконичностью записи алгоритмов, логической стойкостью программ. С++ имеет ряд существенных особенностей, которые выделяют его среди других языков программирования. Знание этого языка позволит создавать эффективные программы. В процессе обучения используется программная среда Borland C++ 3.1 Полученные знания позволят легко освоить в дальнейшем более современные языки программирования под Windows, такие как Visual C и C++ Builder. С++ является основой для массы других популярных платформ программирования – JavaScript, PHP, Perl, Macromedia Flash и др. Помимо изучения самого языка, в программу входит рассмотрение различных алгоритмов, часто применяемых в программировании. Чем же популярен С++? Несмотря на сложность программы нельзя не отметить массу плюсов в его изучении. В связи с повышением использования компьютера людьми вырос спрос на специалистов в данной области. Квалифицированному программисту легко найти высокооплачиваемую работу. Изучение С++ поможет при поступлении и обучении в ВУЗе. В настоящее время масса предметов в ВУЗах требует навыков программирования, которые в большинстве случаев студентам приходится приобретать самостоятельно, на что уходит масса времени. Именно С++ наиболее предпочтителен в ВУЗах. С++ является основой для изучения более специализированных платформ с различными возможностями и направлениями компьютерной деятельности. Методические пособия, созданные в рамках настоящей образовательной программы, облегчают освоение языка и экономят время. Программа С++ состоит из трех модулей, каждый из которых рассчитан на 1 год обучения. Первый модуль: С++ для начинающих: программа рассчитана на детей, не имеющих опыта программирования, здесь требуется знать компьютер на уровне пользователя (Windows, система каталогов, копирование, создание файлов). Второй модуль: С++ для продолжающих: дети должны знать один из языков программирования (любой). Рекомендуется предварительное освоение модуля «С++ для начинающих». Программа рассчитана на детей с повышенными интеллектуальными способностями. В частности, важен математический склад ума и способности к решению нестандартных задач. Учащиеся проходят предварительное тестирование перед записью на данный модуль. Третий модуль: Решение олимпиадных задач: учащиеся должны хорошо знать один из языков программирования (желательно С++), а так же владеть базовыми алгоритмами, иметь хорошую математическую базу. Данная программа предназначена для узкой группы одаренных детей, имеющих способности к олимпиадному программированию. Рекомендуется предварительное освоение модуля «С++ для продолжающих». Учащиеся проходят предварительное тестирование перед записью на данный модуль. На данном этапе учащиеся не изучают языков программирования, наибольшая часть времени уделяется изучению сложных алгоритмов и практическим занятиям. Здесь учащиеся получают профессиональные навыки, позволяющие успешно выступать на районных и краевых предметных олимпиадах по информатике. Программа каждого из модулей представляет собой отдельную логическую единицу. Переход учащихся из одного модуля в другой является желательным, но не обязательным. По завершении обучения каждому из модулей в отдельности учащиеся получают достаточный объем знаний, соответствующих определенному уровню и требованиям данного модуля. Предусматривается профильное групповое обучение по 8-12 человек в группе, что обусловлено необходимостью использования вычислительной техники в классе, количество которой, как правило, ограничено, а так же некоторыми особенностями программы, которая требует индивидуального подхода к учащимся, что накладывает ограничения на ресурсы педагога. Программа каждого модуля рассчитана на 144 часа при нагрузке 4 часа в неделю (2 занятия по 2 часа). Для проведения занятий необходимо помещение, оснащенное компьютерами (по одному на каждого учащегося), объединенных в локальную сеть. Для третьего модуля обучения требуется подключение компьютеров к Internet на скорости не менее 128 Кбит / сек. Основные цели образовательной программы: формирование у учащихся практических навыков применения компьютерной техники для решения задач различного рода; компьютерное моделирование процессов. подготовка учащихся к обучению в ВУЗах по следующим специализациям и направлениям: информатика и вычислительная техника; информатика и системы управления; системы компьютерной безопасности; системный анализ и исследование операций (и др.). Для достижения этих целей решаются следующие задачи: изучение синтаксиса языка С++; формирование навыков разработки алгоритмов для решения практических задач; ознакомление с существующими на данный этап стандартными алгоритмами и подходами (сортировка, поиск, шифрование данных, понятие сжатия данных и др.). введение базовых понятий из области аналитической геометрии ознакомление с алгоритмами машинной графики подготовка к соревнованиям по олимпиадному программированию Реализация этих задач будет способствовать развитию определенного стиля мышления, который необходим для эффективной работы в условиях динамически развивающегося информационного общества, а также получению базовых знаний, необходимых для дальнейшего развития и повышения эффективности работы. Программа построена на основе концепции модульного обучения, которая предусматривает активное участие каждого учащегося в процессе обучения и его (процесса обучения) индивидуализацию. Требование к уровню образования (7-11 класс) связано с общеобразовательной школьной программой, так как некоторые элементы настоящей программы предполагают определенную базу знаний, а наличие сложных тем накладывает дополнительное ограничение на возраст учащихся. Помимо изучения языка программирования, программа включает в себя элементы прикладного и системного программирования, а также моделирования процессов, которые не входят в школьную программу по информатике. Методические особенности программы При проведении занятий используются следующие формы работы: лекционная (получение учащимися нового материала); самостоятельная (выполнение индивидуальных заданий в течении части занятия или одного-двух занятий); проектная деятельность (получение новых знаний, реализация личных проектов) олимпиады (практическое участие в Internet-олимпиадах, использование Internet-технологий в процессе обучения) Условия реализации данной программы: Для проведения занятий можно использовать любые виды школьных компьютеров, удовлетворяющих санитарно-гигиеническим требованиям. Предпочтительная конфигурация технических и программных средств включает: учебный компьютерный класс на 8 - 12 рабочих мест. Компьютеры объединены в локальную сеть и подключены к серверу; каждый учащийся имеет сетевой адрес, пароль и личное пространство на диске размером 10Mb; подключение к Internet на скорости не менее 128 Кбит / сек. Программное обеспечение: операционная система Window 2000 и выше; оболочка – файловый менеджер (Far Manager, Total Commander или аналог); среда программирования Borland C++ 3.1; MinGW Developer Studio 2.0; среда программирования Microsoft Visual Studio 2005 (включая Microsoft Visual С++ 8.0); Borland Delphi 7.0; Internet Explorer 6.0 и выше. Методическое обеспечение: учебное пособие для учащихся «Borland C++ 3.1 для начинающих» (76 стр.), Беляев С.Н. 2004г.; учебное пособие для учащихся «Borland C++ 3.1 для продолжающих» (80 стр.), Беляев С.Н. 2005г.; методическое пособие «Олимпиадные задачи по программированию» (108 стр.), Беляев С.Н., 2007г.; Региональные олимпиады по информатике - 2008/2009: учебно-методическое пособие / Беляев С.Н., Лалетин Н.В. - Краснояр. гос. пед. ун-т им. В.П. Астафьева. - Красноярск, 2009. - 192 с.; авторский Internet-ресурс http://acmp.ru, предназначенный как для очного, так и для дистанционного обучения школьников. По окончании первого модуля учащийся должен: знать синтаксис языка С++; владеть основами алгоритмизации; знать основные алгоритмы решения стандартных задач. По окончании второго модуля учащийся должен: знать синтаксис языка С++; уметь разработать алгоритм решения поставленной задачи средней сложности и составить реализацию этого алгоритма на языке программирования С++; знать базовые алгоритмы решения задач. По окончании третьего модуля учащийся должен: иметь высокий уровень знаний одного из языков программирования; владеть большой алгоритмической базой; уметь решать олимпиадные задачи по информатике. Виды и формы контроля знаний, умений и навыков: индивидуальные задания; компьютерное тестирование; контрольное задание; личный проект. участие в олимпиадах различного уровня Способы оценки достижений: рейтинг (по результатам компьютерного тестирования и выполнения контрольных работ и самостоятельных заданий); результаты участия в олимпиадах, конкурсах и НОУ. рейтинг на сайте http://acmp.ru, результаты участия в личных и командных олимпиадах Учебно-тематический план Модуль 1
Модуль 2
Модуль 3
Содержание программы Модуль 1 Раздел: Введение. (22 часа) Основные понятия. Техника безопасности. Структура ЭВМ. Интегрированная среда BC. Оболочка Borland C++ 3.1. Редактирование, работа с меню. Горячие клавиши. Понятие алгоритма. Алгоритм. Связь алгоритма с программой. Блок-схема алгоритма. Примеры. Типы данных. Переменные. Понятие переменной. Базовые типы данных. Структура программ. Первая программа. Стандартные функции. Выражения. Операторы ввода - вывода. Арифметические выражения. Математические функции библиотеки math.h. Решение задач. Отладка программ. Операции над целыми типами. Задача о счастливых билетах. Раздел: Операторы ветвления. (20 часов) Условный оператор Ветвление. Вариации условного оператора. Примеры. Решение задач с использованием условного оператора. Циклы. Понятие цикла. Виды циклов. Примеры. Цикл с параметром. Понятие цикла с параметром. Блок-схема цикла. Примеры. Решение задач. Цикл с предусловием. Понятие цикла с предусловием. Блок-схема цикла. Примеры. Решение задач. Цикл с постусловием. Понятие цикла с постусловием. Блок-схема цикла. Примеры. Решение задач с использованием функций библиотеки conio.h . Оператор switch. Оператор варианта. Практическое использование оператора switch в программах. Раздел: Типы данных. (20 часов) Символьные типы. Понятие символьного типа. Типы char и char*. Обработка символьных переменных. Решение задач со строками. Массивы. Понятие массивы. Описание массива. Работа с элементами типа массив. Решение задач с массивами. Структуры. Комбинированный тип struct. Примеры. Решение задач с использованием структур. Двумерные массивы. Определение двумерных массивов. Работа с матрицами. Примеры. Повторение пройденного материала. Раздел: Графика. (22 часа) Графический режим. Графический режим. Библиотека graphics.h. Инициализация графики. Операторы putpixel, line, setcolor, circle, getpixel. Основные графические операторы. Заливка и текстуры: setfillstyle, floodfill. Прямоугольные объекты: rectangle, bar, bar3d. Графические режимы: installuserdriver, getmaxx, getmaxy. Текст в графике. Использование текста в графике. Операторы settextstyle, outtextxy. Динамическая память. Спрайты. Тип данных pointer. Спрайты. Операторы imagesize, getimage, putimage. График функции. Построение графика функции в декартовой и полярной системах координат. Раздел: Функции. (20 часов) Понятие функции. Механизм параметров. Функции. Общая структура функций. Примеры. Решение задач. Рекурсия. Рекурсия. Механизм написания рекурсивных подпрограмм. Решение задач по теме “Подпрограммы”. Алгоритмы сортировки массива. Сортировка массива. Алгоритмы: пузырька, выбора, вставки и быстрой сортировки. Решение задач. Раздел: Файлы. (20 часов) Файловые переменные и типы. Файлы. Файловые переменные и типы. Операции над файлами. Операции ввода-вывода. Операторы ввода-вывода: read, write. Перемещение по файлу. Задача о шифровке файла. Текстовые файлы. Текстовые файлы. Обработка текстовых файлов. Работа с текстовыми файлами без текстовых переменных. Решение задач по теме “Файлы”. Раздел: Проекты. (20 часов) Таймер. Стандартные библиотеки в BC. Использование таймера в программах. Графический редактор. Модуль MS_MOUSE.H. Работа с мышью. Реализация программы «Графический редактор». Динамические переменные. Динамические переменные. Решение задач по теме «Динамические переменные». Модуль 2 Раздел: Структура языка. (12 часов) Введение. Интегрированная среда BC. Техника безопасности. Введение. Достоинства и недостатки языка C++. Структура программы. Интегрированная среда BC. Работа с меню. “Горячие клавиши”. Стандартные библиотеки. Стандартные библиотеки языка: «stdio.h», «stdlib.h», «conio.h», «math.h» и «graphics.h». Базовые типы и операторы. Базовые типы данных. Объявление переменных. Инициализация. Операторы ввода-вывода. Операции над целыми типами. Раздел: Операторы циклов и условия. (6 часов) Условный оператор. Запись условий в C++. Условный оператор. Примеры. Операторы циклов. Циклы в С++. Операторы циклов: for, while, do…while. Текстовый режим. Текстовый режим. Функции библиотеки conio.h . Раздел: Структуры данных. (28 часов) Указатели. Указатели. Объявление указателей и ссылочных переменных. ASCIIZ-строки. ASCIIZ-строки. Динамическое выделение памяти. Решение задач с использованием строк. Структуры и комбинированные типы. Комбинированные типы данных. Спецификатор структуры struct. Оператор объединения union. Операторы switch и break. Работа с массивами. Массивы. Одномерные и двумерные массивы. Решение задач с массивами. Раздел: Функции. (10 часов) Функции. Аргументы функции main. Функции. Аргументы функции main. Полиморфные функции. Определение полиморфизма. Полиморфные функции. Функции с переменным числом аргументов. Функции с переменным числом аргументов. Реализация функции суммы и максимума от многих аргументов. Системы счисления. Определение и свойства систем счисления. Перевод чисел из одной системы в другую. Раздел: Графика. (26 часов) Графический режим. Инициализация графического режима в С++. Отображение графических элементов. Текстура и заливка: setfillstyle, floodfill. Работа с текстом в графике: settextstyle, outtextxy. Спрайты: операторы getmem, getimage, putimage. Графические страницы. Графические страницы. Операторы setvisualpage и setactivepage. Технология движения графических объектов с использованием графических страниц. Построение полигонов. Построение полигонов. Операторы grawpoly, fillpoly. Решение задач по теме «Графика». Алгоритмы Брезенхама. Алгоритмы Брезенхама построения линии и окружности по точкам. Раздел: Движение графических объектов. (18 часов) Движение точки на плоскости. Движение точки на плоскости. Вращение, параллельный перенос. Перемещение многоугольника на плоскости. Проволочная модель куба. Понятие проволочной модели объекта. Движение проволочной модели куба в пространстве. Выпуклое тело в пространстве. Удаление невидимых линий. Отображение выпуклого тела в пространстве. Понятие перспективы. Перспективное отображение тела в пространстве. Раздел: Файлы. (16 часов) Файловые переменные и типы. Файлы. Файловые переменные и типы. Операции над файлами. Операции ввода-вывода. Текстовые файлы. Задачи с файлами. Перемещение по файлу. Задача о шифровке файлов. Решение задач. Раздел: Рекурсия. (28 часов) Виды рекурсий. Рекурсия. Виды рекурсий. Вычисление факториала и чисел Фибоначчи. Задача о ханойской башне. Задача о шахматном коне. Быстрая сортировка Хоара. Списки, стеки, очереди. Динамические структуры данных. Списки, стеки, очереди. Бинарные деревья. Бинарные деревья. Сортировка бинарным деревом. Решение олимпиадных задач. Обзор олимпиад по программированию. АСM - олимпиады. Разбор олимпиадных задач. Модуль 3 Раздел: Введение в олимпиадное программирование. (28 часов) Введение. Введение. Виды и типы олимпиад по спортивному программированию. Языки программирования. Обзор языков программирования семейства С++: Borland C++ 3.1, Microsoft Visual C++ 8.0, Java 2 SDK 1.5 . Обзор языков программирования семейства Pascal: Borland Pascal 7.0, Borland Delphi 7.0, Free Pascal 2.0 . Типы данных. Работа с файлами. Базовые типы данных: целые, вещественные, строки, массивы. Работа с файлами: чтение и вывод данных. Структура олимпиадной задачи. Классификация задач. Порядок сложности задач. Базовые алгоритмы. Алгоритмы сортировки массивов: пузырьком, выбором, быстрая сортировка, цифровая сортировка. Алгоритм двоичного поиска. Решение задач. Раздел: Системы автоматического судейства. (20 часов) Системы самотестирования Принципы работы системы самотестирования. Системы: T-Run, Checker Федора Меньшикова, система от olympiads.ru Acmp.ru Знакомство с сайтом http://acmp.ru. Отправка задач в разделе «Архив задач». Участие в личных и командных олимпиадах. Acm.timus.ru Знакомство с Timus Online Judge - архивом задач с проверяющей системой. Рейтинговая система, статистика, форум. Система командных олимпиад. Olympiads.ru Олимпиадная информатика olimpiads.ru: структура сайта, система проведения internet-олимпиад. Neerc.ifmo.ru Раздел сайта для школьников: http://neerc.ifmo.ru/school : архив задач и результатов официальных олимпиад. Участие в личных и командных олимпиадах базового уровня. Раздел: Структуры данных. (16 часов) Элементарные структуры данных. Стеки и очереди. Словари и множества. Бинарные деревья. Использование указателей для формирования структур. C++ Standard Template Library. Понятие шаблона в C++. Основные объекты: стек, очередь, словарь в STL. Использование функций STL для работы со структурами. Преимущества. Примеры. Алгоритмы, использующие структуры. Разбор алгоритмов решения задач «Карточная колода», «Покраска карты», «Скобки». Раздел: Теория чисел. (20 часов) Системы счисления. Свойства систем счисления. Перевод числа из одной системы в другую. Виды чисел и последовательностей. Простые числа. Поиск простых чисел. Разложение числа на множители. Совершенные числа. Числа Фибоначчи. Целочисленная арифметика. Наибольший общий делитель и наименьшее общее кратное. Свойства НОД и НОК. Алгоритм Евклида. Длинная арифметика. Понятие длинной арифметики. Структуры для хранения длинных чисел. Арифметические операции с длинными числами: сложение, умножение, деление и извлечение корня. Раздел: Комбинаторика. (16 часов) Базовые методики счета. Классификация комбинаторных задач. Перебор с помощью двоичных чисел. Перестановки. Обратная перестановка. Поиск циклов и порядка перестановки. Задача о счастливых билетах. Биномиальные коэффициенты. Факториал. A(k,n) и C(k,n). Биномиальные коэффициенты. Вычисление количества комбинаций с использованием сочетаний. Задача «Великий комбинатор». Рекурсия и перебор. Прямая и косвенная рекурсия. Примеры. Рекурсивный перебор всех перестановок. Решение задач. Раздел: Динамическое программирование. (12 часов) Математическая индукция. Принцип математической индукции. Понятие динамического программирования. Примеры. Рекуррентные соотношения. Понятие рекуррентного соотношения. Примеры. Решение задач. Решение задач: «Гвоздики», «Покраска забора», «Лесенка», «Скобочки». Раздел: Графы. (16 часов) Введение. Введение: понятие графа, определения. Классификация графов. Структуры данных для графов. Матрица смежности и таблица ребер. Примеры. Обход графа в ширину. Волновой алгоритм. Пример поиска кратчайшего пути в лабиринте. Обход графа в глубину. Рекурсивная реализация обхода графа в глубину. Задача коммивояжера. Алгоритмы с графами. Алгоритмы Дейкстры и Флойда поиска наикратчайшего пути в графе. Алгоритм Форда-Беллмана релаксации вершин графа. Алгоритм Каскала и Примы построения остова графа. Раздел: Геометрия. (16 часов) Аналитическая геометрия. Векторное и скалярное произведения и их свойства. Вычисление площади треугольника. Принадлежность точки треугольнику. Расстояние от точки до прямой. Вычислительная геометрия. Пересечение отрезков. Площадь многоугольника. Выпуклая оболочка. Теорема Пика. Разбор геометрических задач. Разбор задач: «Треугольные страны», «Целые точки» и «Дремучий лес». Список литературы Алексеев А.В., Беляев С.Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учебно-методическое пособие для учащихся 7-11 классов. Ханты-Мансийск: РИО ИРО, 2008. – 284 с. Алексеев А.В., Беляев С.Н. Дистанционная подготовка школьников к олимпиадам по информатике: учебно-методическое пособие для учащихся 7-11-х классов. Екатеринбург : Сред.-Урал. кн. изд-во, 2009. – 456 с. Беляев С.Н., Лалетин Н.В. Региональные олимпиады по информатике – 2008/2009 : учебно-методическое пособие; Краснояр. гос. пед. ун-т им. В.П. Астафьева. – Красноярск, 2009. – 192 с. Дьюхарст С., Старк К. Программирование на С++, 1993. - 272 с. Бочков С.О., Субботин Д.М. Язык программирования Си для персонального компьютера. - М.: Радио и связь, 1990. - 384 с. Язык С для профессионалов. - М.: Н.В.К - СОФТ, 1992 - 320 с. Белецкий Я. Турбо Си++. Новая разработка. - М.: Машиностроение, 1994. - 400 с. Бочков С.О., Субботин Д. М. Язык программирования Си для персональных компьютеров. –М.: Радио и связь, 1990. Фигурнов В. Э. IBM PC для пользователя. Изд. 6- е, перераб. и доп. – М.: ИНФРА–М, 1995. Шилдт Г. Теория и практика С++: пер. с англ. – СПб.: BHV – Санкт- Петербург, 1996. Страуструп Б. Введение в Си++. Электронный вариант книги разработчика Си++ http://www.citforum.ru/ Федор Меньшиков. Олимпиадные задачи по программированию + CD – СПб.: Питер, 2007 – 315 с. Скиена С.С., Ревилла М.А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям – М.: КУДИЦ-ОБРАЗ, 2005. – 416 с. 1 2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||