Федеральное агентство связи Государственное образовательное учреждение высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики»

Введение Проверка контрольных работ – не самое простое занятие, даже для профессионального преподавателя. Необходимо внимательно просмотреть ход решения и ответ, найти ошибки и выставить оценку соответственно качеству выполненной контрольной работы. Это сделать очень непросто, если нужно проверить множество работ на различные темы. Организация компьютерного контроля знаний направлена, во-первых, на то, чтобы облегчить работу преподавателя, освободив его от рутины проверки письменных работ (он может посвятить больше времени индивидуальным занятиям со студентами) и, во-вторых, на повышение объективности проводимой проверки и оценки знаний. Контроль знаний обеспечивают специальные компьютерные программы, в которых осуществляется: формирование индивидуального набора контрольных заданий каждому обучаемому; вывод заданий на экран; анализ ответов обучаемого; выставление оценки; хранение результатов контроля и данных о работе студента с обучающей программой, которые могут быть впоследствии использованы преподавателем [7]. Данная дипломная работа представляет собой среду для записи и автоматизированной проверки решения и ответа для контрольной работы на тему «Быстрое умножение чисел». Это одна из самых сложных и трудоёмких контрольных работ в курсе «Теория сложности вычислительных процессов и структур». Проблема оценки количества битовых операций, достаточного для вычисления произведения двух n-значных чисел, является нетривиальной проблемой теории быстрых вычислений. Алгоритм Карацубы [5, 6] является простым и в то же время весьма эффективным способом быстрого перемножения чисел. Важно познакомить студентов с этим алгоритмом, а потом оценить их знания при помощи приложения, описанного в данной дипломной работе. Во второй главе данной дипломной работы описана постановка задачи. Описан алгоритм, который необходимо изучить студентам, а также детали клиент-серверного взаимодействия с базой данных, хранящей результаты решения задач студентами. Также были рассмотрены аналоги, существующие на данный момент, и принято решение о написании данной системы с нуля. В третьей главе содержится перечень средств разработки, которые были выбраны для решения поставленной задачи, указано, по какой причине они оптимальны. В четвёртой главе описаны детали реализации. Там указано, какие классы были разработаны в рамках решения задачи, представлены диаграммы этих классов, описано их взаимодействие. Пятая глава представляет собой руководство пользователя. Там описывается разработанный пользовательский интерфейс, режимы работы приложения, необходимые действия пользователя при работе с системой. В шестой главе описаны требования и необходимые меры, которые предпринимаются в целях обеспечения безопасности жизнедеятельности пользователей персональных компьютеров. Седьмая глава посвящена заключению. Там делаются выводы о том, чего удалось добиться автору, насколько успешно он решил поставленную задачу. Постановка задачи Необходимо перемножить два заданных числа по методу быстрого умножения Карацубы. Затем нужно предоставить пользователю возможность залогиниться под своим именем, ввести решение и ответ, и сравнить их с вычисленными значениями. После этого на основе анализа введённого решения вычисляется оценка. Результаты решения задания пользователем отправляются на сервер, где в дальнейшем хранятся. Алгоритм быстрого умножения Область быстрые алгоритмы появилась в 1960 году, когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был назван «Разделяй и властвуй», другими названия этого метода, используемые в литературе, это метод двоичного разбиения (англ. binary splitting), двоичный поиск, метод бисекции и другие [5]. Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа со сложностью вычисления согласно формуле 2.1: (2.1) При . Первый вариант метода основан на формуле: (2.2) Исходя из формулы 2.3, умножение двух чисел и эквивалентно по сложности выполнения возведению в квадрат. (2.3) Пусть есть -значное число, то есть , (2.4) Где , ; . Будем считать для простоты, что , , . Представляя в виде , (2.5) Где , и , Находим: . (2.6) Числа и являются -значными. Число может иметь знаков. В этом случае представим его в виде , (2.7) где есть -значное число, — однозначное число. Тогда . (2.8) Обозначим - количество операций, достаточное для возведения n-значного числа в квадрат по формуле (2.6). Из формулы (2.6) следует, что для справедливо неравенство: , (2.9) Где есть абсолютная константа. Действительно, правая часть формулы (2.6) содержит сумму трёх квадратов -значных чисел, , которые для своего вычисления требуют количество операций: . (2.10) Все остальные вычисления в правой части формулы (2.6), а именно умножение на , , , пять сложений и одно вычитание не более чем -значных чисел требуют по порядку не более n операций. Отсюда следует формула (2.9). Применяя формулу (2.9) последовательно к (2.11) И принимая во внимание, что , (2.12) Получаем: . Тем самым для количества операций, достаточного для возведения -значного числа в квадрат по формуле (2.6) выполняется оценка: , (2.13) Где . Если же не является степенью двух, то определяя целое число неравенствами , (2.14) Представим как -значное число, то есть полагаем последние знаков равными нулю: , (2.15) При этом остальные рассуждения остаются в силе и для получается такая же верхняя оценка по порядку величины . Второй вариант описывает непосредственное умножение двух -значных чисел, основанное на формуле . (2.16) Пусть, как и раньше , , и — два -значных числа. Представляя и в виде , , (2.17) Где , , , - -значные числа, находим: . (2.18) Или (2.19) И тогда . (2.20) Таким образом, в этом случае формула (2.6) заменяется формулой (2.18). Если теперь обозначить количество операций, достаточное для умножения двух n-значных чисел по формуле (2.18), то для выполняется неравенство (2.9), и, следовательно, справедливо неравенство (2.13). Представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до знаков функции в некоторой точке . Если при вычислении по формуле (2.19) происходит переполнение, используется следующий подход [6]. Предположим, что при вычислении получились не , а -разрядные числа, то есть, и имеют разряд. Обозначим и старшие разряды чисел и соответственно; один из них будет обязательно равен 1. Тогда произведение можно осуществить следующим образом: . (2.21) В случае, когда возникает переполнение, перемножение -разрядных чисел выполняется по формуле 2.21. В ней по-прежнему одно умножение и одно сложение, которое может и не понадобиться. На трудоёмкости это существенно не отражается: или . (2.22) Если разбивать не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения (возведения в квадрат). Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы, однако в данной работе реализуется только метод Карацубы.

