Содержание
- 2. Элементы теории алгоритмов. Тема 1: Нестрогое определение алгоритма. Тема 2: Рекурсивные функции. Тема 3: Алгоритм как
- 3. Компьютер нужен человеку для решения задач практики. Просматриваются общие моменты в порядке их решения: - во-первых,
- 4. В связи с этим возникает ряд взаимосвязанных задач, требующих разрешения: определение правил обработки информации с учетом
- 5. Начнем с рассмотрения элементов теории алгоритмов. Это рассмотрение будет построено в два этапа; на первом, приводится
- 6. Исторически термин "алгоритм" произошел от фамилии узбекского математика IX века Мухаммеда ибн Муса ал-Хорезми, который впервые
- 7. В связи с этим возникает вопрос: можно ли построить общее и точное определение алгоритма . Алгоритм
- 8. Элементарность шагов: закон получения последующей системы величин из предыдущей должен быть простым и локальным. Какой шаг
- 9. Любая программа есть ни что иное, как запись алгоритма на языке, который может "понять" исполнитель -
- 10. В теоретических подходах к построению строгого определения понятия алгоритма исторически выделились три основные направления. Первое направление
- 11. Данный подход развивался в работах Э. Поста и А. Тьюринга одновременно с упомянутым выше подходом. Доказательство
- 12. 1.Исполнитель алгоритма - это субъект или устройство способные правильно интерпретировать описание алгоритма и выполнить содержащийся в
- 13. При построении алгоритма для такого исполнителя разработчику достаточно указать последовательность интегральных команд, а их преобразование в
- 14. 2. Допустимость нестрогой формализации представления алгоритмов, если исполнителем является человек. 3. Расширение применимости понятия алгоритма на
- 15. Введем ряд определений. Пусть имеются два множества X и У. Если некоторым элементам множества X поставлены
- 16. В данном подходе любой алгоритм, единый для данной числовой функции, вычисляет ее значение, а его элементарными
- 17. Совокупность вычислимых функций для самых разных понимании процессов, удовлетворяющих перечисленным условиям, оказалась одной и той же
- 18. Перечисленные простейшие функции всюду определены и интуитивно вычислимы. Частичные функции, которые можно получить при помощи этих
- 19. Говорят, что функция h получена из функций g, f1, ..., fn суперпозицией (или подстановкой). Символически такая
- 20. Поскольку областью определения функций является множество всех натуральных чисел, частичная функция f, удовлетворяющая условиям (1), существует
- 21. Частичная функция f(x1, ..., xn) называется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции
- 22. Подобным же образом определяется функция многих переменных: fi(x1, ..., xn)=muy[f(x1, ..., xn, y)=0] Для вычисления функции
- 23. Понятие частично рекурсивной функции является одним из главных понятий теории алгоритмов. Значение его состоит в следующем:
- 24. Понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции. Тезис Черча оказался достаточным, чтобы
- 25. Общие подходы. Алгоритмические процессы - это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем
- 26. перед началом работы машине предоставляются исходные данные из области определения алгоритма; за конечное число шагов работы
- 27. Алгоритм - это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом.( В. М.
- 28. Таким образом, все возможные алфавитные преобразования сводится к операции (1) - замене одного знака другим. Именно
- 29. Алгоритмическая машина Поста Пост, в отличие от Тьюринга, не пользовался термином "машина", а называл свою модель
- 30. Условимся обозначать головку знаком "V" над обозреваемой секцией, а метку - знаком "M" внутри секции. Пустая
- 31. Алгоритм как абстрактная машина. Данный перечень должен быть дополнен следующими условиями: команда может быть выполнена только
- 32. В отличие от этой ситуации, остановка по команде является результативной, т.е. она происходит после того, как
- 33. Можно показать, что с помощью машины Поста реализуются (хотя и довольно громоздко) все арифметические действия над
- 34. Алгоритмическая машина Тьюринга Машина Тьюринга состоит из трех частей: ленты, считывающе - записывающей головки и логического
- 35. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака. Головка всегда
- 36. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на
- 37. Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qiaj->q`ia`jDk, т.е. после обзора символа
- 38. Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов да, одну и только
- 39. В зависимости от начальной конфигурации возможны два варианта развития событий: после конечного числа тактов машина останавливается
- 40. Всякий алгоритм может быть задан посредством тьюринговой функциональной схемой и реализован в соответствующей машине Тьюринга. Эта
- 41. Алгоритм задается системой подстановок, которые указывают, какие замены символов необходимо производить и в каком порядке эти
- 42. Алгоритмом в алфавите А называется эффективно вычислимая функция, областью определения которой служит какое-либо подмножество множества всех
- 43. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в
- 44. Различные варианты решения проблемы формулировки точного определения алгоритма , привели к построению так называемых абстрактных алгоритмических
- 45. Основные понятия теории алгоритмов – вычислимая функция и разрешимое множество. Функция называется вычислимой, если имеется алгоритм,
- 46. Рассмотренный тезис Черча, утверждает, что всякая частично рекурсивная функция является вычислимой. Другими словами, если функцию удалось
- 47. Также была доказана теорема о сводимости одной алгоритмической модели к другой, следствием которой явились утверждения типа:
- 48. Задача считается алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова),
- 49. В теории алгоритмов к алгоритмически неразрешимой относится "проблема остановки": можно ли по описанию алгоритма (Q) и
- 50. Неразрешимой оказывается и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который для любых двух алгоритмов (программ)
- 51. Сложность алгоритма. Исполнение любого алгоритма требует определенного объема памяти компьютера для размещения данных и программы, а
- 52. Обсуждать будем временную сложность алгоритмов. Время работы алгоритма удобно выражать в виде функции от одной переменной,
- 53. При этом, безусловно, предполагается, что во всех задачах используется одинаковая схема кодирования входных слов. Различии между
- 54. Для сопоставления в таблице ниже приведены данные о времени решения задач различной сложности. Из приведенных данных
- 55. Из таблицы видно, что, например, для экспоненциального алгоритма с функцией сложности f(n)=2n рост скорости вычислений в
- 56. Сложность алгоритма.
- 57. Сложность алгоритма. Задача считается трудно решаемой, если для нее не удается построить полиномиального алгоритма.
- 58. Формализация представления алгоритмов. Тема 1: Формальные языки. Тема 2: Способы представления алгоритмов. Тема 3: Структурная теорема.
- 59. Формальные языки. Формальная грамматика. Искусственных язык со строгим синтаксисом и полной смысловой определенностью - такие языки
- 60. Формальные языки. Система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка. Формальная
- 61. Формальные языки. Формальная грамматика задается упорядоченной четверкой [T, N, S, Р], где T и N -
- 62. Способы представления алгоритмов. Исполнитель алгоритма Введем понятие формального исполнителя: Формальный исполнитель - субъект или устройство, способные
- 63. Способы представления алгоритмов. система допустимых внутренних состояний; язык представления алгоритма.
- 64. Способы представления алгоритмов. Строчная словесная запись алгоритма В представлении алгоритмов можно выделить две основные формы: символьную
- 65. Способы представления алгоритмов. "Элементарность" действия определяется возможностями исполнителя. Данный способ представления алгоритма следует считать основным, поскольку
- 66. Способы представления алгоритмов. Формула - строчная запись действий, обеспечивающих обработку числовых, символьных или логических данных. Например,
- 67. Способы представления алгоритмов. Помимо указанных приоритетов принимается дополнительное правило: при наличии операций равного приоритета они выполняются
- 68. Способы представления алгоритмов. внешнее оформление: АЛГ - начало алгоритма, ПРОЦ - начало процедуры, КНЦ; - конец
- 69. Способы представления алгоритмов. Язык программирования - искусственный формализованный язык, предназначенный для записи алгоритма для исполнителя "компьютер",
- 70. Пример команд ассемблера: CLA - очистить один из регистров сумматора (аккумулятор); ADD - сложение содержимого ячейки,
- 71. Способы представления алгоритмов.
- 72. Примерами являются язык FORTRAN (FOFtmula TRANsiator) -язык решения сложных научных и инженерных задач (кстати, это был
- 73. Графическая форма записи Другое распространенное название данной формы - блок-схема. В данной форме для представления отдельных
- 74. Способы представления алгоритмов.
- 75. Идеи структурного программирования были высказаны в 1965 г. Э. Дейкстрой, но сведены в некую законченную систему
- 76. каждый блок выполняется не более одного раза; выполняется каждый блок. Поток управления, в котором выполняются оба
- 77. Очевидно несколько блоков, связанных линейным потоком управления, могут быть объединены в один функциональный блок: Второй тип
- 78. Третий тип потока управления называется циклическим - он организует многократное повторение функционального блока, пока логическое условие
- 79. Структурная теорема. каждое простое действие есть стандартный функциональный блок; каждая из описанных трех управляющих структур является
- 80. Структурная теорема. После введенных определений можно сформулировать структурную теорему Бома Джакопини: любой алгоритм может быть сведен
- 81. Структурная теорема. Эффективность метода структурного программирования особенно заметна при создании сложных программ; модульный принцип позволяет разбить
- 83. Скачать презентацию