Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Формализация понятия "алгоритм"

Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Забавная пачка "5000 дублей".
Юмор – настоящее богатство! Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь
60 руб
Раздел: Прочее

ФОРМАЛИЗАЦИЯ ПОНЯТИЯ «АЛГОРИТМ» 1.1. ПОСТАНОВКА ПРОБЛЕМЫПонятие алгоритма, введенное в предыдущем параграфе, можно назвать понятием алгоритма в интуитивном смысле. Оно имеет нечеткий, неформальный характер, ссылается на некоторые точно не определенные, но интуитивно понятные вещи. Например, при определении и обсуждении свойств алгоритма мы исходили из возможностей некоторого исполнителя алгоритма. Его наличие предполагалось, но ничего определенного о нем не было известно. Говоря языком математики, ни аксиоматического, ни исчерпывающего конструктивного определения исполнителя мы так и не дали. Установленные в предыдущем параграфе свойства алгоритмов следует называть эмпирическими. Они выявлены на основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Этих свойств достаточно для практического программирования, для создания обширного круга программ для компьютеров, станков с ЧПУ, промышленных роботов и т.д. Однако, как фундаментальное научное понятие алгоритм требует более обстоятельного изучения. Оно невозможно без уточнения понятия «алгоритм», более строгого его описания или, как еще говорят, без его формализации. Известно несколько подходов к формализации понятия «алгоритм»: • теория конечных и бесконечных автоматов; • теория вычислимых (рекурсивных) функций; • λ-исчисление Черча. Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем - основы теории рекурсивных функций. Идеи λ-исчислений Черча реализованы в языке программирования LISP (глава 3). Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами в предыдущем параграфе. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения. 1.2. МАШИНА ПОСТААбстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат. Машина Поста менее популярна, хотя она значительно проще машины Тьюринга. С ее помощью можно вести обучение первым навыкам составления программ для ЭВМ.

Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V», и головки, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, или проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка («-») находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста, рис.1.16. Рис.1.16. Абстрактная машина ПостаКоманда машины Поста имеет следующую структуру: п Km, где п - порядковый номер команды, K-действие, выполняемое головкой, т - номер следующей команды, подлежащей выполнению. Существует всего шесть команд машины Поста, рис.1.17: Рис.1.1. Команды машины Поста. Ситуации, в которых головка должна наносить метку там, где она уже имеется, или, наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми). Программой для машины Поста будем называть непустой список команд, такой что 1) на п-м месте команда с номером ; 2) номер т каждой команды совпадает с номером какой-либо команды списка. С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют причины останова машины при выполнении программы: 1) останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы); 2) останов при выполнении недопустимой команды; в этом случае останов называется безрезультативным; 3) машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой). Будем понимать под начальным состояние головки против пустой клетки левее самой левой метки на ленте. Рассмотрим реализацию некоторых типичных элементов программ машины Поста. 1. Пусть задано исходное состояние головки и требуется на пустой ленте написать две метки: одну в секцию под головкой, вторую справа от нее. Это можно сделать по следующей программе (справа от команды показан результат ее выполнения): Рис.1.2. Пример элемента программы машины Поста. 2. Покажем, как можно воспользоваться командой условного перехода для организации циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции. Программа будет иметь следующий вид: Команда условного перехода является одним из основных средств организации циклических процессов, например, для нахождения первой метки справа (или слева) от головки, расположенной над пустой клеткой; нахождение слева (или справа) от головки пустой клетки, если она расположена над меткой и т.д. 3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними. Число k представляется на ленте машины Поста идущими подряд k 1 метками (одна метка означает число «О»).

Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Например, запись чисел 3 и 5 на ленте машины Поста будет выглядеть так: Обратим внимание, что используемая в машине Поста система записи чисел является непозиционной. Составим программу для прибавления к произвольному числу единицы. Предположим, что на ленте записано только одно число и головка находится над одной из клеток, в которой находится метка, принадлежащая этому числу: Для решения задачи можно переместить головку влево (или вправо) до первой пустой клетки, а затем нанести метку. Программа, добавляющая к числу метку слева, имеет вид: Программа, добавляющая к числу метку справа, имеет вид: (отличие только в направлении движения головки в первой команде. Проверьте работоспособность этих программ на каких-либо частных примерах). Предположим, что головка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавить единицу. В этом случае программа усложняется. Появится «блок поиска числа» - две команды, приводящие головку в состояние, рассмотренное в предыдущем примере: Ниже - полные тексты программ, добавляющие единицу слева и справа, соответственно: В первом случае не нужно перемещать головку к крайней левой метке числа 4. Приведем программу для сложения целых неотрицательных чисел а и и на машине Поста, когда головка находится над числом а, а число b находится правее числа а на некоторое число клеток. Эта программа реализует следующий алгоритм: первое число постепенно придвигается ко второму до их слияния, а потом стирается одна метка (иначе результат оказался бы на единицу больше правильного). В случае более сложных начальных условий, когда неизвестно, справа или слева от головки (и на какое число клеток) находится число, можно применить такой принцип поиска числа: двигая головку вправо и влево и отмечая метками степень удаления головки от исходного положения, найти число, а потом уже применить известную программу сложения. При этом проверяется, находится ли головка над одной из меток числа и если да, то задача решена. Иначе проверяется, пуста ли секция справа от головки и следующая за ней; если обе пусты, то делается возврат головки на один шаг и ставится метка, а затем такая же операция выполняется слева и по отмеченной дорожке головка возвращается вправо и т.д. до тех пор, пока головка не натолкнется на число, после чего можно применить ранее рассмотренные выше программы: Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют: • неделимые носители информации (клетки - биты), которые могут быть заполненными или незаполненными; • ограниченный набор элементарных действий - команд, каждая из которых выполняется за один такт (шаг). Обе машины работают на основе программы. Однако, в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д. 1.3. МАШИНА ТЬЮРИНГАМашина Тьюринга подобна машине Поста, но функционирует несколько иначе.

