Область исследования: Алгоритмы и вычисления…
Тема исследования: Для чего нужны быстрые алгоритмы?
Цель исследования: Выяснить какие задачи в вычислительной математике решают с использованием быстрых алгоритмов.
Гипотеза: Быстрые алгоритмы позволяют вычислить заданную функцию с заданной точностью с использованием как можно меньшего числа битовых операций. Так как основным элементом вычислений является битовая информация, быстрые алгоритмы широко применимы в информатике, программировании и вычислительной математике, для умножения матриц и подсчёта множества различных функций.
Задачи:
- Дать определение быстрого алгоритма и сопутствующих терминов, изучив научную литературу по данной теме. Представить полученный теоретический материал в виде презентации.
- Выяснить, как и в каких сферах применяются принципы быстрых алгоритмов, и раскрыть смысл некоторых видов быстрых алгоритмов.
- Провести опрос для того, чтобы узнать уровень осведомлённости респондентов о данной области вычислительной математики.
- Отметить некоторые хронологические события из истории быстрых алгоритмов в виде временной ленты.
- Провести анализ полученных данных.
Методы исследования: Теоретический анализ и обобщение научной литературы и материалов сети Internet. Анализ работ Анатолия Карацубы.
Этапы исследования:
- Моя первостепенная задача заключалась в том, чтобы познакомиться с теорией быстрых алгоритмов для этого я изучила материалы сети Интернет. Итогом моих поисков является данная презентация, в которой я дала определение быстрых алгоритмов, привела примеры некоторых из них, указала сферы применения.
- Еще одним этапом моего исследования являлся опрос. Основная задача опроса заключалась в том, чтобы выяснить, насколько тесно респонденты знакомы с областью быстрых алгоритмов. По результатам опроса я смогла сделать вывод о том, что большинство респондентов имеет некоторое представление о данной области вычислительной математики, хоть ранее и не слышали о ней.
Сводка по результатам опроса:
Опрошенных: 17 респондентов
Социальная группа: студенты
Возрастная группа: 18-20 лет
1 вопрос
Вы когда-нибудь встречались с таким термином как быстрый алгоритм?
(17 ответов)
Комментарий: 3 респондента из 17, ранее встречались с термином быстрые алгоритмы. Остальные 14 респондентов о нём не слышали.
2 вопрос
В информатике минимальной единицей измерения информации является
(17 ответов)
Верных ответов: 15 из 17
3 вопрос
Какие термины, по вашему мнению, можно отнести к области быстрых алгоритмов?
(17 ответов)
Верных ответов: 7 из 17
4 вопрос
Что вы понимаете под битовой операцией?
(17 ответов)
Верных ответов: 13 из 17
5 вопрос
Как вы считаете, существует ли достаточно быстрый алгоритм умножения матриц, с помощью которого было бы возможно самостоятельно умножить две матрицы примерной размерности 64х64?
(17 ответов)
Верных ответов: 15 из 17
6 вопрос
По вашему мнению заслуги русских советских ученых в области быстрых алгоритмов имеют международное значение и почему?
(17 ответов)
Комментарий: большинство респондентов ответило положительно
7 вопрос
Признаёте ли вы оправданность существования данной области математики, если допустить тот факт, что в основе многих программ, предназначенных для сложных подсчетов, лежат быстрые алгоритмы?
(17 ответов)
Комментарий: большинство респондентов считает, что существование теории быстрых алгоритмов оправдано.
Анализ результатов опроса:
По результатам опроса могу сделать вывод, что хоть ранее большинство респондентов не встречались с теорией быстрых алгоритмов, но они знают определения основных терминов и имеют примерное представление о возможных сферах применения.
- Следующим моим немало важным шагом исследования было изучение истории данного вопроса. Я посчитала, что если предстваить полученную мной информацию в виде временной ленты, можно будет сделать вывод о малом возрасте данной области, в сравнении с историей основных алгоритмов.
Выводы:
При написании моего исследовательского проекта я достигла реализации поставленной цели и доказала выдвинутую гипотезу.
На каждом этапе исследования я смогла сделать важные выводы о сферах применения БА, об уровне осведомленности отдельной социальной группы с этими алгоритмами, о возрасте данной области.
Основным достоинством БА является то, что каким бы не был громоздким процесс вычисления той или иной функции (задачи), его можно сократить. Те ученые, которые разрабатывали эти алгоритмы, и те, которые позже их совершенствовали, внесли огромный вклад в науку. Их труды можно назвать попыткой оптимизации алгоритмов, их усовершенствования.
Замечания:
- Быстрые алгоритмы очень тесно связаны с такими областями как информатика и программирование. Электронно-вычислительная машина может работать гораздо быстрее, благодаря тому, что количество битовых операций минимально и достаточно для вычисления функции.
- Значение БА для алгебры также может показаться незначительным, так как большая часть всех методов вычислений остаётся классической, а БА находят своё применение только в исключительных случаях, как например, Алгоритм Штрассена, предназначенный для умножения больших плотных матриц, начиная, примерно, от 64х64.
- Технологии цифровой обработки информации могут непосредственно использовать БПФ (алгоритм быстрого преобразования Фурье). Первая программная реализация алгоритма БПФ была осуществлена в начале 60-х годов XX века Джеймсом Кули в вычислительном центре IBM под руководством Джона Тьюки, а в 1965 году, ими же, была опубликована статья, посвященная этому алгоритму. Дискретное преобразование Фурье (ДПФ), на сегодняшний день, один из самых распространенных инструментов анализа, который применяется во всех отраслях науки и техники.
- Построение быстрых алгоритмов основано на принципе рекурсивного сведения к задачам меньшего размера. Это открытие сделал советский математик Анатолий Алексеевич Карацуба. Сегодня данный принцип построения быстрых алгоритмов носит название «разделяй и властвуй».
Заключение: Хоть эта область имеет сравнительно молодой возраст, ей есть куда развиваться. Найдется еще немало сфер применения теории БА, так как технологии ХХI века не стоят на месте, а программисты и инженеры всегда будут стремиться усовершенствовать работу ЭВМ.
Ссылки на разработки проекта:
Ссылки на используемые сервисы интернета:
