Презентация на тему "ВЫЧИСЛИМЫЕ ФУНКЦИИИ ИХ ПРЕДСТАВЛЕНИЯ В ТЕОРИИ АЛГОРИТМОВ"

Содержание

• 
  Слайд 1

  ВЫЧИСЛИМЫЕ ФУНКЦИИИ ИХ ПРЕДСТАВЛЕНИЯ В ТЕОРИИ АЛГОРИТМОВ

  КВАЛИФИКАЦИОННАЯ РАБОТА СТУДЕНТКИ 5 КУРСА 591 ГРУППЫ ПРОХОРОВОЙ КСЕНИИ

• 
  Слайд 2

  Вычислимые функции

  Формализация понятия алгоритма 1 Рекурсивные функции 2 Изучение темы в школе 3 Программный продукт «Вычислимые функции» 4

• 
  Слайд 3
  

  Цель исследования – изучение теоретических положений вычислимости функций, исследование рекурсивных функций, разработка элективного курса «Вычислимые функции», создание программной поддержки элективного курса «Вычислимые функции», которая является демонстрационной и практической составляющей этого курса.

• 
  Слайд 4

  Формализация понятия алгоритма

  Функция с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий (Верещагин Н.К.) Алгоритм — это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону (программе) из системы величин, имевшихся в предыдущий момент времени (Мальцев А.И.)

• 
  Слайд 5
  

  Классификация алгоритмических моделей: Теория вычислимых функций (Клини, Черч, Гедель) Абстрактные машины (машины Тьюринга, Поста) Комбинаторные модели (алгоритмы Маркова)

• 
  Слайд 6
  

  Требования к понятию алгоритма: Дискретность Детерминированность Элементарность шагов Направленность алгоритма Массовость алгоритма

• 
  Слайд 7

  РЕКУРСИВНЫЕ ФУНКЦИИ

  ПРИМИТИВНО-РЕКУРСИВНЫЕ ФУНКЦИИ

• 
  Слайд 8

  Рекурсивные функции

  Примитивно-рекурсивные 1 Частично-рекурсивные 2 Общерекурсивные 3

• 
  Слайд 9
  

  Базис (элементарные функции): Константа 0 Функции следованияx’ = x +1 Функция выбора где 1

• 
  Слайд 10
  

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

• 
  Слайд 11
  

  Ограниченный оператор минимизации: наименьшему y≤z, такому, чтоP(x1,…,xn, y)истинно, µyy≤zP(x1 ,…, xn,y)=если такое y существует; z в противном случае. Ограниченный оператор минимизации примитивно-рекурсивен!

• 
  Слайд 12
  

  Функция называется частично-рекурсивной, если она может быть построена из простейших функций 0, x’ = x +1, с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и µ-оператора. Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.

• 
  Слайд 13

  Тематическое планирование курса

• 
  Слайд 14

  Программный продукт

  Строка ввода функции Кнопки для работы с функцией Кнопка вызова окна примитивной рекурсии Чтение строки из файла Дерево разложения функции с учетом приоритетов операций

• 
  Слайд 15
  

  Списки для ввода элементарной функции Кнопки работы с окном Доказательство примитивности элементарной функции

• 
  Слайд 16

  Электронное пособие