Geum.ru

Рекомендации по проведению занятий 10

Вид материалаКонтрольные вопросы

Содержание


Рекомендации по проведению занятий
44 :: Содержание
Рекомендации по проведению занятий
48 :: Содержание
51 :: Содержание
N отмеченных секциях. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший (он должен с
N меток (метки расположены через пробел). Надо сжать массив так, чтобы все N
N меток. Уменьшите этот массив в 2 раза. Вариант 23 Даны два натуральных числа n
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   21
§ 6. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

^ Рекомендации по проведению занятий

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

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

Полезна и подготовка рефератов. На семинарских занятиях, помимо обсуждения теоретических вопросов, необходимо решение задач.

44

^ 44 :: ссылка скрыта

44 :: 45 :: ссылка скрыта

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

  1. Что называется графом? ориентированным графом?
  2. Что называется вершинами графа? ребрами?
  3. Какие ребра и какие вершины графа называются смежными?
  4. Какой граф называется мультиграфом?
  5. Какой граф называется полным? дополнением?
  6. Что называется петлей? цепью? циклом? путем в графе?
  7. Какой граф называется деревом?
  8. Что называется суммой графов? пересечением? композицией?
  9. Что называется транзитивным замыканием графа? декартовым произведением графов?
  10. Что называется степенью графа? Что называется полустепенями исхода и захода графа?

44

  1. Что такое цикломатическое число графа?
  2. Что называется хроматическим числом графа? функцией Гранди?
  3. C помощью каких матриц можно задать граф?
  4. Какой граф называется эйлеровым?
  5. В чем состоит содержание теоремы Форда - Фалкерсона?

45

44 :: 45 :: ссылка скрыта

45 :: ссылка скрыта

Темы для рефератов

  1. Исторические вехи теории графов.
  2. Задачи, сводящиеся к графам.
  3. Связность в графах.
  4. Графы и отношения на множествах.
  5. Теоремы о числах графов.
  6. Устойчивость графов.
  7. Расстояния и пути в графах.

45

45 :: ссылка скрыта

45 :: ссылка скрыта

Темы семинарских занятий

  1. Основные понятия теории графов.
  2. Операции над графами.
  3. Степени и числа графов.
  4. Матрицы графов.
  5. Расстояния и пути на графах.
  6. Задачи, сводящиеся к графам. Транспортные сети и задачи о потоках.

45

45 :: ссылка скрыта

45 :: 46 :: ссылка скрыта

Задачи и упражнения

  1. Изобразите графы, имеющие следующие матрицы смежности:

а)

0
1
1
1
0

1
0
0
0
1

1
0
0
1
1

1
0
1
0
1

0
1
0
1
0

б)

0
1
1
0
0

1
0
0
0
0

1
0
0
1
1

0
0
1
0
0

0
0
1
0
0

  1. Получите матрицу смежности графа:



45

  1. Сколько существует различных графов, имеющих n вершин?
  2. Пусть граф с вершинами А, В, С, D имеет ребра AB, AC, BD, CD. Используя матрицу смежности этого графа, определить:
  • а) число маршрутов длины 2 из С в В;
  • б) число маршрутов длины 3 из А в В;
  • в) является ли граф связным?

  1. Сколько различных ориентированных графов может существовать в заданных N вершинах?
  2. Пусть V- множество вершин ориентированного графа. Какова максимальная мощность множества дуг этого графа?

46

45 :: 46 :: ссылка скрыта

46 :: ссылка скрыта

Дополнительная литература

  1. Басакер P., Caamu Т. Конечные графы и сети: Пер. с англ. - M.: Наука, 1874.
  2. Зыков А.А. Основы теории графов. - M.: Наука, 1987.
  3. Кристофидес H. Теория графов. Алгоритмический подход: Пер. с англ. - M.: Мир, 1978.
  4. Кук Д., Бейз Г. Компьютерная математика: Пер с англ. - M.: Наука, 1990.
  5. Ope О. Теория графов: Пер. с англ. - M.: Наука, 1980.
  6. Основы кибернетики. Математические основы кибернетики / Под ред. К.А. Пупкова. - M.: Высш. шк., 1974.
  7. Свами M., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. - M.: Мир, 1984.
  8. Tamm У. Теория графов: Пер. с англ. - M.: Мир, 1988.
  9. Уилсон Р. Введение в теорию графов: Пер. с англ, - M.: Мир, 1977.
  10. Xapapu Ф. Теория графов: Пер. с англ. - M.: Мир, 1973.

