Методика развития алгоритмического мышления учащихся 10-11 классов

— графическим, с помощью специальных графических символов;

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

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

Поговорим подробнее о вероятностных алгоритмах.

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

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

Различают два типа стохастических алгоритмов.

- Алгоритмы типа Лас-Вегас, которые всегда дают корректный результат, однако время их работы не определено. Попросту говоря, цепь действий в таком алгоритме позволяет быть уверенными, что интересующее нас событие рано или поздно случится, но, когда это произойдет -- неизвестно.

- Алгоритмы типа Монте-Карло, которые, в отличие от предыдущих, могут давать неправильные результаты с известной вероятностью. То есть последовательность действий в таком алгоритме не обязательно приведет к интересующему событию, но зато вы точно знаете величину вероятности того, что в результате выполнения алгоритма такое событие случится (или не случится), и можете прогнозировать последствия с достаточной степенью достоверности [29].

1.5 АНАЛИЗ УЧЕБНОЙ ЛИТЕРАТУРЫ ДЛЯ 10-11 КЛАССОВ

Для того, чтобы эффективно подобрать материал курса по выбору, следует проанализировать содержание учебников информатики по теме «Алгоритмы».

Для анализа учебной литературы основной школы курса «Информатика» были выбраны следующие учебники из федерального перечня учебников:

1. Гейн А.Г., Ливчак А.Б., Сенокосов А.И. и др. «Информатика» 10- 11 класс, базовый уровень [15, 16];

2. Семакин И.Г., Хеннер Е.К., Шеина Т. Ю. «Информатика» 10-11 класс, базовый уровень [32, 33];

3. Калинин И.А., Самылкина Н.Н. «Информатика» 10-11 класс, углублённый уровень [17, 18].

Анализ учебников будет проводится по следующим критериям:

• в каком классе изучается тема;

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

• какие свойства алгоритмов выделяют авторы;

• какие способы записи алгоритмов рассматривают авторы;

• наличие оценки сложности алгоритмов;

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

• примеры алгоритмов, рассматриваемые авторами.

Таблица 2. Сравнительная таблица учебников по содержанию темы «Алгоритмы»

Учебно- методическ ие комплексы	Гейн А.Г., Ливчак А.Б., Сенокосов А.И. и др. «Информатика» 10-11 класс, базовый уровень [15, 16].	Семакин И.Г., Хеннер Е.К., Шеина Т. Ю. «Информатика» 10- 11 класс, базовый уровень.	Калинин И.А., Самылкина Н.Н. «Информатика» 10-11 класс, углублённый уровень [17, 18]
Класс	10	10	10
Название главы/параграфа	Алгоритмы и их Свойства	Алгоритмы и величины.	Глава 4. Алгоритмы и программы
		Структура алгоритмов.
Определени е алгоритма	Алгоритмом называется последовательность действий, допустимых для некоторого исполнителя, которая приводит к определенномурезультату.	Алгоритм - это последовательность команд управления каким-либо исполнителем.	Алгоритм - конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает свойствами: конечность, определённость, ввод, вывод, эффективность.
Свойства алгоритма	• дискретность; • детерминированнос ть; • результативность; • конечность; • понятность; • массовость.	Не указано.	• результативность (конечность); • детерминированн ость (определённость); • понятность и дискретность (ввод и вывод); • эффективность; • массовость.
Способы записи алгоритма	• формальный; • схема алгоритма (блок-схема).	• блок-схема; • aлгоритмиче ский язык.	• cловесно- математически; • блок-схема; • описание нпа формальном языке.
Виды алгоритмов	Способы организации действий в алгоритме: • линейный; • ветвление (2 вида); • цикл (2 вида).	Базовые алгоритмические структуры: • следование; • ветвление; • цикл.	Классификация алгоритмов сложности.
Сложность алгоритмов	Нет	Нет	Да
Примеры алгоритмов	Вычисление чисел НОД двух	Алгоритм нахождения корней квадратного уравнения.	Явных примеров нет.

Изучив вышеперечисленные учебники на содержание темы «Алгоритмы», можно сделать следующие выводы: в основном авторы учебников рассматривают алгоритмы как пропедевтику к теме программирование. Из таблицы видно, что во всех трёх рассмотренных учебниках даются различные определения понятия «алгоритм», что еще раз подтверждает отсутствие строгого понятия данного термина. Не все авторы повторяют свойства алгоритмов, например, в учебнике Семакина И.Г. о них упоминаний нет. Если говорить о других видах алгоритмов и их сложности, то такому критерию соответствует только учебник профильного уровня Калинина И.А. и Самылкиной Н.Н., хотя в данном учебном комплекте, также, как и в других, нет упоминаний о вероятностных алгоритмах, хотя данный вид алгоритмов очень важен в современном мире.

Все изученный учебно-методические комплексы соответствуют Федеральному государственному стандарту среднего общего образования и способствуют развитию алгоритмического мышления обучающихся 10-11 классов на уроках информатики. Однако, они не содержат материалов по выбранной теме факультативного курса. Таким образом, можно сказать, что разработанный факультативный курс будет способствовать не только развитию алгоритмического мышления обучающихся, а так же расширению кругозора и интересов в области информатики и математики, что является неотъемлемой частью формирования всесторонне развитой личности обучающегося.



