Тетюшкина Е. Н, учитель информатики и ИКТ МОУ СОШ 1. Основы компьютерной алгебры Элективный курс для 9 класса

Пояснительная записка В составе рассматриваемого элективного курса « Основы компьютерной алгебры » формально можно выделить две составляющие : 1)это различные математические теоремы, леммы, следствия, понимание которых ведет к усвоению того, что информатика – это не только ( и не столько !) прикладная наука, но и фундаментальная. 2)это способы построения и реализации алгоритмов, через которые осуществляется связь математической теории с конкретными задачами и дается практическое обоснование изучения математических вопросов. Таким образом, принимая во внимание подобное деление материала курса, учитывая профиль класса, в котором данный курс преподается, и делая упор на различные части курса, можно преподавать его как в физико - математическом, так и в информационном классе. При этом можно преследовать различные цели : с одной стороны, дать учащимся математического класса общее представление о способах практической реализации изучаемой ими теории, а с другой стороны, подвести информатиков к пониманию того, что в основе программ, реализованных на компьютере, всегда лежит основательный математический фундамент, знание которого обеспечивает более эффективную работу программ.

3а основу курса взяты следующие темы образовательного минимума содержания основных образовательных программ по информатике: «Системы счисления»; «Логика и алгоритмы». Цель курса состоит в ознакомлении учащихся с основными понятиями и принципами компьютерной алгебры, что, в свою очередь, является способом формирования у учащихся отношения к информатике как к фундаментальной теоретической науке. Задачи курса: дать учащимся представление о компьютерной алгебре понятия, области применения, основные принципы; продемонстрировать работу основных алгоритмов компьютерной алгебры; научить школьников пользоваться алгоритмами компьютерной алгебры для выполнения различных вычислений; научить школьников реализации некоторых алгоритмов; углубить умения и навыки учащихся по темам « Системы счисления» и «Логика и алгоритмы»; сформировать отношение к информатике как к фундаментальной науке. Формируемые компетенции: использование и разработка алгоритмов компьютерной алгебры для вычислений.

Введение. Место компьютерной алгебры, предмет компьютерной алгебры, особенности, проблемы, задачи компьютерной алгебры. Арифметические вычисления и операции. Арифметические вычисления, вычисления с дробями в общем виде, поиск наибольшего общего делителя (НОД). Представление целых чисел, ограничение переменных в любой системе программирования. Использование массивов для хранения чисел. Операции с «длинными числами»: сложение, вычитание и умножение. Представление и работа с другими алгебраическими объектами. Полином, разреженное и плотное представление, вычисления, представление рациональных, алгебраических и трансцендентных функций. Эффективность алгоритмов. Эффективность, оценка вычислительной сложности, сравнение быстродействия различных алгоритмов нахождения НОД, разрешимая задача. Элементы теории делимости и теории сравнений. Разложение на частное и остаток, свойства делимости, простые числа, соотношение Безу. Основная теорема арифметики, каноническое представление, решето Эратосфена, поиск НОД, взаимно простые числа, НОД по каноническому представлению, свойства НОД. Алгоритм Евклида, сравнение алгоритмов, теорема Дирихле, числа Фибоначчи, теорема Ламе. Сравнение по модулю, класс вычетов по модулю, свойства операции сравнения по модулю, система вычетов, функция Эйлера, обратные числа, свойства арифметических операций по модулю. Системы счисления. Арабская и римская системы счисления. Арифметические операции в позиционных системах счисления. Перевод целой части, перевод дробной части, перевод произвольного числа. Основное содержание курса

Пример занятия: Нахождение НОД (наибольшего общего делителя) с помощью рекурсивной функции Алгоритм решения задачи: Наибольший общий делитель (НОД) чисел 3430 и 1365 – это 35. Другими словами, 35 – наибольшее число, на которое и 3430 и 1365 делятся без остатка. Чтобы убедиться в этом, разложим оба числа на простые сомножители: 3430 = 2 * 5 * 7 * 7 * = 3 * 5 * 7 * 13 и выделим пары общих сомножителей. В данном случае это пары 5 и 7. Наибольший общий делитель – это произведение совпадающих сомножителей; в данном случае это 5 * 7 = 35. Более изящный метод поиска НОД – алгоритм Евклида. Найдем остаток от деления 3430 на 1365: 3430 mod 1365 = 700 Так как этот остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток: 1365 mod 700 = 665 Этот остаток также не нуль, поэтому еще одно деление: 700 mod 665 = 35 И еще одно: 665 mod 35 = 0 Теперь остаток – нуль, следовательно, НОД равен 35.

Программа на языке Паскаль: var a, b, answer: integer; function gcd(m, n: integer): integer; var modulo: integer; begin modulo := m mod n; if modulo = 0 then gcd := n else gcd := gcd (n, modulo) end; begin write('Enter two numbers: '); readln(a, b); answer := gcd(a, b); writeln('Greatest common divisor: ', answer); readln end.