close

Вход

Забыли?

вход по аккаунту

ВАШ рекламный БЮДЖЕТ;pdf

код для вставкиСкачать
Алгоритмы и программы
Хайруллин Альфред
[email protected]
Введение
Научная дисциплина.
I
Как может быть основана научная дисциплина
I
Каковы основные структурные элементы научной
дисциплины
Дать определение термину - описать его так, чтобы тот, кто
никогда его не видел смог определить является предмет им
или нет. Причем использовать только термины с
закрепленными значениями
Аксиомы - основные компоненты науки. Это понятия,
спецификации, факты в достоверности и истинности которых
нас настоятельно убедили. Хотя доказать их правильность нет
никакой возможности.
2 / 10
Научная эйфория конца XIX века.
Давид Гильберт. Существование метода решения всех
математических проблем
I
Всё в математике может быть создано из конечного
множества соответствующих аксиом
I
Такая математика полна. Каждое утверждение
выраженное на языке этой математики может быть либо
доказано, либо опровергнуто
I
Существует метод определения верности любого
утверждения
Метод решения задачи описывает результативный путь
ведущий к её решению. Данное описание должно содержать
набор команд, которые может выполнить любой человек.
3 / 10
Конец эйфории.
Курт Гедель. Теорема о неполноте
I
Не существует совершенной, рациональной
математической теории
I
Метода (алгоритма) автоматического доказательства
математической теории не существует.
Предпосылки возникновения информатики
До Геделя люди представляли методы решения определенных
задач. Но как доказать, что не существует алгоритма решения
задачи? Доказать не существование объекта, без описания
этого объекта невозможно. Надо описать понятие алгоритм, а
затем можно показать, что для некоторых задач не существует
алгоритма их решения.
4 / 10
Алгоритм
Требования к алгоритму
I
Точное описание действий
I
Описание должно быть абсолютно однозначное
I
Результат одинаков для всех исполнителей
Компьютерный алгоритм
Компьютер умеет складывать, умножать и выполнять другие
арифметические действия над числами. Кроме этого он может
сравнить два числа, прочитать входные данные и вывести
результат.
Требование к компьютерному алгоритму
Он должен работать правильно для каждой возможной задачи.
Работать правильно - это значит заканчивает работу за
определенной время и выводит верный результат.
5 / 10
Теория алгоритмов
Конструктивный объект
Конструктивным объектом называется такой объект, который
может быть полностью описан при помощи конечной
последовательности символов.
Конструктивное пространство
Конструктивным пространством называется множество всех
конструктивных объектов одинакового вида
Вычислимая функция
Вычислимой функцией называется функция из одного
конструктивного пространства в другое конструктивное
пространство, для которой существует алгоритм, позволяющий
по описанию любого аргумента получить описание значения
функции на этом аргументе.
6 / 10
Частично вычислимая функция
Пусть Σ - конечный алфавит. Частичная функция F : Σ∗ → Σ∗
частично вычислимой, если существует алгоритм,
перерабатывающий любое слово w из области определения f в
слово f (w) и не заканчивающий свою работу, если он получает
на вход слово не принадлежащее области определения f .
Вычислимая функция
Функция F : Σ∗ → Σ∗ называется вычислимой, если она
частично вычислима и всюду определена.
Перечислимое множество
Перечислимое множество — множество конструктивных
объектов, все элементы которого могут быть получены с
помощью некоторого алгоритма
7 / 10
Машина Тьюринга
Машина Тьюринга состоит из бесконечной и ограниченной с
одного(левого) конца рабочей ленты разбитой на ячейки, в
каждой из которой может быть записан символ некоторого
конечного алфавита и управляющего устройства, способного
находиться в одном из множества состояний. Число возможных
состояний управляющего устройства конечно и точно задано.
Управляющее устройство работает согласно правилам
перехода, которые представляют алгоритм, реализуемый
данной машиной Тьюринга. Каждое правило перехода
предписывает машине, в зависимости от текущего состояния и
наблюдаемого в текущей клетке символа, записать в эту клетку
новый символ, перейти в новое состояние и переместиться на
одну клетку влево или вправо. Некоторые состояния машины
Тьюринга могут быть помечены как терминальные, и переход в
любое из них означает конец работы, остановку алгоритма.
8 / 10
Программа для машины Тьюринга
Конфигурация машины Тьюринга
Программа машины Тьюринга
9 / 10
Спасибо за внимание
10 / 10
1/--страниц
Пожаловаться на содержимое документа