46

46 :: ссылка скрыта

47 :: 48 :: ссылка скрыта

§ 7. АЛГОРИТМ И ЕГО СВОЙСТВА

^ Рекомендации по проведению занятий

Тему "Алгоритм и его свойства" традиционно считают главной темой теоретической информатики, вводящей в обширные практические разделы алгоритмизации различные процедурные языки программирования, а также методы программирования. Нельзя не отметить, что в данном случае рассматривается интуитивное понятие алгоритма, а также интуитивно ясные его свойства. Данное обстоятельство приводит к тому, что у разных авторов определения алгоритма несколько различаются, также различаются и наборы свойств алгоритмов. Важно не становиться в данном случае на догматические позиции.

Интересно проследить развитие понятия алгоритма, контекста, в котором оно используется, в последние десятилетия. В математике, например, является традиционным подход к алгоритмам с точки зрения их существования и алгоритмической разрешимости задачи. В 70-е годы в работах по кибернетике алгоритм рассматривается в основном еще в плане процесса вычислений, преимущественно с помощью ЭВМ. В 80-е годы уже в книгах по информатике алгоритм связывается с обработкой информации (данных). Ныне алгоритмы не связываются с обработкой чего-то конкретного и вперед выходят их общие свойства.

47

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

При изучении данной темы целесообразно применение различных форм занятий - и семинарских, и лабораторно-практических. При выполнении лабораторных работ может быть использован широкий набор программных средств, моделирующих исполнителей на IBM-совместимых ПК. Надо иметь в виду, что основные практические навыки в отношении разработки алгоритмов будут формироваться в дальнейшем при изучении языков и методов программирования. Главная задача проведения занятий по данной теме - пропедевтика изучения в дальнейшем языков и методов программирования ЭВМ. Остается полезной и подготовка рефератов, посвященных истории формирования понятия алгоритма, различиям в трактовке алгоритмов в математике и информатике, известнейшим алгоритмам.

48

47 :: 48 :: ссылка скрыта

47 :: ссылка скрыта

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

  1. Каково происхождение слова "алгоритм"?
  2. Приведите определение алгоритма.
  3. Приведите примеры вычислительных алгоритмов, алгоритмов обработки информации и алгоритмов, не направленных на обработку информации.
  4. Что такое исполнитель? Приведите примеры.
  5. Из каких элементов состоят алгоритмы?
  6. Охарактеризуйте способы представления алгоритмов.
  7. Какова роль языка в представлении алгоритмов? Что называют "алгоритмическим языком"?
  8. В чем состоит свойство дискретности алгоритма?
  9. В чем состоит свойство детерминированности (определенности) алгоритма? Можно ли говорить о детерминированности алгоритмов, использующих случайные числа?
  10. Что означает свойство направленности (результативности) алгоритма? Можно ли считать алгоритмами процедуры, подразумевающие обработку бесконечных последовательностей чисел?
  11. В чем состоит свойство элементарности (локальности) шагов алгоритма?
  12. Что означает "массовость алгоритма"?
  13. Проинтерпретируйте свойства алгоритмов на приведенных в ответе на вопрос 3 примерах алгоритмов.
  14. Каковы основные алгоритмические конструкции?
  15. Какие элементы графических схем представления алгоритмов используются для отображения основных алгоритмических конструкций?
  16. Каковы основные конструкции алгоритмического языка?

47

47 :: ссылка скрыта

47 :: ссылка скрыта

Темы для рефератов

  1. История формирования понятия "алгоритм".
  2. Известнейшие алгоритмы в истории математики.
  3. Проблема существования алгоритмов в математике.
  4. Средства и языки описания (представления) алгоритмов.
  5. Методы разработки алгоритмов.

47

47 :: ссылка скрыта

48 :: ссылка скрыта

