Презентация, доклад на тему Алгоритмическое решение задач, анализ алгоритмической сложности

Ермагамбетова Гульмира Нурлановна

алгоритмов

автоматы; машины Тьюринга

типы алгоритма

2. Показать структуру алгоритма

4. Рассмотреть машину Тьюринга

обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных.

программы

о задаче;
- фоpмулиpовка условия задачи;
- определение конечных целей решения задачи;
- определение формы выдачи результатов;
- описание данных (их типов, диапазонов величин, структуры и т.п. ).

анализ существующих аналогов;
- анализ технических и программных средств;
- pазpаботка математической модели;
- разработка структур данных.

алгоритма;
- выбор формы записи алгоритма (блок-схемы, псевдокод и др.);
- выбор тестов и метода тестирования;
- проектирование алгоритма.

способов организации данных;
- запись алгоритма на выбранном языке пpогpаммиpования.

отладка семантики и логической стpуктуpы;
- тестовые расчеты и анализ результатов тестирования;
- совершенствование пpогpаммы.

Анализ и исследование задачи, модели
- Разработка алгоритма;
- Пpогpаммиpование
- Тестирование и отладка.

решения конкретных задач;
- составление документации к решенной задаче, к математической модели, к алгоритму, к пpогpамме, к набору тестов, к использованию.

производимый по результатам ее прогона на компьютере.

Тестирование - это испытание, проверка правильности работы программы в целом либо ее составных частей.

и явных ошибок кодирования;
- в процессе же тестирования проверяется работоспособность программы, не содержащей явных ошибок.

Тестирование устанавливает факт наличия ошибок, а отладка выясняет причину неправильной работы программы.

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

работах Гильберта, Черча, Клини, Поста, Тьюринга.

Формы

на основе понятия рекурсивной функции

на основе описания алгоритмического процесса

управляет состоянием памяти.



Основные АМ, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов были предложены в ХХ в.
• Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г.

• Машина Поста (МР) предложена Постом в 1937 г.

• Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.

существует как бы в виде «всем понятной механической процедуры».



Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г.

понятия правильно построенных формул (ППФ) и конечного набора правил преобразования ППФ.
Алгоритм понимается как цепочка применения последовательности правил к начальной ППФ для получения вывода конечной ППФ.
В аксиоматических формальных системах конечные ППФ всегда выводятся из ППФ, которые называются аксиомами.

- Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г.
- λ-исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.

Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г

это единственный процессор.

– это элементы множеств, которые нужно порождать или распознавать.

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

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


Языки программирования содержат оба способа задания функций.

процесса, который управляется состоянием памяти.

вида – ,

Машина Тьюринга

Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ

ячейка может быть пустой.

УГ выбирает и выполняет правила

Если УГ находится в состоянии Si и указатель головки стоит напротив ячейки, где записан символ аi (видит аi), то головка заменяет его на символ аj, переходит в состояние Sj, производит действие dj (Л – сдвигается на ячейку влево, П – сдвигается на ячейку вправо, Н – остается на месте, stop – МТ останавливается).

В начальном такте (t0) УГ находится всегда в состоянии S0, «смотрит» на некоторую ячейку ленты и «ждет» внешнего сигнала «пуск», чтобы начать работу.

результата), выполняется команда (ak, Sk, stop) переводит УГ в конечное состояние и происходит остановка машины;
• неудачное завершение, УГ не может найти правило с условием (ai, Si), ошибка в программе (наборе правил), ошибка в данных. В распознающих МТ неудачные завершение фиксирует «ложность» соответствующего предиката.

Процесс остановки

благополучную ситуацию, когда порождаемое слово может быть бесконечной цепочкой символов. Для распознающей МТ ситуация не предсказуема (либо МТ ещё не нашла значение предиката, либо имеется ошибка в программе).

Процесс «вечной» работы

происходит по условиям (Si, ai), возникшим в ti такт.

удобно показывать на графе «переходов»

вершины, которые соответствуют множеству состояний МТ;
V – множество дуг, которые соответствуют переходам (правилам).из состояния Si в состояние Sj,;

Граф переходов GS замечателен тем, что он содержит все возможные «траектории» работы МТ, которые могут быть сколь угодно длинными (но конечными) и (это основное) определяет логику работы МТ, начиная с начального состояния S0, до момента останова. Граф GS в этом случае задаёт так называемую машину состояний.

Мир, 1989. – 360 с., ил.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. Пер. с англ. под ред. В.В.Мартынюка. – М.: Мир, 1981, 368 c.
Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач. Учебное пособие. СПб.: Питер, 2005. 237 с.: ил.
Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: Построение и анализ / Пер. с англ. под ред. А.Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд., стереотип. – 960 с.: 263 ил.
Дж.Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. Пер. с англ. под ред. С.К.Ландо, Дополнение М.В.Ульянова. – Москва, Техносфера, 2004 – 368 с.
В.С.Новичков, Н.И.Парфилова, А.Н.Пылькин. Алгоритмизация и программирование на Турбо Паскале. Учебное пособие. М.: Горячая линия – Телеком, 2005. 438 с.: ил.
Окулов С.М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2004. 424 с.: ил.
Окулов С.М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний, 2004. 341 с.: ил.
Ставровский А.Б. Первые шаги в программировании. Самоучитель: – М.: Издательский дом “Вильямс”, 2003. 368 с.: ил.

Литература

алгоритмов?
Две формы задач решения алгоритма?
Что такое информационная структура алгоритма?
Какие формы представления алгоритмов существуют?
Что такое процедура структуры?
Машина Тьюринга - представление.

Контрольные вопросы: