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

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Костанайский Государственный Университет
  им. Ахмета Байтурсынова
  Автор презентации: ст. преподаватель кафедры ИиМ
  Ермагамбетова Гульмира Нурлановна
  

• 

  2 слайд

  Тема:
  Алгоритмическое решение задач, анализ алгоритмической сложности
  

• 

  3 слайд

  Цель:
  Познакомить с понятием алгоритм и его свойствами, изучить основные способы записи алгоритмов
  

• 

  4 слайд

  План Лекции:
  1. Этапы решения задач на компьютере
  2. Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга
  
  

• 

  5 слайд

  Задачи Лекции:
  1. Рассмотреть этапы решения задач на компьютере
  3. Выявить основные типы алгоритма
  2. Показать структуру алгоритма
  
  4. Рассмотреть машину Тьюринга
  

• 

  6 слайд

  Этапы решения задач
  на компьютере
  

• 

  7 слайд

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

• 

  8 слайд

  Этапы решения задач на компьютере
  Постановка задачи
  Пpогpаммиpование
  Разработка
  алгоритма
  Сопровождение программы
  

• 

  9 слайд

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

• 

  10 слайд

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

• 

  11 слайд

  Этапы решения задач на компьютере
  3. Разработка алгоритма
  - выбор метода проектирования алгоритма;
  - выбор формы записи алгоритма (блок-схемы, псевдокод и др.);
  - выбор тестов и метода тестирования;
  - проектирование алгоритма.
  

• 

  12 слайд

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

• 

  13 слайд

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

• 

  14 слайд

  Этапы решения задач на компьютере
  6. Анализ результатов
  решения задачи
  - Анализ и исследование задачи, модели
  - Разработка алгоритма;
  - Пpогpаммиpование
  - Тестирование и отладка.
  

• 

  15 слайд

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

• 

  16 слайд

  Процесс разработки программы
  Разработка программы = Изготовление + Проверка и исправление
  

• 

  17 слайд

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

• 

  18 слайд

  Отладка и тестирование:
  при отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования;
  - в процессе же тестирования проверяется работоспособность программы, не содержащей явных ошибок.
  Тестирование устанавливает факт наличия ошибок, а отладка выясняет причину неправильной работы программы.
  

• 

  19 слайд

  Тест = Некоторая совокупность исходных данных + Точное описание соответствующих этим данным всех результатов работы программы в том виде, в котором эти результаты должны быть выданы.
  

• 

  20 слайд

  2 Основные вычислительные алгоритмы: конечные автоматы; машины Тьюринга
  

• 

  21 слайд

  Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга.
  Формы
  на основе понятия рекурсивной функции
  на основе описания алгоритмического процесса
  

• 

  22 слайд

  Типы алгоритмов
  Алгоритмические машины
  Функции вычислимые алгоритмом
  Исчисления
  

• 

  23 слайд

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

• 

  24 слайд

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

• 

  25 слайд

  Исчисления
  Представляют собой формальные системы, в которых определены понятия правильно построенных формул (ППФ) и конечного набора правил преобразования ППФ.
  Алгоритм понимается как цепочка применения последовательности правил к начальной ППФ для получения вывода конечной ППФ.
  В аксиоматических формальных системах конечные ППФ всегда выводятся из ППФ, которые называются аксиомами.
  
  - Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г.
  - -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.
  Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г
  

• 

  26 слайд

  Структура алгоритма
  

• 

  27 слайд

  Процессорная структура
  Во всех теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор.
  

• 

  28 слайд

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

• 

  29 слайд

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

• 

  30 слайд

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

• 

  31 слайд

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

• 

  32 слайд

  – алфавит рабочих символов
  – алфавит состояний
  – алфавит действий
  - набор правил вида – ,
  Машина Тьюринга
  

• 

  33 слайд

  Интерпретация Машины Тьюринга
  Процессор – в МТ называется управляющей головкой (УГ).
  Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ
  ячейка может быть пустой.
  

• 

  34 слайд

  Интерпретация Машины Тьюринга
  Процесс вычислений происходит по тактам
  в каждом ti УГ выбирает и выполняет правила
  Если УГ находится в состоянии Si и указатель головки стоит напротив ячейки, где записан символ аi (видит аi), то головка заменяет его на символ аj, переходит в состояние Sj, производит действие dj (Л – сдвигается на ячейку влево, П – сдвигается на ячейку вправо, Н – остается на месте, stop – МТ останавливается).
  В начальном такте (t0) УГ находится всегда в состоянии S0, «смотрит» на некоторую ячейку ленты и «ждет» внешнего сигнала «пуск», чтобы начать работу.
  

• 

  35 слайд

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

• 

  36 слайд

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

• 

  37 слайд

  Интерпретация Машины Тьюринга
  Список правил для МТ не упорядочен. Поиск правила происходит по условиям (Si, ai), возникшим в ti такт.
  

• 

  38 слайд

  Машина Тьюринга
  Логическую структуру алгоритма (ЛСА), содержащую все возможные последовательности команд удобно показывать на графе «переходов»
  

• 

  39 слайд

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

• 

  40 слайд

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

• 

  41 слайд

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

• 

  42 слайд

  Спасибо за Внимание!
  Спасибо за Внимание!
  Спасибо за Внимание!