Темы семинарских занятий

  1. Понятие алгоритма.
  2. Средства представления алгоритмов. Основные конструкции алгоритмических
  3. Свойства алгоритмов

48

48 :: ссылка скрыта

48 :: ссылка скрыта

Рекомендации по программному обеспечению

Вследствие давних традиций в изучении данной темы имеется большое число программных средств для учебных компьютеров типа "Корвет", "УКНЦ", "Yamaha", остающихся кое-где в эксплуатации, а также для IBM-совместимых компьютеров, моделирующих те или иные исполнители. Многие из них предназначены для обучения информатике детей младшего и среднего школьного возраста (например, программные модели исполнителей "Пылесосик" и "Кенгуренок"). Весьма интересным комплексом является "Роботландия". Однако изучение систем команд этих исполнителей более соответствует задачам курса методики обучения информатике.

Весьма полезным при изучении представления алгоритмов на формальном языке, а также основных алгоритмических конструкций является так называемый Е-практикум или комплекс КУМИР (разработанный на мехмате МГУ в конце 80-х - начале 90-х годов), работающий в среде MS-DOS - файловой оболочки типа Norton Commander. Используя данное программное обеспечение, можно поставить несколько лабораторных работ, обеспечивающих качественное знакомство с представлением алгоритмов на формальном алгоритмическом языке, а также с основными алгоритмическими конструкциями и даже с некоторыми типами данных.

48

^ 48 :: ссылка скрыта

48 :: ссылка скрыта

Задачи и упражнения

  1. Изобразите алгоритм Евклида для нахождения наибольшего общего делителя положительных чисел а и b с помощью граф-схемы и запишите его на алгоритмическом языке.
  2. Изобразите с помощью граф-схемы и запишите на алгоритмическом языке алгоритмы, являющиеся решением следующих задач:
  • а) пусть задана последовательность x1, х2, х3, ... хп из п произвольных действительных чисел и число a\ требуется подсчитать в этой последовательности количество К чисел xi > a и количество M чисел xi < a;
  • б) требуется вычислить сумму 1 + 1/1! + 1/2! + 1/3! + ... + n! и проверить, что с ростом п эта сумма приближается к основанию натурального логарифма e;
  • в) с точностью 10-5 решить уравнение x = sin(x), используя метод итераций, т.е. получить последовательность 1, x1, x2, ... ,xn-1, xn где xi-1 = sin(xi) и |xn - xn-1| < 10-5

48

48 :: ссылка скрыта

48 :: ссылка скрыта

Лабораторные работы

  1. Система команд исполнителя алгоритмов.
  2. Основные алгоритмические конструкции в языке исполнителя.
  3. Разработка алгоритмов на языке исполнителя.

48

48 :: ссылка скрыта

49 :: ссылка скрыта

Дополнительная литература

  1. Алферова З.А. Теория алгоритмов. - M.: Статистика, 1973.
  2. Брой M. Информатика: В 3 т. Т. 1. Основополагающее введение: Пер. с нем. - M.: Диалог-МИФИ, 1996.
  3. Bupm H. Алгоритмы и структуры данных: Пер. с англ. - M.: Мир, 1989.
  4. Гудман C., Хадитниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. - M.: Мир, 1981.
  5. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы: Пер. с англ. - M.: Мир, 1976.
  6. Матюшков Л.П., Лихтаровыч A.A. Основы машинной математики: Пособие для учителя. - Минск: Нар. Асвета, 1988.
  7. Основы кибернетики. Математические основы кибернетики/Под ред. К.А.Пупкова. - M.: Высш. шк., 1974.

49

49 :: ссылка скрыта

49 :: ссылка скрыта

Дополнительная литература

  1. Алферова З.А. Теория алгоритмов. - M.: Статистика, 1973.
  2. Брой M. Информатика: В 3 т. Т. 1. Основополагающее введение: Пер. с нем. - M.: Диалог-МИФИ, 1996.
  3. Bupm H. Алгоритмы и структуры данных: Пер. с англ. - M.: Мир, 1989.
  4. Гудман C., Хадитниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. - M.: Мир, 1981.
  5. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы: Пер. с англ. - M.: Мир, 1976.
  6. Матюшков Л.П., Лихтаровыч A.A. Основы машинной математики: Пособие для учителя. - Минск: Нар. Асвета, 1988.
  7. Основы кибернетики. Математические основы кибернетики/Под ред. К.А.Пупкова. - M.: Высш. шк., 1974.