ГЛАВА 2. ПОСТРОЕНИЕ ФАКУЛЬТАТИВНОГО КУРСА «ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ И ТЕСТЫ НА ПРОСТОТУ»

2.1 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К ФАКУЛЬТАТИВНОМУ КУРСУ «ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ И ТЕСТЫ НА ПРОСТОТУ»

Программа факультативного курса предлагается учащимся 10 - 11 классов общеобразовательных школ. В зависимости от учебной нагрузки курс может быть рассчитан на 14-16 часов.

Ниже приведен примерный учебно-тематический план курса.

Таблица 3. Тематическое планирование.

№ урока	Тема	Часы
1	Введение.	1
2	Алгоритмы и их свойства	2
3	Простые числа. Критерии простоты.	1
4	Решето Эратосфена.	1
5	Теория сравнений.	1
6	Теорема Вильсона	1
7	Критерий Поклингтона	1
8	Тест Ферма.	1
9	Псевдопростые числа	2
10	Тест Миллера-Рябина	1
11	Тест Соловья-Штрассена*	2
12	Итоговое занятие	2
	Всего:	16

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

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

Учебный материал определяет формы организации занятий:

- лекции (обзорные и тематические);

- семинары;

- практикумы;

- самостоятельные исследования;

- консультации.

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

1. C++ Builder 6.0 Enterprise: Самая полная версия популярной финальной системы визуального программирования под Windows для разработки приложений и СУБД. Поддержка интерфейса Win2000/Me/Office2000, технологий Client-Server, Web-приложений, возможность разработки программ для Linux. Поддерживает почти все

операционные системы.

2. Visual C++ 6.0 + SP5 + Русификатор: Это самое эффективное и высокопродуктивное средство разработки на языке C++ для Windows и Web. Visual C++ 6.0 выводит C++ на новый уровень производительности без потери гибкости, быстродействия и контроля. Дополнительно можно использовать SP5 для значительного расширения возможностей среды. Можно использовать русификатор для установки Русского языка.

3. Dev-C++ 4.9: Полнофункциональный редактор и компилятор для написания программ на C++. Содержит все необходимые инструменты для написания, компилирования, проверки и выполнения программ, написанных на С++. Есть также инструмент для создания пакетов установки для ваших программ.

4. C++ Compiler 5.5: Быстрый и надежный 32-битный компилятор от Borland. Включает самую последнюю ANSI/ISO поддержку языка C++, STL (Standard Template Library) Framework и Borland C/C++ Runtime Library (RTL). Прилагается компоновщик исполнения Borland и компилятор ресурсов. C++ Compiler можно использовать как самостоятельно, так и с визуальной средой разработки (Visual Studio или Borland C++ Builder X).

5. Turbo C++ 3.0: Популярнейший в прошлом компилятор языка C++ для DOS. Свою популярность приобрел благодаря удобной среде разработки и общенациональной любви к Borland. К данной версии компилятора написано множество библиотек и приложений. До сих пор используется во многих образовательных учреждениях (не требователен к ресурсам и прост в обучение) [42].

2.2 МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ФАКУЛЬТАТИВНОМУ КУРСУ «ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ И ТЕСТЫ НА РОСТОТУ»

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

Введение (1 ч.)

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

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

Занятие 1. Алгоритмы и их свойства. (2 ч.)

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

Занятие 2. Алгоритм Евклида. Сложность алгоритмов. (1 ч.) Повторение определения наибольшего общего делителя (НОД).

Алгоритм Евклида. Нахождение НОД через алгоритм Евклида. Введение определения сложности алгоритма. Введение понятия вероятностного алгоритма. Создаётся компьютерная программа, вычисляющая НОД двух чисел. На данном занятие учащиеся знакомятся с новыми понятиями. Важной задачей данного занятия является понимание учащимися разницы между применением вероятностных и детерминированных алгоритмов.

Занятие 3. Простые числа. Критерии простоты. (1 ч.)

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

Занятие 4. Решето Эратосфена. (1 ч.)

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

Занятие 5. Теория сравнений. (1 ч.)

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

Занятие 6. Теорема Вильсона. (1 ч.)

Даётся формулировка теоремы Вильсона. Формулировка теоремы Вильсона на языке теории сравнений. Создаётся компьютерная программа, проверяющая число на простоту тестом, основанным на теореме Вильсона. Важной задачей данного занятия является понимание учащимися сложности вычисления факториала, и временных затрат на проверку исследуемых чисел.

Занятие 7. Критерий Поклингтона. (1 ч.)

Формулируется критерий Поклингтона. Выполняется практическая проверка простоты числа по данному критерию. Создаётся компьютерная программа, проверяющая число на простоту по критерию Поклингтона.

Занятие 8. Тест Ферма. (1 ч.)

Формулировка малой теоремы Ферма. Вводится тест Ферма, основанный на малой теореме Ферма. Объяснение работы вероятностных алгоритмов. Создаётся компьютерная программа, проверяющая число на простоту тестом Ферма. Даётся домашнее задание в виде подготовки докладов для изучения следующей темы «Псевдопростые числа».

Занятие 9. Псевдопростые числа (2 ч.)

Вводится понятие псевдопростого числа по модулю некоторого числа и числа Пуле и Кармайкла как частные случаи псевдопростоты натуральных чисел. Заслушиваются доклады на тему занятия.

