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

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

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

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

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

Индуктивные функции применяются при решении следующих практических задач:

• обработка очередей;

• обслуживание клиентов;

• обработка больших массивов данных поступающих в систему.

Достоинства применения индуктивных функций:

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

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

Понятие индуктивной функции

Функция называется индуктивной, если её значение для удлинённой (за счёт добавления элемента) последовательности можно выразить через значение этой же самой функции для исходной последовательности и через добавляемый элемент.

Предикат – логическое утверждение, содержащее переменную величину.

Инвариант – предикат, сохраняющий своё значение после исполнения заданных шагов алгоритма.

Инвариант — важнейшее понятие при доказательстве корректности алгоритмов или его фрагмента.

Путь доказательства корректности фрагмента алгоритма:

1) выбираем предикат (или группу предикатов), значение которого истинно до начала исполнения фрагмента;

2) исполняем фрагмент, наблюдая за поведением предиката;

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

Примеры индуктивных функций:

• вычисление суммы группы элементов;

• вычисление произведения группы элементов;

• вычисление наибольшего или наименьшего элемента из последовательности чисел;

• схема Горнера (вычисление значения многочлена);

• поиск элемента в последовательности.

Рассмотрим функции, которые определены на конечных последовательностях произвольной длины (x1, . . . xn)с элементами из множества A, и принимают значение в множестве B. Функция f данного вида называется индуктивной, если существует функция

.

Применение инддуктивных функция при решении задач

Индуктивные функции естественным образом применяются для решения задач специального вида:

• вход: последовательность (n заранее не задано);

• выход:

Функция является параметром и фактически определяет задачу. Тип элементов последовательности зависит от задачи.

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

Такие задачи часто встречаются в реальной жизни. Например, при реализации электронной очереди в банке, заранее неизвестно кто из клиентов придёт по какому вопросу, и нужно распределять всех клиентов по сотрудникам по мере прихода.

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

Алгоритмы для таких задач называют онлайн-алгоритмами. То есть, онлайн-алгоритм вычисляет значение после считывания каждого элемента

Заметим, что если алгоритм на каждом шаге вычисляет индуктивную функцию, то это онлайн алгоритм.

Если же он вычисляет индуктивное расширение , то он не обязательно онлайн – для того, чтобы стать онлайн-алгоритмом, ему нужно ещё на каждом шаге вычислять и значение

Общая схема вычисления значения индуктивной функции на последовательности выглядит следующим образом:

(

вх: последовательность S

)

| дано: последовательность S

| надо: вычислить функцию y = f(S)

начало алгоритма

| y := значение функции f на пустой последовательности;

| встать в начало последовательности S;

| цикл пока в последовательности S есть

| | непрочитанные элементы

| | прочесть очередной элемент

| | последовательности S в (вых:x);

| | y := G(y, x);

| конец цикла

| ответ := y;

конец алгоритма

Таким образом, для каждой конкретной индуктивной функции надо лишь правильно задать ее значение на пустой последовательности (инициализация) и определить, как новое значение функции вычисляется через старое при добавлении к последовательности очередного элемента. Схема вычисления для всех индуктивных функций одна и та же.

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

Список использованных источников

1. Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. - М.:, 2021. - 764 c.

2. Н. Н. Кузюрин и С .А. Фомин. Эффективные алгоритмы и сложность вычислений. 2019.

3. Степанов, Александр От математики к обобщенному программированию / Александр Степанов. - М.: ДМК Пресс, 2018. - 866 c.

4. Страуструп, Бьярне Программирование. Принципы и практика с использованием C++ / Бьярне Страуструп. - Москва: ИЛ, 2023. - 855 c.

5. Т. Кормен, Ч. Лейзерсон, Р. Ривест и К. Штайн. Алгоритмы: построение и анализ. 3-е. М.: Вильямс, 2018.

Код для цитирования: Скопировать