пользователей: 21231
предметов: 10456
вопросов: 177504
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Понятие алгоритма. Тезис Черча.

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

Х – множество исходных данных.

а€X|->A(a) - результат и |=Ф(А(а))

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

Х – множество исходных данных.

аÎ Х |® А(а) – результат и |=Ф(А(а))

Если результат не может быть получен, то говорят, что алгоритм не м.б. применим к полученным данным, либо результат не определен.

Характерные черты:

  1. Детерменированность(т.е. результат и шаги однозначно определяются по исходным данным)
  2. Дискретность(действия осуществляются по нумерации: шаг1, шаг2…)
  3. Элементарность шагов
  4. Массивность

Способы:

  1. Нормальные алгоритмы Маркова(Алгоритм – последовательность замен)
  2. Машины Тьюринга(Алгоритм – вычисления на машине Тьюринга)
  3. Алгоритм – частично-рекурсивных функций.

Подходы имеют один результат.

Если результат не может быть получен, то говорят, что алгоритм не м.б. применим к полученным данным, либо результат не определен.

Характерные черты:

  1. Детерменированность(т.е. результат и шаги однозначно определяются по исходным данным)
  2. Дискретность(действия осуществляются по нумерации: шаг1, шаг2…)
  3. Элементарность шагов
  4. Массивность

Способы:

  1. Нормальные алгоритмы Маркова(Алгоритм – последовательность замен)
  2. Машины Тьюринга(Алгоритм – вычисления на машине Тьюринга)
  3. Алгоритм – частично-рекурсивных функций.

Подходы имеют один результат.

Тезис Чёрча:

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

 

 


23.01.2014; 11:06
хиты: 0
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь