LOGO Рекурсивные функции Простейшие функции Операция суперпозиции.

Презентация:



Advertisements
Похожие презентации
LOGO Определение машины Тьюринга. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс Это математический объект, а не физическая.
Advertisements

Пример 2 Записать корректно подстановку Решение. Пример 3 Вычислить функцию-константу: Решение.
Вычислимые функции. Частично рекурсивные и общерекурсивные функции 9po-32k Смирнов Кирилл.
ГБПОУ «МСС УОР 2» Москомспорта Преподаватель информатики Володина М.В г.
Логические функции Занятие 6. Компьютерная логика Функция ЕСЛИ.
LOGO Теорема об эффективной счетности множества пар натуральных чисел.
Лекция 1 для студентов 1 курса, обучающихся по специальности Педиатрия К.п.н., доцент Шилина Н.Г. Красноярск, 2012 Тема: Интегральное исчисление.
Системы линейных уравнений Лекция 3. Пусть задана система n линейных уравнений с n неизвестными.
ЛИНЕЙНАЯ ФУНКЦИЯ И ЕЁ ГРАФИК Алгебра 7 класс. Пусть функция задана формулой, где Х у , , ,524,57 Отметим в координатной.
Область определения, Область значений функции Функция математическое понятие, отражающее связь между элементами множеств. Более точно, это «закон», по.
1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление высказываний Высказывание – утверждение о математических.
Презентация к уроку по информатике и икт (9 класс) по теме: Логические выражения и логические высказывания
ФУНКЦИЯ И ЕЁ ГРАФИК Урок - лекция. X Y ОСЬ АБСЦИСС ОСЬ ОРДИНАТ.
Работу выполнили: Сидорова Анжела Соловьева Наталья Захарова Ольга Сафонова Виктория Пискунова Наталья Руководитель: Елоевич Нина Тимофеевна Муниципальная.
Дифференциальные уравнения Срайчук Иван 11 класс КОШ 86.
Технология хранения, поиска и сортировки информации в базах данных
Предел функции Лекция 1. Ведение в Математический анализ – часть математики, в которой функции и их обобщения изучаются с помощью пределов. § Понятие.
Логические задания в ЕГЭ по информатике Учитель информатики первой кв. категории: Леонтьева И.Н. Лицей им. В.В.Карпова с. Осиново, Зеленодольский район.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 16 Тема: Метод математической индукции.
LOGO Необходимость уточнения понятия алгоритм. Длительное время интуитивного понятия алгоритма было достаточно.
Транксрипт:

LOGO Рекурсивные функции Простейшие функции Операция суперпозиции

Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f Такие функции называются вычислимыми

Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции

Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна Простейшие функции Простейшими функциями называются следующие арифметические функции: 1) Нулевая функция О n (x 1, x 2, …, x n ) = 0 O(x) = 0 2) Функция следования (x) = x + 1, x N 3) Функция проецирования (выбора) I m n (x 1, x 2, …, x n ) = x m Вспомните понятие арифметической функции

Замечание Вычислимость функции проецирования обеспечивается нашей способностью найти в строке (x 1, x 2, …, x n ) место с номером m и указать число на этом месте

Пусть заданы арифметические функции: f 1 (x 1, x 2, …, x n ), f 2 (x 1, x 2, …, x n ), …, f m (x 1, x 2, …, x n ), (y 1, y 2, …, y m ) Операция подстановки (суперпозиции) Говорят, что функция (x 1, x 2, …, x n ) получена из функций и f 1, f 2, …, f m операцией подстановки (суперпозиции), если: Обозначение:

Пример 1 Операция подстановки (суперпозиции)

Пример 1 Операция подстановки (суперпозиции)

Правильное применение суперпозиции: необходимо соблюдать требования к набору аргументов каждой функции Операция подстановки (суперпозиции)

Пример 1 Операция подстановки (суперпозиции) Преобразуем функции f 1 и f 2 так, чтобы они удовлетворяли требованиям к аргументам для применения суперпозиции Корректно

Замечание Такое применение функции проецирования предложил К.Гёдель (1934) Все функции f i, i = 1,…m зависят от n переменных, а функция имеет m переменных (по количеству функций f i ) Результат подстановки, функция зависит от n переменных

Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных и применения функции проецирования I m n

Пример 2 Записать корректно подстановку Решение

Пример 3 Вычислить функцию-константу: Решение

Литература 1.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с. 2.Теория алгоритмов / Электронный учебник 3.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. - СПб.: Лань, с.

Нельзя научить, можно научиться