Занятие 10. Тест Миллера-Рябина. (1 ч.)

Даётся тест Миллера-Рябина. Создаётся компьютерная программа, реализующая тест Миллера-Рябина.

Занятие 11. Тест Соловья-Штрассена*. (2 ч.)

Вводится определение символа Якоби. Приводятся свойства символа Якоби и примеры вычисления. Даётся формулировка теста Соловья- Штрассена. Приводятся примеры выполнения теста. Создаётся компьютерная программа, проверяющая число на простоту тестом Соловья- Штрассена.

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

Занятие 12. Итоговое занятие. (2 ч.)

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

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

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

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

2.3 МАТЕМАТИЧЕСКОЕ СОДЕРЖАНИЕ КУРСА «ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ И ТЕСТЫ НА ПРОСТОТУ»

ЗАНЯТИЕ 1. АЛГОРИТМЫ И ИХ СВОЙСТВА.

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

Алгоритм - это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи [19].

Каждый такой алгоритм должен удовлетворять ряду свойств.

1. Результативность (Конечность), т.е. если исходные данные определены верно, то алгоритм будет выполнен за конечное число шагов - мы либо получим ответ, либо установим, что его нет.

2. Детерминированность (Определенность (точность и понятность)). Каждая команда в последовательности имеет одно и только одно значение. Команда входит в список допустимых команд исполнителя (компьютера).

3. Понятность и дискретность (Ввод и вывод). Алгоритм получает исходные данные и сообщает о результатах работы, а каждый последующий шаг алгоритма определяется предыдущим шагом.

4. Эффективность алгоритма определяется по количеству действий, совершаемых исполнителем алгоритма для решения задачи и объемом памяти, который ему для этих действий требуется [39].

Если последовательность выполняемых действий не удовлетворяет данным свойствам, то мы не можем назвать её алгоритмом.

При всем многообразии алгоритмов в них можно выделить три основных вида:

• линейный;

• ветвящийся;

• циклический.

Все алгоритмы принято представлять в формализованном виде. Это можно сделать следующими способами записи алгоритмов:

— словесным, то есть записью последовательности действий на естественном языке;

— графическим, с помощью специальных графических символов;

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

— табличным, и виде таблицы, в которой фиксируются этапы исполнения алгоритма и результаты исполнения [8].

Упражнение 1. Запишите алгоритм нахождения корней квадратного уравнения табличным и графическим способами.

Решение.

Табличный способ.

Вычислить значение дискриминанта квадратного уравнения: таковым для него называется выражение D = b2 ? 4ac.

Таблица 4.

Условие	D > 0	D = 0	D < 0
Число действительных корней.	два корня	Корень один (два равных или совпадающих корня).	Корней на множестве действительных чисел нет.
Формула	? b ± vb2 ? 4ac x1,2 =2а	b x1 = x2 = ?2а	x = ?

Графический способ.

Рис. 1. Блок-схема алгоритма вычисления корней квадратного уравнения

ЗАНЯТИЕ 2. АЛГОРИТМ ЕВКЛИДА. СЛОЖНОСТЬ АЛГОРИТМОВ.

Упражнение 2. Составить блок-схему нахождения НОД (a,b),

используя алгоритм Евклида. Найти: a) НОД (88,32);

b) НОД (26,130);

c) НОД (733,1998).

Решение.

Наибольший общий делитель (НОД) - это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД [29].

Алгоритм Евклида.

Для целых чисел a и b можно составить алгоритм:



a = b ?q1 + r1 0 ? r1 < b

b = r1 ?q2 + r2 0 ? r2 < r1

r1 = r2 ?q3 + r3 0 ? r3 < r2

? ? ? ? ? ?

rn-1 = rn ?qn+ 1 rn+ 1 = 0

Последний, отличный от нуля, остаток в алгоритме Евклида для пары чисел есть их наибольший общий делитель [26].

Описание алгоритма нахождения НОД.

1. Большее число делим на меньшее;

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла.

3. Если есть остаток, то большее число заменяем на остаток от деления.

4. Переходим к пункту 1.

Составим блок-схему алгоритма нахождения НОД (Рис. 2):



a) НОД (88,32):

b) НОД (26,130):

88/32 = 2 (остаток24), 32/24 = 1 (остаток8), 24/8 = 3 (остаток0), НОД (88,32) = 8.

130/26 = 5(остаток0), НОД (26,130) = 26.

d) НОД (733,1998):

1998/733 = 2 (остаток532), 733/532 = 1(остаток201), 532/201 = 2(остаток130), 201/130 = 1(остаток71), 130/71 = 1(остаток59), 71/59 = 1(остаток12) , 59/12 = 4(остаток11),

Задания.

12/11 = 1(остаток1), 11/1 = 11(остаток0) , НОД (733,1998) = 1.

1. На компьютере составьте программу нахождения корней квадратного уравнения для любых a,b и c.

2. С помощью программы вычислите корни для следующих уравнений:

a) 150x2 + 75x + 16 = 0;

b) 3x2 ? 56x ? 59 = 0;

c) ? 87x2 ? 163x + 250 = 0.

3. На компьютере составьте программу нахождения наибольшего общего делителя для двух чисел a и b.

4. С помощью программы вычислите: a) НОД (156,1688);

b) НОД (782,25985);

c) НОД (259,9856).

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

Сложность алгоритма - это примерная оценка количества ресурсов (шагов исполнения и/или памяти), которые необходимо затратить на решение задачи с помощью этого алгоритма.

Сложность алгоритмов обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком) или количеством времени, необходимых для выполнения всех действий, предписанных алгоритмом [8].

Существует так же ещё один способ классификации алгоритмов. Он базируется на подразделении алгоритмов на детерминированные и вероятностные.

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

Алгоритм называется вероятностным (стохастическим), если выполняется одно из следующих утверждений: результат работы алгоритма является решением поставленной задачи с некоторой вероятностью; алгоритм оканчивает свою работу с некоторой вероятностью; оценка числа шагов алгоритма является случайной величиной [29].

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

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

Что же такое алгоритм с вероятностью ошибки 0,0001? Это такой алгоритм, запуская который 10000 раз, мы получим правильный результат 9999 раз и ошибку всего 1 раз.

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

ЗАНЯТИЕ 3. ПРОСТЫЕ ЧИСЛА. КРИТЕРИИ ПРОСТОТЫ.

Как известно, произведение двух натуральных чисел всегда является натуральным числом. Следовательно, существуют натуральные числа, представляющие собой произведения двух натуральных чисел, больших единицы. Но существуют также натуральные числа, большие единицы, которые не являются произведениями двух натуральных чисел, больших единицы, например, числа 2, 3, 5 или 13. Именно такие числа мы называем простыми.

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

Множество простых чисел обозначается символом P. Таким образом, Р = {2,3,5,7,11,13,17,19,23,29, …}.

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

Множество составных чисел обозначается символом S. Таким образом, S = {4,6,8,9,10,12,14,15,16, 18, …}.

Можно заметить, что всё множество натуральных чисел ? состоит из объединения множества простых чисел P, составных чисел S и единицы. Принято считать, что единица не является ни простым ни составным числом [6].

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

Возникает вопрос, можем ли мы для любого натурального числа проверить, является ли оно простым? Для того, чтобы дать на него ответ, рассмотрим несколько простых алгоритмов, которые помогут нам это сделать.

Метод пробных делений.

Если n - составное то, n = ab, где 1 < a ? b, причем a ? vn. Поэтому для d = 2,3,… ,[vn]мы проверяем, делится ли n на d? Если делитель числа n не будет найден, то n - простое. В противном случае будет найден минимальный простой делитель числа n, т.е. мы даже разложим n на два множителя [4].

Пример.

Проверим, является ли число 37 простым?

[v37]= 6.

Таким образом, d = 2,3,5.

37/2 = 18(остаток1), 37/3 = 12(остаток1), 37/5 = 7(остаток2).

Ни один остаток от деления на d не равен нулю, следовательно, 37 - простое число.

Упражнение 3. Проверьте, являются ли числа 29, 56, 153, 1897 простыми, пользуясь методом пробных делений.

Решение.

Таким образом, d = 2,3,5.

[v29]= 5.

29/2 = 14(остаток1), 29/3 = 9(остаток2), 29/5 = 5(остаток4).

Ни один остаток от деления на d не равен нулю, следовательно, 29 - простое число.

[v56]= 7.

Таким образом, d = 2,3,5,7.

56/2 = 28(остаток0).

Простой делитель найден, следовательно, число 56 - составное. Данный алгоритм для этого числа можно было и не выполнять, заметив, что число 56 - четное, а, следовательно, оно по определению делится на 2.

[v153]= 12.

Таким образом, d = 2,3,5,7,11.

153/2 = 76(остаток1), 153/3 = 51(остаток0).

Простой делитель найден, следовательно, число 56 - составное.

[v1897]= 43.

Таким образом, d = 2,3,5,7,11,13,17,19,23,31,37,41,43.

1897/2 = 948(остаток1), 1897/3 = 632(остаток1), 1897/5 = 379(остаток2), 1897/7 = 271(остаток0).

Простой делитель найден, следовательно, число 1897 - составное. Задания.

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

2. С помощью программы проверьте являются ли числа:

561,1105,1729,2465,2821,6601,8911,10585,15841, 29341 простыми.

Выполнив упражнение 3, можно заметить, что данный метод очень трудоёмкий. Уже на четырёхзначных числах растёт число простых делителей, что для более больших чисел, приведёт к заполнению большого объёма памяти компьютера.

ЗАНЯТИЕ 4. РЕШЕТО ЭРАТОСФЕНА

Если мы хотим составить таблицу всех простых чисел среди чисел 2, 3,

…, N, то нужно сперва вычеркнуть все числа, делящиеся на 2, кроме 2, то есть, начиная с двойки (и не вычеркивая ее), каждое второе натуральное число: 4, 6, 8, … . Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3, то есть, начиная с тройки (и не вычеркивая ее), каждое третье натуральное число: 6, 9, 12, … . Затем взять следующее невычеркнутое число (т.е. 5) и вычеркнуть все последующие делящиеся на него числа (каждое пятое), и так далее. В итоге останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим [23].

Упражнение 4. Выпишите все простые числа на числовом промежутке от 721 до 853.

Решение.

