Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» icon

Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей»



НазваниеПрограммирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей»
Дата конвертации07.10.2012
Размер121.01 Kb.
ТипПрограмма
источник

ПРОГРАММИРОВАНИЕ МАТЕМАТИЧЕСКИХ ЗАДАЧ


Колотова И.В., учитель информатики МОУ «Медико-биологический лицей» г. Саратова


Пояснительная записка.

Программа «Программирование математических задач» относится к математическим основам информатики и адресована учащимся, выбравшим информационно-технологический профиль и прослушавшим базовый курс, предполагающий получение достаточных знаний основных структур языка Pascal. Задачей данного цикла элективных курсов является расширение знаний по заявленной тематике, что необходимо как для дальнейшего успешного освоения программы ВУЗа, так и для работы в будущем в качестве программиста-разработчика программных продуктов. Тем учащимся, которые не станут профессионалами, полученные знания помогут глубже понять алгоритмы поиска и сортировки, которые присутствуют во многих широко используемых программных продуктах, например таких, как Word и Excel. Знания по тематике данного цикла элективных курсов необходимы будущему программисту. Так, например, владение техникой составления рекурсивных процедур значительно облегчит изучение функциональных языков программирования, таких, например, как LISP или Haskell.

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

Цикл элективных курсов «Программирование математических задач» состоит из четырёх, каждый из которых может рассматриваться как отдельный, самостоятельный модуль. Учитель вправе использовать целиком предложенный цикл элективных курсов или отдельные его модули в зависимости от цели и задачи обучения. В зависимости от уровня обученности модули цикла могут изучаться в 9 классе (если предпрофиль осуществлялся с 8 класса и учащиеся овладели знаниями основ языка Pascal) или в 10 классе при наличии подготовки по информатике в объёме базового курса 9 класса.

При составлении программы цикла элективных курсов «Программирование математических задач» была использована работа ученых Саратовского государственного университета Огневой М.В. и Шуриновой Е.В. Turbo Pascal: первые шаги. Примеры и упражнения. Саратов, «Стило», 2001 г.

Цикл элективных курсов «Программирование математических задач» состоит из следующих четырех модулей:

^ Первый модуль. (9 часов) Рекуррентные соотношения. Определение рекуррентного соотношения. Составление рекуррентных соотношений для последовательностей. Задачи суммирования. Числа Фибоначчи и их свойства.

Контрольная работа №1.

^ Второй модуль. (8 час.) Рекурсии. Определение рекурсивного алгоритма. Известные задачи, решаемые методом рекурсии. Составление рекурсивных алгоритмов.

Контрольная работа №2.

^ Третий модуль. .(8 час.) Методы сортировки. Три основных метода сортировки: простой выбор, простой обмен, простые вставки. Методы быстрой сортировки: подсчетом и слияниями. Обсуждение алгоритмов и составление программ. Решение задач.

Контрольная работа №3

^ Четвертый модуль. (8 час.) Алгоритмы поиска. Поиск в неупорядоченном массиве, линейный поиск, бинарный поиск, случайный поиск. Поиск второго минимального элемента. Решение задач. Контрольная работа №4

В результате изучения цикла элективных курсов «Программирование математических задач» учащиеся должны иметь представление:

- о рекуррентных соотношениях;

- о рекурсивных алгоритмах;

- об основных методах сортировки: простым выбором, простым обменом и простыми вставками;

- о методах быстрой сортировки: подсчетом, слияниями;

- об алгоритмах линейного, бинарного и случайного поиска.

уметь:

- составить рекуррентные соотношения для решения задач суммирования;

- решить известные задачи методом рекурсии;

- применить алгоритмы сортировки методами простых вставок, простого обмена и простого выбора и изученные алгоритмы быстрой сортировки при решении задач;

- использовать изученные алгоритмы поиска при решении задач.


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

Первый модуль. Рекуррентные соотношения.

Определение рекуррентной последовательности. Составление рекуррентных соотношений для последовательностей. Задачи суммирования. Числа Фибоначчи и их свойства.

^ Второй модуль. Рекурсии.

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

^ Третий модуль. Методы сортировки.

Сортировка методами простого выбора, простого обмена и простых вставок. Подробное изучение на примерах. Методы быстрой сортировки: подсчетом и слияниями. Решение задач.

^ Четвертый модуль. Методы поиска.

Поиск в неупорядоченном массиве. Линейный поиск. Бинарный поиск. Случайный поиск. Поиск 2-го минимального элемента. Решение задач.




^ Тема модуля

Кол-во часов

Формы работы

Образовательный продукт

Формы контроля

Литература для учителя

Литература для учащихся

