Номер 1.11, страница 423 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

1.11.!* Запишите алгоритм, который для функции, заданной таблично, определяет, является ли она обратимой.

Функция является обратимой тогда и только тогда, когда она является биективной. Биекция — это отображение, которое одновременно является инъективным и сюръективным.

1. Инъективность (взаимная однозначность) означает, что разным значениям аргумента соответствуют разные значения функции. Математически: если $x_1 \neq x_2$, то $f(x_1) \neq f(x_2)$. Для функции, заданной таблично, это означает, что все значения во втором столбце (или второй строке), т.е. все значения $y$, должны быть уникальными. Если хотя бы два значения $y$ совпадают, функция не является инъективной и, следовательно, не является обратимой.

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

Таким образом, для функции, заданной таблично, проверка на обратимость сводится к проверке на инъективность, то есть к проверке уникальности всех значений функции.

Алгоритм для определения обратимости функции, заданной таблично:

1. Взять все значения функции (второй столбец или вторая строка таблицы). Пусть это будет массив (список) $Y = \{y_1, y_2, \dots, y_n\}$.
2. Создать пустую структуру данных для хранения уже проверенных значений (например, множество или хеш-таблицу), назовем ее `seen_values`. Использование множества является наиболее эффективным.
3. Начать перебор всех элементов массива $Y$ от первого до последнего. Для каждого элемента $y_i$:
   • Проверить, содержится ли элемент $y_i$ в `seen_values`.
   • Если $y_i$ уже есть в `seen_values`, это означает, что найдено повторяющееся значение. Функция не является инъективной и, следовательно, не обратима. Завершить алгоритм с результатом "Функция не является обратимой".
   • Если $y_i$ отсутствует в `seen_values`, добавить его в эту структуру и перейти к следующему элементу массива $Y$.
4. Если перебор всех элементов массива $Y$ завершен и не было найдено ни одного повторения, это означает, что все значения функции уникальны. Следовательно, функция является обратимой. Завершить алгоритм с результатом "Функция является обратимой".

Пример:
Таблица 1:
x | 1 | 2 | 3
y | 5 | 8 | 2
Значения $Y = \{5, 8, 2\}$ все уникальны. Функция обратима.

Таблица 2:
x | 1 | 2 | 3
y | 4 | 9 | 4
Значения $Y = \{4, 9, 4\}$. Значение 4 повторяется. Функция не обратима.

Ответ: Для определения обратимости функции, заданной таблично, необходимо проверить, являются ли все значения функции (значения $y$) в таблице уникальными. Если все значения уникальны, функция обратима. Если есть хотя бы одно повторяющееся значение, функция не является обратимой.