Выпишем все нечетные натуральные числа в интервале от 721 до 853.

Четные писать не будем, так как они заведомо не простые.

Выпишем все простые делители p, такие, что: 2 < g ? v853. g:3, 5, 7, 11, 13, 17, 19, 23, 29, g = 2 не выписываем, поскольку все чётные числа мы уже выбросили. Для каждого из выписанных g найдём наименьшее x, x ? 721, делящиеся на g.

Для g = 3 это число 723. А далее все числа вида 723+3k тоже будут делиться на 3. Такие числа в нашем наборе это: 723, 729, 735, 741, 747, 753, 759, 765, 771, 777, 783, 789,795, 801, 807, 813, 819, 825, 831, 837, 743, 849.

Затем вычеркиваем все числа, которые делятся на 5. По признаку делимости, это те числа, которые оканчиваются 0 или 5, то есть первое такое число - это 725. А далее все числа вида 725+5k тоже будут делиться на 5. Такие числа в нашем наборе это: 725, 735, 745, 755, 765, 775, 785, 795, 805, 815, 825, 835, 845.

Теперь вычеркиваем все числа, которые делятся на 7. Первое такое число из нашего промежутка - это 721, а остальные можно получить как 721+7k (или 721+14k), в таком случае мы не получим чётных чисел, которые мы изначально отбросили).

Так как число 737 делится на 11, то на 11 делятся числа: 759, 781, 803, 825, 847. Вычеркиваем их. На 13 делится 741, значит на 13 делится 767, 793, 819, 845. Вычеркиваем их. На 17 делится 731, значит на 17 также делятся 765, 799, 833. На 19 делится 741, значит делится 779 и 817. На 23 делится 759, значит, 805 и 851 тоже делятся на 23. На 29 делится 725, следовательно, 783 и 841 тоже делятся на 29.

Вычеркнув все эти числа, мы получим следующее:

721 723 725 727 729 731 733 735 737 739 741 743

745 747 749 751 753 755 757 759 761 763 765 767

769 771 773 775 777 779 781 783 785 787 789 791

793 795 797 799 801 803 805 807 809 811 813 815

817 819 821 823 825 827 829 831 833 835 837 839

841 843 845 847 849 851 853

Таким образом, на числовом промежутке от 721 до 853 точно 19 простых чисел: 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,

821, 823, 827, 829, 839, 853.

Задания.

Составьте таблицу простых чисел:

a) от 1 до 50;

b) от 200 до 300;

c) от 401 до 450.

ЗАНЯТИЕ 5. ТЕОРИЯ СРАВНЕНИЙ.

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

В дальнейшем мы будем встречаться с таким выражением как «сравнение по модулю числа», выясним, что это значит.

Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки [7].

Пример.

32 и 11 сравнимы по модулю 7, так как

32/7 = 4(остаток4), 11/7 = 1(остаток4).

Существует эквивалентная формулировка: a и b сравнимы по модулю n, если их разность a ? b делится на n, или если a может быть представлено в виде a = b + kn, где k -- некоторое целое число.

Утверждение « a и b сравнимы по модулю n» записывается следующим образом:

a ? b(mod n).

Отношение сравнения обладают многими свойствами обычных равенств. Например, их можно складывать и перемножать:

1. Если a1 ? b1(mod n) и a2 ? b2(mod n) , то

a1 + a2 ? b1+ b2(mod n) и a1a2 ? b1b2(mod n).

Однако, сравнения нельзя делить друг на друга или на другие числа. Пример.

14 ? 20(mod 6).

Если мы сократим 14 и 20 на 2, то получим ошибочное сравнение:

7 ? 10(mod 6).

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

2. Можно делить обе части сравнения на число, взаимно простое с модулем: если aс ? bс(mod n) и НОД (с, n) = 1, то a ? b(mod n).

3. Можно одновременно разделить обе части сравнения и модуль на их общий делитель: если ac ? bc(mod nc), то a ? b(mod n).

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Задания.

1. Сравнить по модулю n числа a и b.

Таблица 5.

a	7	4	2	11	15	42	33	9	48
b	3	17	9	62	91	25	21	53	57
n	3	4	5	7	8	9	11	12	13

2. Верно ли, что если na ? nb(mod x), то a ? b(mod x).

3. Проверьте, что n5 ? n(mod 5) для любого n ? ? .

4. Покажите, что 1,2,3,4 ? 1(mod 5).

5. Используя определение сравнений, составьте на компьютере простейшую программу, определяющую, сравнимы ли два числа по модулю натурального числа.

ЗАНЯТИЕ 6. ТЕОРЕМА ВИЛЬСОНА

Теорема Вильсона гласит:

Натуральное число g > 1 является простым тогда и только тогда, когда (g ? 1) + 1 делится на g [19].

Другими словами, используя теорию сравнений, можно сказать: если для натурального числа g > 1 выполняется условие:

(g ? 1)!? ? 1(mod g), то такое число является простым. Упражнение 5.

Проверим, является ли число 7 простым, используя алгоритм, основанный на теореме Вильсона.

Задания.

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

2. С помощью программы проверьте являются ли числа: 561,1105,1729,2465,2821,6601,8911,10585,15841,29341 простыми.

ЗАНЯТИЕ 7. КРИТЕРИЙ ПОКЛИНГТОНА