Она бит за битом инвертирует двоичную строку, записанную на ленте (считаем, что изначально головка находится в крайней левой ячейке, с которой начинается запись числа), а когда строка заканчивается, заканчивает работу и программа. Эта модель вычислений, получившая название машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). На первый взгляд такой простой объект кажется недостаточным для того, чтобы описать все многообразие компьютерных архитектур,P но пока не известно ни одного алгоритма, который нельзя было бы реализовать на машине Тьюринга. В логике и информатике широко известно нестрогое утверждение (так называемый тезис Черча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным хотя доказать его, разумеется, невозможно. Теперь нам нужно научиться оценивать скорость работы различных алгоритмов, сравнивать их друг с другом

1. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

2. Формализация понятия алгоритма

3. Формализация философских понятий

4. Интуитивное понятие алгоритма и его свойств

5. Интуитивное понятие алгоритма и его свойств

6. Знак и значение. Метод формализации
7. Некоторые проблемы формализации гуманитарных знаний (на примере археологии)
8. Структура и алгоритмы работы спутниковых радионавигационных систем

9. Генетические алгоритмы

10. Понятие государственного бюджета (Доклад)

11. Понятие опровержения и способы опровержения

12. Правонарушения и преступления. Понятия и виды

13. Понятие и принципы административной ответственности

14. Авторский договор: понятие и виды

15. Договор купли-продажи, договор имущественного найма, понятие и виды договора перевозки грузов

16. Понятие договора, классификация

Набор капиллярных ручек "Fine Writer 045", 20 цветов, 0,8 мм, пластиковая банка.
Цвет чернил - ассорти. Набор - да. Количество в наборе - 20. Форма корпуса - шестигранная. Толщина линии - 0,45 мм. Диаметр пишущего узла
317 руб
Раздел: Капиллярные
Машинка закаточная винтовая "Мещёра-2".
Машинка идеальна для домашнего консервирования, она проста в использовании и надежна в работе. Конструкция машинки обеспечивает ее
337 руб
Раздел: Консервирование
Аэрозоль Gardex "Extreme" от клещей, 150 мл.
Аэрозоль является эффективным средством, парализующим клещей после соприкосновения с одеждой. Действие активного вещества сохраняется до
305 руб
Раздел: Аэрозоль, спрей

17. Понятие договора найма по Закону о договорных и внедоговорных обязанностях

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

19. Обязательства: понятия и виды

20. Понятие Иска. Виды исков

21. Понятие и состав земель промышленности и иного назначения

22. Понятие и состав земель сельскохозяйственного назначения
23. Соотношение понятий "единство власти" и "разделение властей"
24. Понятие договора найма по Закону о договорных и внедоговорных обязанностях

25. Понятие государственного режима

26. Понятие, содержание и принципы исполнительной власти

27. Понятие и содержание основ конституционного строя РФ

28. Понятие международного гуманитарного права

29. Понятие и структура компетенции местного самоуправления

30. Государственный долг: понятие, состав и его обслуживание (по Казахстану)

31. Понятие вещных прав, виды и т.п.

32. Правовое государство. Понятие и основные черты. Правовой статус товарной и фондовой биржи

Стерилизатор "Care" для микроволновой печи (на 3 бутылочки).
Стерилизатор Care предназначен для стерилизации детских бутылочек. С помощью данного устройства можно эффективно простерилизовать
1045 руб
Раздел: Стерилизаторы, сушилки
Подставка для ножей овальная, 16x6,5x22 см.
Размеры: 16х6,5х22 см. Материал корпуса: пластик. Внутренняя часть: полипропиленовое волокно. Цвет: бежевый. Предназначена для безопасного
822 руб
Раздел: Подставки для ножей
Форма силиконовая для выпечки "Пряничный домик" (арт. TK 0231).
Вы в восторге от европейских рождественских ярмарок? Хотите, чтобы и в Вашем доме почаще царила атмосфера волшебства? С помощью
503 руб
Раздел: Формы и формочки для выпечки

33. Понятие права и правовой нормы. Виды и структура правовой нормы. Понятие и виды юридической ответственности

34. Понятие правонарушений и их виды

35. Понятие права, и современный подход к типологии права

36. Понятие и классификация договоров в римском праве

37. Понятие и виды договоров в Римском частном праве

38. Понятие правоспособности, её статусы и изменения
39. Биржа: понятие и значение
40. Понятие и задачи таможенного оформления, порядок производства

41. Соотношение понятий "система права" и "правовая система"

42. Форма правления, понятие и виды

43. Государство: понятие, признаки, формы правления и функции

44. Понятие источника (формы) права

45. Правовые отношения: понятия, признаки, элементы, виды

46. Правоотношения. Понятия правоотношений и их виды

47. Происхождение права, теории происхождения права, понятие признаки, виды, функции, принципы

48. Правоотношения: понятие, сущность, элементы

Набор "My Little Pony", 3 предмета.
Набор посуды в подарочной упаковке. Кружка 250 мл. Салатник 13 см. Тарелка 19,5 см.
578 руб
Раздел: Наборы для кормления
Логическая игра "Лабиринт".
781 руб
Раздел: Сортеры, логические игрушки
Обучающая игра "Спирограф-линейка. Чудесные узоры".
Большинство прописных букв состоит из плавных линий, которые необходимо рисовать безотрывно, а этот прибор в игровой форме разрабатывает
369 руб
Раздел: Трафареты фигурные, наборы

49. Трудовое право: понятие и виды переводов

50. Понятие трудового права. Предмет науки трудового права

51. Понятие и значение государственного кредита

52. Ценные бумаги: понятие и виды

53. Г. Вельфлин. Основные понятия истории искусства

54. О понятиях "культура, цивилизация"
55. Основные понятия. Типы цивилизаций
56. Рекурсивные алгоритмы

57. Распределенные алгоритмы

58. Принцип программного управления. Микропроцессор. Алгоритм работы процессора

59. Алгоритм Кнута-Морриса-Пратта

60. Написание игровой программы Tetris и описание алгоритма

61. Понятие, назначение и составные элементы систем программирования

62. Алгоритм создания базы данных складского учета

63. Компьютерный файлово-загрузочный полиморфный стелс-вирус ONEHALF 3544, особенности алгоритма и методы борьбы с ним

64. Основные понятия дифференциального исчисления и история их развития (Бакалавр)

Кружка "Акула".
Пусть утро станет добрым! Кружка с забавной фигуркой на дне - это шанс вызвать улыбку близкого человека. По мере выпивания напитка фигурка
434 руб
Раздел: Оригинальная посуда
Рюкзак для школы и офиса "SpeedWay 2", 46x32x19 см, серо-оранжевый.
Рюкзак для школы и офиса с отделением для ноутбука с диагональю до 15,6”. 3 больших отделения. 1 передний карман для мелких предметов. 2
1092 руб
Раздел: Без наполнения
Фломастеры утолщенные "Jumbo", 36 цветов.
Фломастеры, вентилируемый колпачок, утолщенный трехгранный корпус. В наборе: 36 цветов.
829 руб
Раздел: Более 24 цветов

65. Адаптивное параметрическое оценивание квадратно-корневыми информационными алгоритмами

66. Число как основное понятие математики

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

68. Трансплантация органов и тканей. Определение понятия пластической хирургии. Современная терминология в трансплантологии. Основные виды пересадки кожи. Причины отторжения трансплантантов. Профилактика осложнений. Реплантация. Имплантация

69. Понятие инвалидности. Причины и группы инвалидности. Пенсии по инвалидности.

70. Понятие и основные методы исследовательской фотографии
71. Понятие и характер нотариальных функций
72. Понятие предварительного расследования и его формы

73. Понятие и классификация доказательств

74. Понятие и признаки соучастия

75. Понятие соучастия в уголовном праве

76. Понятие соучастия в уголовном праве

77. Понятие и признаки преступления

78. Понятие уголовного права

79. Формирование понятия "фермент" в курсе биологии и связь с школьным курсом химии

80. Понятия о популяциях, сообществах, биоге- оценозах, экосистеме, биосфере и ее основных компонентах

Готовальня "Stop System", 3 предмета.
Готовальня из 3 предметов: 1 циркуль, 1 универсальный держатель, 1 пенал с грифелями. Цвет может отличаться от представленного на фото!
340 руб
Раздел: Циркули, чертежные инструменты
Пазл "Киты", 66 деталей.
Пазл собирается на основании в рамке — детали не растеряются и ограниченное пространство подскажет ребёнку правильный размер картины. На
548 руб
Раздел: Пазлы (54-99 элементов)
Дождевик Bambola, ПВХ.
Прозрачный, прочный дождевик для прогулочной коляски, подходит и для колясок с ручкой сзади (крепление задней стороны - на
408 руб
Раздел: Дождевики, чехлы для колясок

81. Использование алгоритмов при изучении орфографии в начальных классах

82. Формирование экологических понятий на уроках русского языка

83. Педагогические категории и понятия

84. Понятие формы государства

85. Понятие мировой политики и международных отношенияй

86. Понятие - личность
87. Мышление. Понятие мышления
88. Профориентация и понятие профпригодности

89. Явление и понятие установки. Виды установок, экспериментальные исследования установок

90. Понятие о деятельности

91. Понятие одаренности

92. Понятие методологии психологии

93. Понятие о телевидении

94. Методы и алгоритмы компоновки, размещения и трассировки печатных плат

95. Примеры задач оптимизации, связанных с фундаментальными понятиями теории связи

96. Операцианализация понятия интеллект

Рюкзак школьный с эргономичной спинкой "Neon. Модель Multi Pack".
Ранец с эргономичной спинкой. Жесткий каркас. Вмещает формат А4+. Размер: 40x32x18 см. Имеет два отделения на молнии, боковые карманы на
2306 руб
Раздел: Без наполнения
Кружка фарфоровая "FIFA 2018. Забивака. Класс!", 380 мл.
Объем: 380 мл. Материал: фарфор.
319 руб
Раздел: Кружки, посуда
Органайзер для обуви "Сороконожка".
Органайзер "Сороконожка", который можно повесить на дверное полотно, стену и другие поверхности, будет содержать всю Вашу обувь
1056 руб
Раздел: Полки напольные, стеллажи

97. Социальное действие и социальное взаимодействие как базовые понятия в социологии

98. Понятие и проблема статуса личности в социологии

99. Понятие социальной группы. Классификация социальных групп

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


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.