Похожие:

	Федеральное агентство связи Государственное образовательное учреждение... Программа составлена в соответствии с требованиями Федерального государственного образовательного стандарта начального общего образования...		Федеральное агентство связи Государственное образовательное учреждение... Когда умцик накопил достаточный опыт и достиг наглядных результатов в практической и научной деятельности, Министерство здравоохранения...
	Федеральное государственное образовательное бюджетное учреждение... ...		Рабочая программа дисциплины «Информатика» Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Поволжский государственный...
	Федеральное агентство по образованию федеральное государственное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Федеральное агентство воздушного транспорта федеральное государственное... Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования
	Федеральное агентство по образованию федеральное государственное... Изотова Елена Анатольевна – учитель биологии муниципальной средней общеобразовательной школы №1 г. Галича		Федеральное агентство по образованию государственное образовательное... Государственное образовательное учреждение высшего профессионального образования «Ставропольская государственная медицинская академия»...
	Федеральное агентство по образованию федеральное государственное... «Теория и практика благотворительной помощи университетам. Зарубежный опыт», выполняемому в рамках «Программы развития сфу на 2007–2010...		Нир научно-исследовательская работа Университет – Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный...
	Федеральное агентство воздушного транспорта московский государственный... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Федеральное агентство связи федеральное государственное образовательное... Университете системы равноправных отношений между студентами, сотрудниками вуза и его администрацией, принимает настоящий Этический...
	Федеральное агентство по образованию государственное образовательное... Утверждены: Ученым советом Федеральным государственным бюджетным образовательным учреждением высшего профессионального образования...		Федеральное агентство по образованию государственное образовательное... Утверждены: Ученым советом Федеральным государственным бюджетным образовательным учреждением высшего профессионального образования...
	Российской Федерации Федеральное агентство по рыболовству Федеральное... Г. Г., Авдеева Е. В., Шеховцев Л. Н., Шибаев С. В., Орлов Е. К., Уманский С. А. Калининград: Федеральное государственное бюджетное...		Федеральное агентство по образованию и науке РФ федеральное государственное... Форма обучения – очная, заочная, заочная (сокращенная) на базе впо, очно-заочная (вечерняя) на базе спо