49

49 :: ссылка скрыта

49 :: 50 :: ссылка скрыта

Краткие сведения

Введенного на интуитивном уровне понятия алгоритма и опытным путем установленных свойств алгоритмов вполне достаточно для решения широкого круга математических задач. Достаточно такого подхода и при решении практических задач программирования компьютеров. Однако в тех случаях, когда задача оказывается сложной и ее алгоритмическое решение найти не удается, встает вопрос о ее алгоритмической разрешимости. При этом требуется понятие алгоритма формализовать, т.е. четко определить исполнителя алгоритмов, с помощью которого можно провести доказательство алгоритмической неразрешимости задачи.

В первой половине XX века почти параллельно были разработаны несколько подходов к формализации алгоритмов - рекурсивные функции, абстрактные машины Тьюринга и Поста, λ-исчисление, нормальные алгоритмы (так это традиционно называется в математике) Маркова, впоследствии оказавшиеся эквивалентными. Некоторые из этих подходов оказали воздействие на становление информатики и нашли отражение в производственных языках программирования - таких, как Lisp (λ-исчисление), Рефал (нормальные алгоритмы Маркова). Последний язык используется в исследованиях и разработках в области искусственного интеллекта; кстати, он чуть ли не единственный, разработанный в России и получивший мировое признание.

Формализованные подходы к алгоритмам в информатике обладают высокой образовательной ценностью. Так, абстрактные машины Тьюринга и Поста являются прекрасными средствами освоения алгоритмизации даже при безмашинном

49

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

50

49 :: 50 :: ссылка скрыта

50 :: ссылка скрыта

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

  1. Зачем в математике потребовалось формализовать понятие алгоритма?
  2. Какие подходы к уточнению понятия алгоритма существуют?
  3. Какие функции называют вычислимыми? Какие функции называют частичными?
  4. Какие функции называют частично-рекурсивными?
  5. Какой набор простейших функций и элементарных операций используется в теории рекурсивных функций?
  6. Какова формулировка тезиса Черча? Что он означает?
  7. Каково устройство абстрактной машины Поста? Каковы выполняемые ею команды?
  8. Каково устройство абстрактной машины Тьюринга? Каковы выполняемые ею действия?
  9. Как описывается машина Тьюринга? Приведите примеры схем машин Тьюринга.
  10. Что называется композицией машин Тьюринга?
  11. В чем состоит содержание теоремы Тьюринга?
  12. Приведите примеры дедуктивных цепочек.
  13. Как определяются нормальные алгоритмы Маркова?
  14. В чем состоит задача универсального алгоритма?

50

50 :: ссылка скрыта

50 :: ссылка скрыта

Темы для рефератов

  1. Проблема алгоритмической разрешимости в математике.
  2. Основатели теории алгоритмов - Клини, Черч, Пост, Тьюринг.
  3. Основные определения и теоремы теории рекурсивных функций.
  4. Тезис Черча.
  5. Проблемы вычислимости в математической логике.
  6. Машина Поста.
  7. Машина Тьюринга.
  8. Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.

50

50 :: ссылка скрыта

50 :: ссылка скрыта

Темы семинарских занятий

  1. Формализация понятия алгоритма и алгоритмическая разрешимость.
  2. Основы теории рекурсивных функций.
  3. Абстрактные автоматы и уточнение понятия алгоритма. Машины Поста и Тьюринга.
  4. Ассоциативные исчисления и нормальные алгоритмы Маркова.

50

50 :: ссылка скрыта

51 :: ссылка скрыта

Рекомендации по программному обеспечению

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

Для поддержки изучения нормальных алгоритмов Маркова имеется версия транслятора языка Рефал для 8-разрядных учебных машин типа "Yamaha MSX-2".

51

^ 51 :: ссылка скрыта

51 :: ссылка скрыта