1

Модуль 1. Рекуррентные соотношения.

Составление рекуррентных соотношений для последовательностей. Задачи суммирования. Числа Фибоначчи и их свойства.

9

Лекции.

Практикум по решению задач и составлению программ.

Опорный конспект.

Индивидуальный решебник с программами и подробными комментариями.

Контрольная работа №1.

1. Огнева М.В., Шуринова Е.В. Turbo Pascal: первые шаги. Примеры и упражнения. Саратов, «Стило», 2001 г.

2. Н.Н. Воробьёв. Числа Фибоначчи. «Наука», 1984 г.

1. В.А. Дагене, Г.К. Григас, К.Ф. Аугутне. 100 задач по программированию. М., Просвещение, 1995 г.

2. Огнева М.В., Шуринова Е.В. Turbo Pascal: первые шаги. Примеры и упражнения. Саратов, «Стило», 2001 г.

2

Модуль 2. Рекурсии.

Понятие о рекурсивных алгоритмах. Определение рекурсии. Составление рекурсивных алгоритмов.

8

Лекции.

Практикум по решению задач и составлению программ.

Опорный конспект.

Индивидуальный решебник с программами и подробными комментариями.

Контрольная работа №2.

1. С. Окулов. Основы программирования. Москва. БИНОМ. Лаборатория знаний. 2005 г.

1. В.А. Дагене, Г.К. Григас, К.Ф. Аугутне. 100 задач по программированию. М., Просвещение, 1995г.

3

Модуль 3. Методы сортировки.

Сортировка методами простых вставок, простого выбора, простого обмена. Методы быстрой сортировки: подсчетом и слияниями. Решение задач.

8

Лекции.

Практикум по решению задач и составлению программ.

Опорный конспект.

Индивидуальный решебник с программами и подробными комментариями.

Контрольная работа №3.

1. С. Окулов. Основы программирования. Москва. БИНОМ. Лаборатория знаний. 2005 г.

1. В.А. Дагене, Г.К. Григас, К.Ф. Аугутне. 100 задач по программированию. М., Просвещение, 1995г.

4

Модуль 4. Методы поиска.

Поиск в неупорядоченном массиве. Линейный поиск. Бинарный поиск. Случайный поиск. Решение задач.

Поиск 2-го минимального элемента.

8

Лекции.

Практикум по решению задач и составлению программ.

Опорный конспект.

Индивидуальный решебник с программами и подробными комментариями.

Контрольная работа №4.

1. С. Окулов. Основы программирования. Москва. БИНОМ. Лаборатория знаний. 2005 г.

1. В.А. Дагене, Г.К. Григас, К.Ф. Аугутне. 100 задач по программированию. М., Просвещение, 1995г.


^ Примерный план урока.

Тема: Метод быстрой сортировки: сортировка слиянием.

Цель урока: рассмотреть алгоритм сортировки методом слияния, составить процедуру на Pascal'е и провести ее ручную трассировку на различных примерах.

^ Задачи урока:

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

б) вместе с учащимися создать процедуру на Pascal'е;

в) отработать навыки трассировки процедуры «вручную» на нескольких примерах.
^

Ход урока


1. Проверка домашнего задания.

2. Рассказ об алгоритме сортировки методом слияний.

Метод сортировки слиянием был предложен Дж. фон Нейманом в 1946 году.

Прежде, чем говорить непосредственно о методе сортировки слиянием, рассмотрим следующую задачу. Требуется объединить («слить») два упорядоченных фрагмента массива А A[k],..., A[m] и A[m+1],..., A[q] в один A[k],...,A[q] тоже упорядоченный (k ≤ m ≤ q).

Чтобы решить эту задачу, поступим следующим образом: создадим вспомогательный массив D и будем сравнивать очередные элементы каждого фрагмента. Тот элемент, который окажется меньше, будем переносить в массив D. При этом следует не забыть переписать в D оставшиеся элементы того фрагмента, который не успел себя исчерпать.

Рассмотрим это решение на примере: пусть первый фрагмент состоит из четырех элементов: 1, 2, 6, 8, а второй из трех элементов: 3, 4, 7. Составим таблицу выполнения изложенного алгоритма:


^ Номер шага

Входные массивы

(фрагменты)

Выбираемый элемент

Выходной массив D

1

1, 2, 6, 8

3, 4, 7

1

пустой

2

2, 6, 8

3, 4, 7

2

1

3

6, 8

3, 4, 7

3

1, 2

4

6, 8

4, 7

4

1, 2, 3

5

6, 8

7

6

1, 2, 3, 4

6

8

7

7

1, 2, 3, 4, 6

7

8

