Программно-методическое обеспечение профильного обучения по информатике и ИКТ

Тема 5. Алгоритмы и структуры данных (12 ч)

Содержание обучения

Поиск элементов методом деления пополам. Обработка текстовых данных, содержащихся в текстовых файлах. Алгоритмы сортировки порядка n* log 2( n). Конечные автоматы в задачах обработки текстов. Рекурсия. Рекурсивная обработка деревьев. Поиск делителей числа. Простые числа. Разложение числа на простые множители. Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК). Действия с многозначными (большими) числами.

Требования к знаниям и умениям выпускников

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

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

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

Кол-во часов	Тема урока	Содержание
1	Поиск элементов методом деления пополам	Поиск элементов в упорядоченном массиве методом дихотомии
2	Алгоритмы сортировки порядка n * log 2 ( n )	Быстрая сортировка, сортировка деревом, слиянием
1	Конечные автоматы в задачах обработки текстов	Составные символы, комментарии
2	Рекурсия. Рекурсивная обработка деревьев	Примеры рекурсивных программ. Двоичные деревья
2	Поиск делителей числа. Простые числа. Разложение числа на простые множители	Делитель числа. Алгоритмы поиска делителей числа, простых чисел. Алгоритм разложения простых чисел на простые множители
1	Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)	Алгоритм нахождения наибольшего общего делителя. Алгоритм нахождения НОК
2	Действия с многозначными (большими) числами	Сложение, вычитание, умножение больших чисел
1	Зачет по теме "Алгоритмы и структуры данных"

Литература

Абрамов С. А., Гнездилова Г. Г., Капустина Е. Н., Селюн М. И. Задачи по программированию. М.: Наука, 1988.
Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.

Разработки уроков

© Комитет по образованию администрации г. Мурманска, 2006-2007
Разработчик: Городской информационно-методический центр работников образования
При полном или частичном использовании материалов ссылка на диск обязательна