Задачи и упражнения

  1. Используя рекурсивные функции, постройте:
  • а) трехместную функцию сложения;
  • б) n-местную функцию сложения.

  1. Используя рекурсивные функции, постройте:
  • а) двухместную функцию умножения;
  • б) трехместную функцию умножения;
  • в) n-местную функцию умножения.

  1. Постройте частичную двухместную функцию деления.
  2. Напишите и самостоятельно исполните программу машины Поста, складывающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, вычитающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, умножающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, делящую одно число на другое, разделенные на ленте одним пробелом.
  2. Постройте машины Тьюринга, вычисляющие простейшие арифметические функции.
  3. Имея машины Тьюринга, вычисляющие функции g и h, постройте машину, вычисляющую:
  • а) суперпозицию этих функций;
  • б) функцию, получаемую из g и h примитивной рекурсией.

  1. Постройте машину Тьюринга, производящую обращение функции.
  2. Постройте машину Тьюринга, вычисляющую:
  • а) сумму двух чисел;
  • б) разность двух чисел;
  • в) произведение двух чисел;
  • г) частное двух чисел.

  1. Постройте нормальный алгоритм Маркова, реализующий вычитание двух целых чисел, представленных символами 1. Проверьте его работу на примерах.
  2. Задайте нормальный алгоритм Маркова, реализующий умножение двух чисел, представленных символами 1.

51

51 :: ссылка скрыта

51 :: ссылка скрыта

Задачи и упражнения

  1. Используя рекурсивные функции, постройте:
  • а) трехместную функцию сложения;
  • б) n-местную функцию сложения.

  1. Используя рекурсивные функции, постройте:
  • а) двухместную функцию умножения;
  • б) трехместную функцию умножения;
  • в) n-местную функцию умножения.

  1. Постройте частичную двухместную функцию деления.
  2. Напишите и самостоятельно исполните программу машины Поста, складывающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, вычитающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, умножающую два числа, разделенные на ленте:
  • а) одним пробелом;
  • б) произвольным числом пробелов.

  1. Напишите и самостоятельно исполните программу машины Поста, делящую одно число на другое, разделенные на ленте одним пробелом.
  2. Постройте машины Тьюринга, вычисляющие простейшие арифметические функции.
  3. Имея машины Тьюринга, вычисляющие функции g и h, постройте машину, вычисляющую:
  • а) суперпозицию этих функций;
  • б) функцию, получаемую из g и h примитивной рекурсией.

  1. Постройте машину Тьюринга, производящую обращение функции.
  2. Постройте машину Тьюринга, вычисляющую:
  • а) сумму двух чисел;
  • б) разность двух чисел;
  • в) произведение двух чисел;
  • г) частное двух чисел.

  1. Постройте нормальный алгоритм Маркова, реализующий вычитание двух целых чисел, представленных символами 1. Проверьте его работу на примерах.
  2. Задайте нормальный алгоритм Маркова, реализующий умножение двух чисел, представленных символами 1.

51

51 :: ссылка скрыта

52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: ссылка скрыта

Лабораторные работы

Лабораторная работа № 1

Машина Поста

Время выполнения 4 часа.

Вариант 1

На ленте машины Поста расположен массив в ^ N отмеченных секциях. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший (он должен состоять из 2N меток). При этом исходный массив может быть стерт.

Вариант 2

На ленте машины Поста расположен массив из ^ N меток (метки расположены через пробел). Надо сжать массив так, чтобы все N меток занимали N расположенных подряд секций.

Вариант 3

На информационной ленте машины Поста расположено N массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определите число массивов.

Вариант 4

Игра Баше. В игре участвуют двое (человек и машина Поста). Напишите программу, по которой всегда будет выигрывать машина Поста. Суть игры заключается в следующем: имеется 21 предмет. Первым ходит человек. Каждый из играющих может брать 1, 2, 3 или 4 предмета. Проигрывает тот, кто берет последний предмет.

Вариант 5

Число k представляется на ленте машины Поста k + 1 идущими подряд метками. Одна метка соответствует нулю. Составьте программу прибавления 1 к произвольному числу k, Каретка расположена над одной из меток, принадлежащих заданному числу k.

Вариант 6

Составьте программу сложения двух целых неотрицательных чисел а и b, расположенных на ленте машины Поста. Каретка расположена над одной из меток, принадлежащих числу а. Число b находится правее числа а через несколько пустых секций.

Вариант 7

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

52

Вариант 8

На ленте машины Поста расположен массив из N меток. Составьте программу, действуя по которой машина выяснит, делится ли число на 3. Если да, то после массива через одну пустую секцию поставьте метку V.

Вариант 9

Число k представлено на ленте машины Поста k + 1 идущими подряд метками. Найдите остаток от деления целого неотрицательного числа k на 3, если известно, что каретка находится справа от заданного числа.

Вариант 10

Составьте программу нахождения разности двух неотрицательных целых чисел а и b, находящихся на ленте машины Поста. Каретка находится над левой меткой левого числа. Неизвестно, какое число больше: а или b.

Вариант 11

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

Вариант 12

На ленте машины Поста расположен массив из 2N- 1 меток. Составьте программу отыскания средней метки массива и стирания ее.

Вариант 13

На ленте машины Поста расположены два массива. Составьте программу стирания того из массивов, который имеет большее количество меток.

Вариант 14

На информационной ленте машины Поста находятся два массива в M и N меток. Составьте программу выяснения, одинаковы ли массивы по длине.

Вариант 15

Задача В.А.Успенского. На информационной ленте либо вправо, либо влево от секции, над которой расположена каретка, находится массив меток. Расстояние до массива выражается произвольным числом. Необходимо составить программу, работая по которой машина Поста найдет этот массив и установит каретку на начало этого массива.

Вариант 16

Составьте программу умножения двух чисел а и b.

Вариант 17

На ленте машины Поста находится n массивов меток, после последнего массива на расстоянии более трех пустых секций находится одна метка. Массивы

53

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

Вариант 18

На ленте изображено n массивов меток, отделенных друг от друга одной свободной ячейкой. Каретка находится над первой меткой первого массива. Определите количество массивов.

Вариант 19

На ленту машины Поста нанесены два массива меток на некотором расстоянии друг от друга. Соедините эти два массива в один. Каретка находится над крайней левой меткой левого массива.

Вариант 20

На ленте машины Поста отмечен массив n меток. Найдите число 2n + 1 и проверьте, делится ли оно на 3. Если да, то после числа через одну пустую секцию поставьте две метки, если нет - поставьте три метки. Каретка находится над крайней левой отмеченной секцией.

Вариант 21

Дан массив меток. Каретка обозревает первую пустую секцию перед началом массива. Раздвиньте массив так, чтобы после каждой метки была пустая секция.

Вариант 22

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

Вариант 23

Найти НОД двух чисел, находящихся на ленте машины Поста. Между этими числами находится произвольное количество пустых секций. Каретка находится над левой меткой левого числа.

Вариант 24

На ленте машины Поста находятся n массивов меток. Каретка находится где-то над первым массивом. Удалите все массивы с четными номерами (соседние массивы разделены тремя пустыми секциями).

Вариант 25

На информационной ленте машины Поста находится массив меток. Каретка находится где-то над массивом (но не над крайней меткой). Сотрите все метки, кроме крайних, таким образом, чтобы положение каретки при этом не изменилось.

54

Лабораторная работа № 2

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

Время выполнения 4 часа.

Вариант 1

На информационной ленте машины Тьюринга содержится массив символов +. Необходимо разработать функциональную схему машины Тьюринга, которая каждый второй символ + заменит на -. Каретка в начальном состоянии находится где-то над указанным массивом.

Вариант 2

Дано число n в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число n на 1.

Вариант 3

Дана десятичная запись натурального числа n > 1. Разработайте машину Тьюринга, которая уменьшала бы заданное число n на 1. При этом запись числа n - 1 не должна содержать левый нуль, например, 100 - 1 = 99, а не 099. Начальное положение головки - правое.

Вариант 4

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

Вариант 5

Дана строка из букв а и b. Разработайте машину Тьюринга, которая переместит все буквы а в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки.

Вариант 6

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

Вариант 7

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

Вариант 8

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

55

Вариант 9

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

Вариант 10