Пусто

8

1, 2, 3, 4, 6, 7

8

Пусто

Пусто

-

1, 2, 3, 4, 6, 7, 8


Т.о., получили массив D, также упорядоченный. Здесь: k=1, m=4, q=7.

Задание 1. «Слить» два следующих массива «вручную»:

(3, 5, 8, 11) и (1, 4, 5, 7, 11, 16, 18, 20). Составить таблицу.

Задание 2. «Слить два массива «вручную»:

(1, 2, 5, 7, 9, 11) и (2, 3, 4, 6, 10, 12, 17, 19). Составить таблицу.

Пусть в основной программе объявлен тип массив:

Type

Marray= Array[1..N] of integer;

где N – максимальное количество элементов массива.

Составим процедуру на Pascal'е для описанного выше алгоритма:

Procedure S1(k, m,q: integer; Var A: Marray);

Var

i, j, t: integer;

D: Marray;

Begin

i:=k; j:=m+1; t:=1;

While (i<=m) and (j<=q) Do

Begin (* пока не закончился хотя бы один массив*)

If A[i]<= A[j]

Then

Begin D[t]:=A[i]; Inc(i); end

Else

Begin D[t]:= A[j]; Inc(j); end;

Inc(t);

end;

While i<=m Do

Begin D[t]:= A[i]; Inc(i); Inc(t) End;

While j<=q Do

Begin D[t]:= A[j]; Inc(j); Inc(t) End;

For i:=1 to t-1 Do A[k+i-1]:=D[i];

end;


Задание 3. Провести «вручную» трассировку процедуры на следующем примере: «Слить» два массива: (1, 3, 4, 6, 8, 11) и (2, 5, 7, 10).

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

Пример. Сортировка слиянием массива из 10 элементов.


Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5

19




1




1




1




1

1




19




19




19




13

25




25




25




21




19

63




63




63




25




21

92




87




21




38




25

87




92




38




63




38

21




21




87




87




42

38




38




92




92




63

42




13




13




13




87

13




42




42




42




92


Параметр m из заголовка процедуры S1 можно убрать. Достаточно оставить нижнюю и верхнюю границы массива. Пусть k – нижняя граница, а q - верхняя.

Вычисление m, которая теперь становится локальной переменной, сводится к оператору: m:=k + (q-k) div 2;

Домашнее задание. Написать процедуру S1, сделав параметр m локальной переменной.

Написать рекурсивную программу сортировки «слиянием».

Планируемый результат урока: освоение и уверенное использование при решении задач алгоритма сортировки слиянием, одного из алгоритмов быстрой сортировки.




Похожие:

Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconВведение в комбинаторику колотова И. В., учитель информатики ноу «Медико-биологический лицей»
Все это необходимо для изучения и построения формальных моделей и позволяет научиться такому подходу к любой задаче. При этом решение...
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconАнализ математических функций василихин Ростислав Викторович
Голованова О. В., учитель информатики, муниципальное образовательное учреждение лицей №180
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconНестандартные методы решения алгебраических задач куприянов Владислав
Голованова О. В., учитель информатики, муниципальное образовательное учреждение лицей №180
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconАвтор: Медведева Анастасия, учащаяся 10 класса моу сош №3. Алексашина Галина Михайловна, учитель математики
«Применение математических методов при решении задач из различных областей науки и практики»
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconБиологический квн 9 классы назарова Эльвира Александровна, учитель биологии мбоу «Лицей «Дубна»
Приучить учащихся самостоятельно мыслить, проявлять инициативу, творческую активность
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconПолатайко Ирина Андреевна, Псковская область, город Остров
Научные руководители: Иванова Галина Петровна, учитель математики, заведующая кафедрой математики и информатики, моу «Гимназия»,...
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconУсловия обучения в краевой заочной школе естественно-математических наук
Краевая заочная школа естественно-математических наук (кзшемн) вошла в состав отделения дополнительного образования детей гбоу спо...
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconКабинет информатики моу «Лицей №19»

Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconСолошенко Антон, Румянцев Родион г. Омска. Руководители: Лукашенко Ирина Викторовна, учитель биологии моу «Лицей №74»
Руководители: Лукашенко Ирина Викторовна, учитель биологии моу «Лицей №74». Мальгина Ирина Леонидовна, педагог доп образования Областной...
Программирование математических задач колотова И. В., учитель информатики моу «Медико-биологический лицей» iconРешение задач части с егэ по информатике по теме: "Алгоритмизация и программирование"
Андрафанова, Н. В. Решение задач части с егэ по информатике по теме: “Алгоритмизация и программирование” [Текст] / Н. В. Андрафанова...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы