XVI Международная студенческая научная конференция Студенческий научный форум - 2024

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

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

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

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

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

Одним из популярных наивных алгоритмов является алгоритм Байеса.

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

Рис. 1. Фомула теоремы Байеса.

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

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

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

Для окончательного понимания эффективности работы наивных алгоритмов реализуем сравнение двух алгоритмов сортировки - пузырьком и методом вставок. Программа написана на языке c++ и является консольным приложением. Для работы использовалась среда разработки «Visualstudio 2019»

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

Рис. 2. Листинг алгоритма сортировки пузырьком.

Вторым алгоритмом который мы будем сравнивать будет алгоритм сортировки вставками. Этот алгоритм не считается наивным.

Рис. 3. Листинг алгоритма сортировки вставками.

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

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

• Наименование алгоритма;

• отсортированный массив - для подтверждения того, что сортировка действительно была выполнена;

• время выполнения;

• количество перестановок.

Рис. 4. Результат работы программы при работе с небольшим массивом.

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

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

Рис. 5. Работа алгоритмов с более большим массивом.

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