На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три различные буквы: А, В и С. Каретка в начальном состоянии обозревает букву, расположенную справа. Необходимо составить функциональную схему машины Тьюринга, которая сумеет поменять местами крайние буквы.

Вариант 11

Даны два натуральных числа т и n, представленных в унарной системе счисления. Соответствующие наборы символов " | " разделены " - " , вслед за последним символом набора n стоит знак "=". Разработайте машину Тьюринга, которая будет находить разность чисел m и п. При этом результат должен быть записан следующим образом: если т > n, то справа от "=" должны стоять знак "+" и набор символов " | " в количестве т - n; если т = n, то справа от знака "=" должна стоять пустая клетка; если т < n, то справа от "=" должны стоять знак "-" и набор символов " | " в количестве n - т.

Вариант 12

Даны два натуральных числа n и m, заданных в унарной системе счисления. Числа n и т представлены наборами символов " | " , разделенных " \ ". В конце набора стоит "=". Разработайте машину Тьюринга, которая будет производить деление нацело двух натуральных чисел n и т и находить остаток от деления. При этом результат должен быть записан следующим образом: после "=" должен находиться набор символов " | " частного (он может быть и пустым), после чего ставится знак "(", за которым следует набор символов " | " остатка от деления n на т.

Вариант 13

На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.

Вариант 14

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

Вариант 15

На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {a, b, с, d}. Подсчитайте число букв "а" в данном слове и полученное значение запишите на ленту левее исходного слова через пробел. Каретка обозревает крайнюю левую букву.

56

Вариант 16

На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово "да", если нет - "нет". Каретка находится где-то над числом.

Вариант 17

На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.

Вариант 18

На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.

Вариант 19

На информационной ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удалив из него все элементы В.

Вариант 20

Число n задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение n по формуле:

φ(n) =

{
n - 2 если n > 5,

1, если n = 5,

2n, еcли n < 5.

Каретка обозревает крайнюю левую метку.

Вариант 21

Число n задано на ленте машины Тьюринга массивом меток. Преобразуйте это значение n по формуле:

φ(n) = [

5n

4

  ] + 2.

Каретка обозревает крайнюю левую метку.

Вариант 22

На ленте машины Тьюринга находится массив 2^ N меток. Уменьшите этот массив в 2 раза.

Вариант 23

Даны два натуральных числа n и т, представленные в унарной системе счисления. Между этими числами стоит знак "?". Выясните отношение т и n, т.е. знак "?" замените на один из подходящих знаков ">", "<", " = ".

Вариант 24

Найдите произведение двух натуральных чисел т и л, заданных в унарной системе счисления. Соответствующие наборы символов "|" разделены знаком "*", а

57

справа от последнего символа правого члена стоит знак " = ". Поместите результат умножения этих чисел вслед за знаком " = ".

Вариант 25

На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2, 3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.

58

52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: ссылка скрыта

58 :: ссылка скрыта

Дополнительная литература

  1. Алферова З.А. Теория алгоритмов. - M.: Статистика, 1973.
  2. Брой M. Информатика: В 3 т. Т. 1. Основополагающее введение: Пер. с нем. - M.: Диалог-МИФИ, 1996.
  3. Мальцев А.И. Алгоритмы и вычислимые функции. - M.: Наука, 1986.
  4. Манин Ю.И. Вычислимая и невычислимое. - M.: Сов. радио, 1980.
  5. Марков А.А., Нагорный H.M. Теория алгоритмов. - M.: Наука, 1984.
  6. Матюшков Л.П., Лихтарович А.А. Основы машинной математики: Пособие для учителя. - Минск: Нар. Асвета, 1988.
  7. Машины Тьюринга и вычислимые функции: Пер. с нем. - M.: Мир, 1972.
  8. Миков А.И. Информатика. Введение в компьютерные науки. - Пермь: ПГУ, 1998.
  9. Основы кибернетики. Математические основы кибернетики/Под ред. К.А. Пупкова. - M.: Высш. шк., 1974.
  10. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. - M.: Сов. радио, 1974.
  11. Успенский B.A. Машина Поста. - M.: Наука, 1988.

58

58 :: ссылка скрыта

58 :: 59 :: ссылка скрыта