Курсовая работа: Нод и нок многочленов

-м шаге алгоритма сначала вычисляется остаток от деления
на , 0 . Затем, если , то полагаем , . Если же , то полагаем

,

В результате получаем равенство , в котором

.

Нетрудно доказать, что в описанном алгоритме . Однако у описанного алгоритма по-другому оценивается количество шагов. Действительно, из условия , следует, что . Значит, количество шагов алгоритма не превосходит . Эта оценка не сколько меньше оценки, полученной в теореме 1.3 для алгоритма Евклида. Вместе с тем общая оценка сложности алгоритма не изменяется.

Имеется целый ряд алгоритмов вычисления наибольшего общего делителя, в которых операция деления с остатком заменена на операцию деления с остатком на степени двойки. Поскольку данная операция для чисел , представленных в -ичной системе счисления выполняется всего за операций, то достигается выигрыш в сложности каждого шага алгоритма. Однако обычно число шагов данных алгоритмов оказывается больше числа шагов алгоритма Евклида. [3]

Для чисел

сложности таких алгоритмов вычисления обычно оценивается величиной , однако экспериментальные данные свидетельствуют о том, что данные алгоритмы на 20-25% эффективнее алгоритма Евклида.

Пусть даны целые числа . Опишем сначала сам LSBGCD-алгоритм. Вычисляется последовательность упорядоченных пар неотрицательных чисел, где , и если уже вычислена пара , то:

1. 
   Находится число свойством
   
2. 
   Вычисляется
   
3. 
   Если при этом , то полагаем , а если , то полагаем .
   

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

1. 
   
   
2. 
   
   

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

-го шага можно оценить как . Кроме того, из неравенства , вытекает, что .Значит, . Данная оценка числа шагов LSBGCD-алгоритма позволяет получить общую оценку его сложности в виде . [8]

Заключение

Уроки математики углубляют и расширяют знания обучающихся, а также способствуют развитию их интереса к предмету, развитию математических способностей, привитию обучающимся интереса к самостоятельным занятиям математикой, воспитанию и развитию личной инициативы и творческих особенностей.Изучение и углубление знаний по теме «Многочлены» является достаточно необходимым действием, которое позволяет значительно увеличить ценность современного образования и развить способности и стремления обучающихся к научно-исследовательской, а также познавательной деятельности.Тема «многочлены» в курсе алгебры основной школы является одной из наиболее важных тем. Она лежит в основе при изучении формул сокращенного умножения, преобразований выражений и всех других типов выражений. Данная тема широко представлена и на государственных экзаменах, таких как ОГЭ и ЕГЭ. В ходе работы над данной работой были получены следующие результаты:

1. 
   В первой главе рассмотрены общие сведения о многочленах.
   
2. 
   Во второй главе более углубленно рассмотрены НОД, НОК, алгоритм Евклида и способы решения заданий с его помощью.
   

Данная курсовая работа расширит кругозор студентов и обучающихся, которые изучают предмет «Алгебра», также она может быть полезна для учителей математики, для проведения элективных занятий в старшей школе (10-11 класс), профильных классах, с углубленным изучением математических наук. Таким образом можно сделать вывод, что цель работы достигнута в полной мере, а задачи реализованы.

Список используемой литературы

1. 
   Алимов, Ш.А. Алгебра. 8 класс: учебник для общеобразовательных учреждений/ Ш.А. Алимов, Ю.М. Колягин, Ю.В. Сидоров и др. −21-изд. – М.: Просвещение, 2014. – 255 с.: ил.
   
2. 
   Алимов, Ш.А. Алгебра. 9 класс: учебник для общеобразовательных учреждений/ Ш.А. Алимов, Ю.М. Колягин, Ю.В. Сидоров и др. −17-изд. – М.: Просвещение, 2012. – 287 с.: ил.
   
3. 
   Булычева Ю. В., Васильева Т. В., Карпасюк И. В.Алгебра (Булычева, Ю. В. Алгебра : учебное пособие / Ю. В. Булычева, Т. В. Васильева, И. В. Карпасюк. — 2-е изд. — Астрахань : АГТУ, 2020. — ISBN 978-5-89154-699-8. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/195063 (дата обращения: 06.02.2023). — Режим доступа: для авториз. пользователей. — С. 13.).
   
4. 
   Булычева Ю. В., Васильева Т. В., Карпасюк И. В.Алгебра (Булычева, Ю. В. Алгебра : учебное пособие / Ю. В. Булычева, Т. В. Васильева, И. В. Карпасюк. — 2-е изд. — Астрахань : АГТУ, 2020. — ISBN 978-5-89154-699-8. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/195063 (дата обращения: 08.02.2023). — Режим доступа: для авториз. пользователей. — С. 162.).
   