Пусть n - натуральное число. Пусть число n ? 1 имеет простой делитель q , причем q > vn ? 1 . Если найдётся такое целое число a , что выполняются следующие два условия:

an-1 ? 1(mod n).

Числа n и a(n-1)/q ? 1 взаимнопросты, то n - простое число [26]. Упражнение 6.

Докажите, что число 31 является простым по критерию Поклингтона. Задания.

1. На компьютере составьте программу, которая бы проверяла простоту числа по критерию Поклингтона.

2. С помощью программы проверьте являются ли числа: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341 простыми.

ЗАНЯТИЕ 8. ТЕСТ ФЕРМА

Данный тест основан на малой теореме Ферма, которая гласит: если натуральное число g является простым, то для любого натурального числа a имеет место сравнение ap ? a(mod g) [29].

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

Другими словами, через остатки, для того, чтобы проверить, является ли число g простым, нужно:

1. выбрать любое натуральное число a;

2. разделить a на g с остатком a/g = b ? g + r;

3. возвести выбранное число a в степень g;

4. разделить ap на g с остатком ap/g = c ?g + m;

5. cравним получившиеся остатки. Если m = r , то g - вероятно простое число. В противном случае число g является составным.

Для того, чтобы проверить вероятностным алгоритмом, является ли целое число n простым, выбирают случайное число n , 1 < a < n , и проверяют условие алгоритма. Если число n не проходит тест по основанию a , то алгоритм выдает результат «Число n составное», и n действительно является составным.

Рис. 3. Схема вероятностного алгоритма проверки числа на простоту. Упражнение 7.



Если же n проходит тест по основанию a, ничего нельзя сказать о том, действительно ли число n является простым. Последовательно проведя ряд проверок таким тестом для разных a и получив для каждого из них ответ «Число n , вероятно, простое», можно утверждать, что число n является простым с вероятностью, близкой к 1. После t независимых испытаний вероятность того, что составное число n будет t раз объявлено простым (вероятность ошибки), не превосходит 1 . 2t

Проверим простоту числа 3, используя три случайных a. Через остатки.

Пусть a = 13.

1. 13/3 = 4(остаток1),m = 1;

2. 133 = 2197;

3. 2197/3 = 732(остаток1),r = 1;

4. m = r, 3 - простое число. Пусть a = 154.

1. 154/3 = 51(остаток1),m = 1;

2. 1543 = 3652264;

3. 3652264/3 = 1217421(остаток1),r = 1;

4. m = r, 3 - простое число. Пусть a = 62.

1. 62/3 = 20(остаток2),m = 2;

2. 623 = 238328;

3. 238328/3 = 79442(остаток2),r = 2;

4. m = r, 3 - простое число. На языке сравнений.

133 ? 13(mod 3),

2197 ? 13(mod 3),

1 ? 1(mod 3).

Сравнение верно, следовательно, 3 - простое число.

1543 ? 154(mod 3),

3652264? 154(mod 3),

1 ? 1(mod 3).

Сравнение верно, следовательно, 3 - простое число.

623 ? 62(mod 3),

3652264 ? 62(mod 3),

2 ? 2(mod 3).

Сравнение верно, следовательно, 3 - простое число. Задания.

1. Проверьте простоту числа 5, используя 1, 2, 3 случайных a.

2. Проверьте «простоту» числа 6, используя 1, 2, 3 случайных a.

3. На компьютере создайте программу проверки числа на простоту тестом Ферма.

4. С помощью созданной компьютерной программы проверьте простоту числа 17, используя 2, 4, 6 случайных чисел a.

5. С помощью созданной компьютерной программы проверьте являются ли числа: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341 простыми.

ЗАНЯТИЕ 9. ПСЕВДОПРОСТЫЕ ЧИСЛА.

Введем теперь новое понятие: Составное число x называется псевдопростым по основанию a , если a и x взаимно-просты, и as-1 ? 1(mod x). Дело в том, что всегда имеется вероятность того, что проверенное нами число при помощи теста Ферма - только псевдопростое.

Если основание a = 2 , то такие псевдопростые числа называются числами Пуле. Наименьшее число Пуле равно 341. Оно составное, так как представимо в виде 11•31, но несложно убедиться, что оно удовлетворяет условиям малой теоремы Ферма: 234O ? 1(mod 341).Последовательность чисел Пуле начинается с элементов 341, 561, 645, 1105, 1387, … .

Натуральное число х, которое является псевдопростым для всех допустимых (то есть, взаимно-простых с x) значений a называется числом Кармайкла. Натуральное число n является числом Кармайкла тогда и только тогда, когда n бесквадратно, и, для любого простого делителя р числа n, g ? 1 делит n ? 1.

В 1910 году Кармайкл нашел первое и наименьшее такое число, 561. (Что 561 является числом Кармайкла, легко видеть из предыдущей теоремы: действительно, 561=3•11•17 бесквадратно, и 2/560,10/560,16/560.)

В 1910 году Кармайкл нашел первое и наименьшее такое число, 561. (Что 561 является числом Кармайкла, легко видеть из предыдущей теоремы: действительно, 561=3•11•17 бесквадратно, и 2/560,10/560,16/560.)

Число (6к+1)(12к+1)(18к+1) является числом Кармайкла, если все три указанных множителя являются простыми.

Существует бесконечно много чисел Кармайкла. Именно, для достаточно большого n существует приблизительно n2/7 чисел Кармайкла между 1 и n.

Однако, при движении вправо по числовой оси, числа Кармайкла становятся очень редки. Например, существует 1401644 чисел Кармайкла между 1 и 1016 (приблизительно одно на 700 миллионов чисел) [7].

ЗАНЯТИЕ 10. ТЕСТ СОЛОВЬЯ-ШТРАССЕНА.

Тест простоты Соловья?Штрассена опирается на свойства символа Лежандра. Для данного нечетного простого числа р и данного целого a числа a, взаимно простого с р, символ Лежандра (p) равен, по определению, 1, если a является полным квадратом по модулю р, т. е. для некоторого 2 целого xO имеет место сравнение xO ? a(mod g);в этом случае число a называется квадратичным вычетом по модулю р. В противном случае символ a Лежандра (p) равен ?1, а число a называется квадратичным невычетом по модулю р.

a p--1

Эйлер доказал, что (p) = a 2 (mod g) . Этот факт известен как критерий Эйлера и играет важную роль в теории чисел.

Таким образом, если мы хотим выяснить, является ли данное натуральное число n простым, мы случайным образом выбираем число a из промежутка[2,n ? 1] и проверяем выполнимость сравнения ? a n n--1 2 (mod n).

Если сравнение не имеет места для данного a, то n является составным. Если сравнение имеет место для нескольких значений a, мы говорим, что, с большой долей вероятности, n является простым. В отличие от теста Ферма, для каждого составного n по меньшей мере половина всех чисел a ? [2,n ? 1] являются «свидетелями» того, что n составное, откуда следует, что вероятность объявить составное число n простым после того, как t случайным образом выбранных чисел a характеризовали его как простое, не превосходит 2-t.

Сложность теста Соловья?Штрассена определяется сложностью вычисления символа Якоби и равна 0(log3n) [26].

ЗАНЯТИЕ 11. ТЕСТ МИЛЛЕРА-РЯБИНА.

Еще одним вероятностным алгоритмом проверки числа на простоту является тест Миллера-Рябина. На сегодняшний день данный тест является более эффективным и чаще используемым.

Данный тест опирается на проверку ряда равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает, что число составное.

Для теста Миллера-Рябина используется следующее утверждение: Пусть n > 2 . Представим число n ? 1 в виде n ? 1 = 2sd , где d - нечётно. Тогда если n - простое число, то для любого a , целого числа, выполняется одно из условий:

1. ad ? 1(mod n);

2. cуществует такое r, 0 ? r < s, что, a2rd ? ? 1(mod n).

Если утверждение (условие 1 или 2) выполняется для некоторых чисел a и n (не обязательно простого), то число n является вероятно простым. При случайно выбранном a вероятность ошибочно принять составное число за простое составляет 25%, но её можно уменьшить, выполнив проверки для других a.

В случае, когда оба условия не выполняются для выбранных чисел, число n является составным [6].

Упражнение 8.

Проверьте тестом Миллера-Рябина, является ли число 221 простым. Решение.

n = 221,n ? 1 = 220 = 22 ? 55,тогда, s = 2,d = 55.

Произвольно выберем такое число a , что 0 < a < n . Допустим a =

174. Проверим выполнение условий:

a20d(mod n) = 17455(mod 221) = 47 ? 1,n ? 1, a21d(mod n) = 17411O(mod 221) = 220 = n ? 1.

Так как 220 ? ? 1(mod 221),то 221 вероятно простое число. Допустим a = 137. Проверим выполнение условий:

a20d(mod n) = 13755(mod 221) = 188 ? 1,n ? 1, a21d(mod n) = 13711O(mod 221) = 205 ? n ? 1.

Так как не выполняются условие, то число 221 составное. Задания.

1. На компьютере составьте программу, выполняющую проверку простоты числа тестом Миллера-Рябина.

2. С помощью программы проверьте являются ли числа: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341 простыми.

ЗАНЯТИЕ 12. ИТОГОВОЕ ЗАНЯТИЕ.

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

• метод пробных делений;

• теорема Вильсона;

• критерий Поклингтона;

• тест Ферма;

• тест Соловья-Штрассена;

• тест Миллера-Рябина.

Если вы были внимательны, то обратили внимание, что с помощью данных программ были произведены проверки простоты для одного и того же набора чисел: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341.

Задания.

1. Выберете любые три теста проверки чисел на простоту (2 детерминированных и 1 вероятностный).

2. Измените код программы так, чтобы вместе с результатом проверки программа выдавала количество времени, затраченное на реализацию.

3. Составьте сводную таблицу для ряда чисел: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, с указанием затрат времени у каждого теста проверки простоты числа.

4. На основе полученной таблица сделайте выводы.

2.4 РЕЗУЛЬТАТЫ ОПЫТНОЙ ПРОВЕРКИ

Экспериментальная проверка полученных результатов проводилась во время педагогической практики в 2017 году в государственном бюджетном образовательном учреждении города Москвы «Школа № 1253 с углублённым изучением иностранного языка».

В школе к экспериментальным занятиям привлекались ученики 10 класса. Для проведения эксперимента были разработаны необходимые методические материалы для учителей и материалы для учеников.

