Презентация на тему: Основы алгоритмизации Часть 2

Основы алгоритмизации Часть 2
Формализация понятия алгоритма
Формализация понятия алгоритма
Формализация понятия алгоритма
Формализация понятия алгоритма
Формализация понятия алгоритма
Понятие алгоритмической разрешимости задач
Методы разработки алгоритмов
Методы разработки алгоритмов
1/9
Средняя оценка: 4.9/5 (всего оценок: 16)
Код скопирован в буфер обмена
Скачать (141 Кб)
1

Первый слайд презентации: Основы алгоритмизации Часть 2

Изображение слайда
2

Слайд 2: Формализация понятия алгоритма

Нормальные алгоритмы Маркова (1940-е): Исходные данные – строки символов, слова. Символы из алфавита А, который может быть пустым. Если имеются два алфавита: А=(1, 2, 3, 4) и В=(1, 2, 3, 4, 5, 6) = > В – расширение алфавита А.

Изображение слайда
3

Слайд 3: Формализация понятия алгоритма

Нормальные алгоритмы Маркова (1940-е): Используя символы алфавита, можно образовывать произвольные последовательности слов: «информатика» = > «инфо», «форма», «мат», «тик», « ик », «а» и т.д., но не «ириска», «морж», «фора», «». При многократном вхождении подстроки в строку, различают первое вхождение.

Изображение слайда
4

Слайд 4: Формализация понятия алгоритма

Нормальные алгоритмы Маркова (1940-е): Пустое слово входит в подстроку несколько раз: перед первой буквой, между буквами, после последней буквой. Подстановка (P,Q) : в исходном слове R находим первое вхождение слова P и заменяем его на Q. Если P в R нет, то к R подстановка ( P, Q ) не применима.

Изображение слайда
5

Слайд 5: Формализация понятия алгоритма

Нормальные алгоритмы Маркова (1940-е): Необходимо: Задать алфавит А нормального алгоритма. Задать множество подстановок в соответствующем порядке. Применить подстановки последовательно. http://cmcmsu.info/1course/alg.schema.nam.htm#

Изображение слайда
6

Слайд 6: Формализация понятия алгоритма

Нормальные алгоритмы Маркова (1940-е): Принцип нормализации: любому алгоритму, использующему в качестве исходных и результирующих данных некоторые слова из одного алфавита А, соответствует эквивалентный ему нормальный алгоритм над алфавитом А.

Изображение слайда
7

Слайд 7: Понятие алгоритмической разрешимости задач

Разрешимые задачи – задачи, для решения которых существуют алгоритмы. Например: найти максимальное из чисел матрицы. Доказанно неразрешимые задачи: Задача о квадратуре круга. Задача трисекции угла. Задача об удвоении куба. Принципиально неразрешимые задачи (парадоксы): Парадокс Рассела. Парадокс лжеца.

Изображение слайда
8

Слайд 8: Методы разработки алгоритмов

Любая задача может быть сформулирована как функция преобразования некоторых исходных данных в выходные данные, f(x)=Y. Как исходные данные, так и функция могут быть достаточно сложными. Разбиение задачи на подзадачи: Разбивать исходные и выходные данные на части или упрощать их. Разбиение – разделение структуры данных на части, упрощение – разложение данных, например, на сумму x = x 1+х2. Тогда f(x1) и f(x2) найти бывает легче, чем f(x). Производить декомпозицию функции f.

Изображение слайда
9

Последний слайд презентации: Основы алгоритмизации Часть 2: Методы разработки алгоритмов

Основные методы разработки алгоритмов: Метод разложения задачи в последовательность разнородных подзадач. Результаты выполнения первой подзадачи становятся входными данными для второй подзадачи и т.д. Метод итераций, т.е. разложение исходной задачи в последовательность однородных подзадач. Метод рекурсии. Метод последовательных приближений. Метод решения обратной задачи. Метод полного перебора. Эвристические методы. Их правильность не доказана.

Изображение слайда