5. 
   Виленкин, Н.Я. Алгебра. 8 класс [Текст]: учебное пособие для учащихся школ и классов с углубленным изучением математики/ Н.Я. Вилен-кин, А.Н. Виленкин, Г.С. Суворов, Ю.А. Дробышев, И.В. Дробышева, А.И.Кудрявцев; под ред. Н.Я Виленкин. – М.: Просвещение, 1998. – 235 с
   
6. 
   Глухов М. М., Круглов И. А., Пичкур А. Б., Черемушкин А. В.Введение в теоретико-числовые методы криптографии (Введение в теоретико-числовые методы криптографии : учебное пособие / М. М. Глухов, И. А. Круглов, А. Б. Пичкур, А. В. Черемушкин. — Санкт-Петербург : Лань, 2022. — ISBN 978-5-8114-1116-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/210746 (дата обращения: 04.02.2023). — Режим доступа: для авториз. пользователей. — С. 16.).
   
7. 
   Глухов М. М., Круглов И. А., Пичкур А. Б., Черемушкин А. В.Введение в теоретико-числовые методы криптографии (Введение в теоретико-числовые методы криптографии : учебное пособие / М. М. Глухов, И. А. Круглов, А. Б. Пичкур, А. В. Черемушкин. — Санкт-Петербург : Лань, 2022. — ISBN 978-5-8114-1116-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/210746 (дата обращения: 07.02.2023). — Режим доступа: для авториз. пользователей. — С. 18.).
   
8. 
   Жук Л. В., Прокуратова О. Н.Практикум по алгебре многочленов. Часть I (Жук, Л. В. Практикум по алгебре многочленов : учебное пособие / Л. В. Жук, О. Н. Прокуратова. — Елец : ЕГУ им. И.А. Бунина, 2019 — Часть 1 — 2019. — 76 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/196020 (дата обращения: 04.02.2023). — Режим доступа: для авториз. пользователей. — С. 40.).
   
9. 
   Звягин А. В.Курс лекций по алгебре. Многочлены (Звягин, А. В. Курс лекций по алгебре. Многочлены : учебно-методическое пособие / А. В. Звягин. — Воронеж : ВГУ, 2018. — 50 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/171159 (дата обращения: 08.02.2023). — Режим доступа: для авториз. пользователей. — С. 20.).
   
10. 
    Игонина Е. В., Прокуратова О. Н.Лекции по теории многочленов (Игонина, Е. В. Лекции по теории многочленов : учебное пособие / Е. В. Игонина, О. Н. Прокуратова. — Елец : ЕГУ им. И.А. Бунина, 2016. — 85 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/195890 (дата обращения: 06.02.2023). — Режим доступа: для авториз. пользователей. — С. 17.).
    
11. 
    Крючкова, В.В. Об опыте работы с правилами в теме «Многочлены»/ В.В. Крючкова//Математика в школе. - 1984. - № 5. – С. 38–39.
    
12. 
    Мартынов Л. М.Алгебра и теория чисел для криптографии (Мартынов, Л. М. Алгебра и теория чисел для криптографии : учебное пособие для вузов / Л. М. Мартынов. — 2-е изд., стер. — Санкт-Петербург : Лань, 2022. — ISBN 978-5-8114-9346-3. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/189446 (дата обращения: 05.02.2023). — Режим доступа: для авториз. пользователей. — С. 171.).
    
13. 
    Рыбин С. В.Дискретная математика и информатика (Рыбин, С. В. Дискретная математика и информатика : учебник для вузов / С. В. Рыбин. — Санкт-Петербург : Лань, 2022. — ISBN 978-5-8114-8566-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/193326 (дата обращения: 06.02.2023). — Режим доступа: для авториз. пользователей. — С. 116.).
    
14. 
    Сикорская Г.А. Алгебра и теория чисел (Сикорская, Г. А. Алгебра и теория чисел : учебное пособие / Г. А. Сикорская. — Оренбург : ОГУ, 2017. — ISBN 978-5-7410-1975-8. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/110642 (дата обращения: 08.02.2023). — Режим доступа: для авториз. пользователей. — С. 52.).
    
15. 
    Тропин М. П. Основы прикладной алгебры (Тропин, М. П. Основы прикладной алгебры : учебное пособие / М. П. Тропин. — 2-е изд., стер. — Санкт-Петербург : Лань, 2020. — ISBN 978-5-8114-5327-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/139282 (дата обращения: 08.02.2023). — Режим доступа: для авториз. пользователей. — С. 101.).
    
16. 
    Черемисина М. И.Избранные вопросы алгебры и теории чисел. Многочлены (Черемисина, М. И. Избранные вопросы алгебры и теории чисел. Многочлены : учебное пособие / М. И. Черемисина. — Оренбург : ОГПУ, 2021. — 65 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/179894 (дата обращения: 07.02.2023). — Режим доступа: для авториз. пользователей. — С. 12.).