Весь эксперимент был разбит на следующие этапы.

1. Констатирующий эксперимент.

2. Поисковый эксперимент.

3. Обучающий и контролирующий эксперимент.

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

Анкета №1 (нужные ответы подчеркните).

1. Ваше отношение к предмету «Информатика»:

1) самый любимый предмет;

2) занимает равное место среди других предметов, изучаемых в школе;

3) нелюбимый предмет (укажите причину);

4) иной вариант (запишите).

2. Ваше отношение к предмету «Математика»:

2) занимает равное место среди других предметов естественного цикла;

3) занимает равное место среди других предметов, изучаемых в школе;

4) нелюбимый предмет (укажите причину).

3. Что Вам интереснее всего при изучении информатики:

1) теория;

2) работа над практическими за компьютером в парах;

3) самостоятельное выполнение практических за компьютером;

4) практическое применение своих знаний;

5) исторические сведения.

4. Что Вам интереснее всего при изучении математики:

1) теория;

2) решение задач всем классом;

3) самостоятельное решение задач;

4) практическое применение своих знаний;

5) исторические сведения.

5. Ваше участие во внеклассной и внешкольной работе по информатике:

1) посещаю факультатив по информатике;

2) посещаю другой факультатив;

3) посещаю подготовительные курсы по информатике в ВУЗе или училище;

4) посещаю подготовительные курсы по информатике в ВУЗе или училище и посещаю факультатив по информатике.

6. Ваше участие во внеклассной и внешкольной работе по математике:

1) посещаю факультатив по математике;

3) посещаю подготовительные курсы по математике в ВУЗе или училище;

4) посещаю подготовительные курсы по математике в ВУЗе или училище и посещаю факультатив по информатике.

7. Если посещаете факультатив по информатике, укажите причину:

1) углубление знаний по информатике;

2) расширение знаний по информатике, т.е. сверх программы;

3) подготовка к вступительным экзаменам в ВУЗ;

4) другие причины (укажите какие).

8. Если посещаете факультатив по математике, укажите причину:

1) углубление знаний по математике;

2) расширение знаний по математике, т.е. сверх программы;

3) подготовка к вступительным экзаменам в ВУЗ;

4) другие причины (укажите какие).

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

1) Да.

2) Нет.

Анкетированием было охвачено 64 учащихся. Результаты анкетирования представлены в таблице 6.



Таблица 6.

Вопросы => Ответы	1	2	3	4	5	6	7	8	9
1)	14%	21%	21%	24%	15%	29%	25%	24%	37%
2)	43%	36%	36%	38%	55%	7%	11%	12%	63%
3)	30%	25%	7%	6%	12%	31%	50%	55%	-
4)	13%	18%	18%	17%	18%	19%	14%	9%	-
5)	-	-	18%	15%	-	-	-	-	-

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

Среди учащихся, проявивших интерес к факультативным занятиям, было проведено отдельное анкетирование.

Анкета №2 (нужные ответы подчеркните).

1. Алгоритмом называется:

1) программа в машинных кодах;

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

3) указание на выполнение действий;

4) всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

2. Укажите свойства, которыми должен обладать любой алгоритм.

1) Понятность.

2) Эффективность.

3) Результативность.

4) Детерминированность.

5) Конечность.

6) Массовость.

7) Все, перечисленные выше.

3. Что из перечисленного не является алгоритмом?

1) Вычисление корней квадратного уравнения.

2) Рецепт приготовления омлета.

3) Вычисление периметра прямоугольника.

4) Всё, перечисленное выше.

4. Постройте блок-схему нахождения наибольшего общего делителя двух чисел.

1) Блок-схема построена верно.

2) Блок схема построена не верно.

5. Дайте определение простого числа.

1) Ответ дан верно.

2) Ответ дан не верно.

6. Является ли число 117 простым? Ответ обоснуйте.

1) Да.

2) Нет.

7. Какие способы/алгоритмы/критерии проверки простоты числа вы знаете?

1) Да, знаю, это: … .

2) Не знаю ни одного.

Результаты анкетирования приведены в таблице 7.

Таблица 7.

Вопросы Ответы	1	2	3	4	5	6	7
1)	7%	--	21%	36%	58%	61%	0%
2)	36%	--	27%	64%	42%	39%	100%
3)	29%	--	13%	--	--	--	--
4)	14%	--	29%	--	--	--	--
5)	--	--	--	--	--	--	--
6)	--	--	--	--	--	--	--
7)	--	23%	--	--	--	--	--

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

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

На втором этапе эксперимента, поисковом, решались следующие задачи:

1. Отбор содержания элективного курса «Теоретико-числовые алгоритмы и тесты на простоту» с помощью научно-методической и психолого-педагогической литературы.

2. Уточнение программы элективного курса «Теоретико-числовые алгоритмы и тесты на простоту» отвечающего одновременному решению образовательных, воспитательных и развивающих задач обучения.

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

Занятие №1: Алгоритмы и их свойства.

Занятие №2: Простые числа. Критерии простоты. Занятие №3: Решето Эратосфена.

Занятие №4: Теория Сравнений. Занятие №5: Теорема Вильсона. Занятие №6: Критерий Поклингтона.

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