Рабочая тетрадь по дисциплине «Теория алгоритмов»

Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Министерство общего и профессионального образования Свердловской области

ГАПОУ СО

«ЕКАТЕРИНБУРГСКИЙ КОЛЛЕДЖ ТРАНСПОРТНОГО СТРОИТЕЛЬСТВА»













Теория алгоритмов


Рабочая тетрадь



для студентов специальности

«Программирование в компьютерных системах
»





















2016


2

ОДОБРЕНО

цикловой методической
комиссией
Информатика
и информационные
технологии

Председатель ЦМК


Е.В. Черепанова

СОГЛАСОВАНО

Заместитель директора по
научно
-
методической и
инновационной работе
ГАПОУ СО
«Екатеринбургский колледж

транспортного строительства»

Т.К. Пермякова

УТВЕРЖДАЮ

Заместитель директора

по учебно
-
воспитательной
работе ГАПОУ СО
«Екатеринбургский колледж
транспортного строительства»

А.М. Шанин





Автор:
Хмельницкая Г.В.

, преподаватель дисциплины
«Теория а
лгоритмов»

ГАПОУ СО «Екатеринбургский колледж
транспортного строительства»



Рецензент
:
Черепанова Е.В. ,
преподаватель дисциплин профессионального
профиля ГАПОУ СО «Екатеринбургский
колледж транспортного строительства»















Рабочая тетрадь пре
дназначена для самостоятельной работы п
о основным разделам
дисциплины
«Теория алгоритмов» для студентов 2 курса специальности 09.02.03
«Программирование в компьютерных системах» среднего профессионального образования.

В рабочую тетрадь входят разделы, как

теоретического характера, так и рекомендации по
проведению практических работ, в частности с использованием офисного приложения Microsoft
Office.

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





3


Оглавление

ВВЕДЕНИЕ

................................
................................
................................
................................
.............

4

ТЕХНИКА БЕЗОПАСНОСТИ

................................
................................
................................
...............

5

Раздел
1.

Развитие алгоритмического мышления
–

основа программистской деятельности

.........

7

Тема 1.1.

Этапы решения задач на ЭВМ

................................
................................
..............................

7

Тема 1.2 Ал
горитм
–

функциональное понятие программирования.

................................
..............

10

Раздел 2. Основные виды алгоритмов и принципы составления алгоритмов

................................

11

Тем
а 2.1.Описание алгоритмов, способы описания

................................
................................
..........

11

Тема 2.2. Правила построения схем алгоритмов. Основные модели (виды) алгоритмов

.............

15

Тема 2.3Машина Поста.

................................
................................
................................
.......................

16

Тема 2.4 Машина Тьюринга.

................................
................................
................................
................

18

Тема 2.5 Нормальные алгоритмы Маркова

................................
................................
........................

21

Раздел
III

Основные положения и методика составления сложных алгоритмов.

..........................

24

Тема 3.1. Эволюция языков программирования. Системы программирования.

............................

24

Тема 3.2. Методика составления сложных алгоритмов

................................
................................
....

25

Тема 3.3. Методы определения сложности работы алгоритмов

................................
......................

26

Литература

................................
................................
................................
................................
.............

27

Приложение

................................
................................
................................
................................
...........

28





4

ВВЕДЕНИЕ

Рабочая тетрадь по дисциплине «
Теория алгоритмов
» разработана с учётом

требова
ний
федерального компонента государственного стандарта

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

В ходе изучения

материала

у обучающихся формируется информационно
-
коммуникационная компетентность
–

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

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

составлять
алгоритмы решения сложных з
адач,

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

для
профессионального роста.

Рабочая тетрадь поможет студентам в освоении теоретических понятий
теории
алгоритмов
, а

преподавателю в проверке качества знаний обучаемых. Она создана для удобной
и комфортной работы на
аудиторных занятиях

и во внеурочное время.




5


ТЕХНИКА БЕЗОПАСНОСТИ

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

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

1)

н
е входить в помещение, где находится вычисл
ительная техника без разр
ешения
преподавателя;


2)

н
е включ
ать без разрешения оборудование;


3)

п
ри несчастном случае, или поломке обо
рудования позвать преподавателя;

з
нать, где
находится пульт выключения оборудования (выключат
ель, красная кнопка, рубильник);


4)

н
е трогать провода и разъемы (возможно

поражение электрическим током);


5)

не допускать порчи оборудования;


6)

н
е работат
ь в верхней одежде;


7)

н
е

прыгать, не бегать (не пылить);


8)

н
е шуметь.

С

ст
рого запрещается:

1)

трогать разъемы соединительных кабелей;

2)

при
касаться к питающим проводам и устройствам заземления;

3)

прикасаться к экрану и тыльной стороне монитора;

4)

включать и отключать аппаратуру без указания преподавателя;

5)

работать во влажной одежде и влажными руками;

6)

класть диск, книги, тетради на монитор и кл
авиатуру.

Работать следует на расстоянии 60
-
70 см, допустимо не менее 50 см, соблюдая правильную
посадку, не сутулясь, не наклоняясь; учащимся, имеющим очки для постоянного ношения,
-

в
очках.

Уровень глаз при вертикальном расположении экрана должен прихо
диться на центр экрана или
2/3 его высоты. Оптимальное расстояние глаз учащихся до экрана монитора должно быть в
пределах 0,6
-

0,7 м, допустимое
-

не менее 0,5 м.

Нельзя работать при недостаточном освещении и при плохом самочувствии.

Все задания выполнят
ь только
с разрешения преподавателя.

ЧЕМ ОПАСЕН ДЛЯ НАС КОМПЬЮТЕР


Компьютер
-

высокотехнологичное технически
хорошо продуманное устройство, но вместе с тем
очень опасное. Иногда опасность реальна, а иногда,
он незаметно воздействует на Ваше здоровье и
пс
ихику.

Возможные воздействия:



На зрение. (Преломление
-

искажение
изображения происходит в связи с тем, что лицевое
стекло монитора очень толстое, для безопасности
на случай разрушения кинескопа; растр
-

изображение состоит из точек и строк; мелькание
-

и
зображение формируется кадрами, как в
телевизоре; свечение
-

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



Излучение микроволновое (радиация) и
электромагнитное.

ЧЕМ ОПАСНЫ МЫ ДЛЯ
КОМПЬЮТЕРА

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

Возможные
повреждения:



Блоков компьютера
-

это царапины,
вмятины, трещины.



Механические повреждения
клавиатуры. Стираются надписи на
клавишах

(маникюр, кольца, кремы...), от
сильного удара клавиши "залипают" (в
особенности пробел и ввод).



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



Внутренние механические
повреждения, которые могут возникнуть

6



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



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



Компьютерные вирусы влияют на здоровье:
плавающие линии, плавающая четкость,
инфразвуки, ультразвуки, "двадцать пятый кадр",
стресс от потери информации...



Артрит (при работе с мышкой и клавиатурой
более всего задействованы
-

указатель
ный и
средний пальцы, мышцы запястья и предплечья,
что может вызвать болезнь суставов)
–

необходимо
распределение нагрузки на все пальцы
(десятипальцевый
-

слепой метод печати).



Ионизированная (наэлектризованная) пыль
-

сильный канцероген
–

необходимо про
ветривать
помещение и содержать в чистоте.



Компьютерные игры и Интернет иногда
перерастают в психологическую (компьютерную)
зависимость, поэтому следует развивать чувство
самоконтроля.

от удара или попадания постороннего
предмета вовнутрь. (Категорически
запрещается переносить, передвигать
блоки компьютера во включенном
состоянии.)



Токопроводящая пыль, загрязнения
,
влага нарушают теплопроводность
блоков и могут вывести из строя блоки
компьютера.



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



Бумага, положенная на вентиляционные
отверстия блоков (монитора) нарушает
их тепло
вой режим.



Частое включение / выключение
компьютера создает дополнительную
нагрузку на блоки компьютера.


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



7

Раздел 1.

Развитие алгоритмического мышления
–

основа программистской
деятельности

Тема 1.1.

Этапы решения задач на ЭВМ

Задание 1.

Запишите определения.

Информация
-
_______________________________________________________
____
___________

__________________________________________________________________
___
_____________

Алгоритм

-

____________________________________________________
____
____
____________

__________________________________________________________________
____
____________

Алгори
тмический объект

–

________________________________________
___
___
____________

__________________________________________________________________
____
____________

Алгоритмический процесс
-

______________________________________
____
___
_____________

__________
________________________________________________________
____
____________

Алгоритмическая модель

-

__________________________________________
____
_
____________

__________________________________________________________________
____
____________

Результативност
ь _______________________________________________________
____________

Универсальность

-

___________________________________________
____
_______
____________

__________________________________________________________________
____
____________

Конечность

-

_____
_________________________________________
___
__________
___________

__________________________________________________________________
____
____________

Дискретность

-

___________________________________
___
__________________
_
____________

______________________
____________________________________________
____
____________

Программирование

-

_______________________________________
_____
________
____________

__________________________________________________________________
____
____________

Массовость

-

_______________
________________________
____
____
____________
___________

__________________________________________________________________
____
____________

Детерминированность

–

_____________________________________________
____
____________

Надежность

–

____________________
_______________
_____
__________________
____________


8

Задание 2.

Заполните таблицу
:

Графически способ представления алгоритмов

Название

Обозначение и пример

Пояснение

Процесс



Решение



Модификация



Предопределенный
процесс



Ввод
-
вывод



Пуск
-
Остан
овка





9

Задание 3.

За
по
лните блок
-
схему

ЭТАПЫ РЕШЕНИЯ ЗАДАЧ
НА ЭВМ




























Задание 4.


Поставь соответствие.

Поколение 1 Транзисторы

Поколение 2 Микропроцессор

Поколение 3

Электронные лампы

Поколение 4 Интегральные схемы

Задание 5
.

Перечислите действия каждого этапа постановки задачи (см.Задание 3):

1)

_____________________________________________________________________
________
_______________________________________________________
________________________

2)

_____________________________________________________________________________
_______________________________________________________
________________________

3)

___________
_____________________________________________________
_____________
_____________________________________________________
__________________________

4)

_____________________________________________________________________________
_________________________________
______________________
__
______________________

5)

_____________________________________________________________________________
______________________________________________________
__________________________

6)

___________________________________________________
__________________________
______________________________________________________
_________________________

7)

_____________________________________________________________________________
_____________________________________________________
____________________
______


да

нет


10

Тема 1.2 Алгоритм
–

функциональное понятие программирования.

Задание 6
.


Закон РФ №3523
-
I

«О правовой охране программ для ЭВМ и баз данных»

определяет
____________________________________________________________
______________________
_______________
___________________________________________________________________
__________________________________________________________________________________
__________________________________________________________________________________

Задание 7
.


Составьте бл
ок
-
схему решения системы двух линейных уравнений, используя все этапы
постановки задачи на ЭВМ.































Задание 8.

Заполните таблицу истинности:

А

В

Отрицание
Инверсия
(НЕ)¬ А

Конъюнкция

Логическое
умножение
(И) А˄В

Дизъюнкция
Логиче
ское
сложение
(ИЛИ) А˅В

Следование
Импликация
А→В

0

0





0

1





1

0





1

1






Задание 9.

Выполните задание № 1
-
30 из

приложения.

Блок схема Решение систем линейных уравнений


11

Раздел 2.
Основные виды алгоритмов и принципы составления алгоритмов

Тема 2.1.Описание алгоритмов, способы описания


Задание 1
.

Заполните таблицу
:

1.

Свойства информации

Свойства информации

Примеры

1.

Доступная


2.

Адекватная


3.

Репрезентативность


4.

Актуальная


5.

Полная


6.

Достоверная


Запишите определения

Алгоритмический язык________________________________________________
_____
_________

______________________________________________________________________
____________

Исполнитель_______________________________________________________________________
__________________________________________________________
_______________________
_

Компьютер_____________________________________________________________
___________

Описательная сложность_________________________________________________
____________

______________________________________________________________________
____________

Вычис
лительная сложность_______________________________________________
___________

______________________________________________________________________
____________

Структурная схема______________________________________________________
____________

___________
___________________________________________________________
____________

Массив____________________________________________________________________________
________________________
__________________________________________________________

Цикл_______________
_______________________________________________________________
________________________
________________________
__________________________________

Машина Поста___________________________________
___________
_______________________


Задание 2
.


Прочитайте теор
етический материал и выполните задание.

Для перевода чисел из десятичной системы счисления в двоичную используют так называемый
"алгоритм замещения", состоящий из следующей последовательности действий:

1.

Делим десятичное число

А

на

2
. Частное

Q

запоминаем дл
я следующего шага, а
остаток

a

записываем как

младший

бит двоичного числа.

2.

Если частное

q

не равно

0
, принимаем его за новое делимое и повторяем процедуру,
описанную в шаге 1. Каждый новый остаток (
0

или

1
) записывается в разряды двоичного
числа в направле
нии от

младшего

бита к

старшему
.

3.

Алгоритм продолжается до тех пор, пока в результате выполнения шагов 1 и 2 не
получится частное

Q

=

0

и остаток

a

=

1
.

4.

Например, требуется перевести десятичное число

247

в двоичное. В соответствии с
приведенным алгоритмом п
олучим:


247
10

: 2 = 123
10

247
10

-

246
10

=

1
, остаток

1

записываем в

МБ

двоичного числа.

123
10

: 2 = 61
10

123
10

-

122
10

=

1
, остаток

1

записываем в следующий после

МБ

разряд двоичного числа.

61
10

: 2 = 30
10

61
10

-

60
10

=

1
, остаток

1

записываем в стар
ший разряд двоичного числа.


12

30
10

: 2 = 15
10

30
10

-

30
10

=

0
, остаток

0

записываем в старший разряд двоичного числа.

15
10

: 2 = 7
10

15
10

-

14
10

=

1
, остаток

1

записываем в старший разряд двоичного числа.

7
10

: 2 = 3
10

7
10

-

6
10

=

1
, остаток

1

записыва
ем в старший разряд двоичного числа.

3
10

: 2 = 1
10

3
10

-

2
10

=

1
, остаток

1

записываем в старший разряд двоичного числа.

1
10

: 2 = 0
10
, остаток

1

записываем в старший разряд двоичного числа.

5.

Таким образом, искомое двоичное число равно

11110111
2
.


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

Блок схема перевода в двоичную систему счисления.


13


Задание 3
.

1)

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


Двоичн
ая

Восьмеричная

Десятичная

Шестнадцатеричная

101010













127













269













9
B



Задание 4
.

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

Вариант 1

Вариант 2

1)100001
2

=?
8
=?
10
;

534
8
=?
2
=?
10
;

254
10
=?
2
=?
8
;

2)100111
2

=?
8
=?
10
=?
16
;

624
8
=?
2
=?
10
=?
16
;

231
10
=?
2
=?
8
=?
16
;

1АС
16
=?
2
=?
10
=?
8

1) 101101
2

=?
8
=?
10
;

627
8
=?
2
=?
10
;

3
78
10
=?
2
=?
8
;

2) 110011
2

=?
8
=?
10
=?
16
;

425
8
=?
2
=?
10
=?
16
;

199
10
=?
2
=?
8
=?
16
;

2
DB
16
=?
2
=?
10
=?
8


Задание 5
.

Прочитайте теоретический материал и заполните нижеприведенную таблицу.




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

"1
"(импульс напряжения) или " О" (отсутствие импульса). Комбинации двоичного кода для
кодирования информ
а
ции называются
цифровым кодированием.

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

Сообщение о событии, у которого только два одинаково возможных и
с
хода, содержит
одну единицу информации, называемую

битом

(Да
-

Нет, 1
-
0, И
с
тина
-
Ложь).

№ п/п

Из 10 в 8

Из 10 в

16

1



2



3



4



5



6



7



Алгоритм перевода в восьмеричную и шестнадцатеричную системы счисления.



14

Бит
-

это минимальная ко
личественная характеристика информации. Для измерения
компьютерной информации служит восьмибитовое число
-

байт.

Байт

-

минимальная единица информации, с помощью которой кодир
у
ют 1 символ.

1байт= 8бит;

1Кбайт (килобайт)
=

1024 или 2
10

байт;

1Мбайт (мегабай
т) =1 048 576 или 2
20

байт;

1Гбайт (гигабайт) =1 073 741 824 или 2
30
бaйт;

1Тбайт (терабайт) = 1 099 511 627 776 или 2
40

байт.

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

= 256. Каждому символу (цифре, букве, знаку) ставится в
соответствие единственный код из числа кодовых комбинаций. С помощью восьмиразрядного
кода можно закодировать строчные и прописные буквы лат
инского алфавита, буквы русского
алфавита, цифры, знаки препинания, знаки математических операций и некоторые спец
и
альные
символы. Передача символьной информации в этом случае заключается в пересылке по линии
передачи кодовых двоичных наборов информации. П
ри этом один разряд двоичной
информации принимается за 1 бит. Последовательность из 8 двоичных разр
я
дов кода
информации в ЭВМ осуществляется 8
-
разрядным двоичным кодом, т.е. каждому входному
символу соответствует 1 байт информ
а
ции.

Единицы измерения количе
ства информации

Название

Условное обозначение

В битах

В байтах

1Килобит

1Кбит



1Мегабит

1Мбит



1Гигабит

1Гбит



1Килобайт

1Кб



1Мегабайт

1Мб



1Гигабайт

1Гб



Задание 6
.

Решите задачи.

1) Книга, набранная с помощью компьютера, содержит 150 страни
ц, на каждой странице
–

40 строк, в каждой строке
–

60 символов. Каков объем информации в книге?

Ответ: _________________________________________________


2) Сколько килобайт составляет сообщение,

содержащее
,

12288 бит?

Ответ: _____________________________
____________________

3) Можно ли уместить на одну дискету книгу, имеющую 432 страницы, причем на каждой
странице этой книги 46 строк, а в каждой строке 62 символа?

Ответ: _________________________________________________

4) На странице обычного учебника по
мещается примерно 50 строк, в каждой строке по 60
знаков (байт). Сколько печатных листов такого учебника может поместиться на обычную 3
-
х
дюймовую дискету?

Ответ: _________________________________________________

5) Лазерный диск может содержать 650 Мбайт
информации. Определите, сколько дискет
объемом 1,38 Мбайт потребуется, чтобы разместить информацию с одного лазерного диска?

Ответ: _________________________________________________

Задание 7
.

Заполните пропуски числами, выполнив соответствующие вычисления
:


а)

5

Кбайт

= ____________

байт

= ____________________

бит,


б)

__________

Кбайт

= ___________

байт

= 12288

бит;


в)

__________

Кбайт

= ___________

байт

= 2
13
бит;


г)

__________
Гбайт

=1536

Мбайт

= ________________

Кбайт;


д)

512

Кбайт

= ___________
___


байт =

________________

бит.



15

Тема 2.2. Правила построения схем алгоритмов. Основные модели (виды) алгоритмов

Задание 8
.

Алгоритмические структуры

Ознакомьтесь с описанием различных алгоритмических структур на языке блок
-
схем.


Ветвление if

Это самый простой тип ветвления. Если результат вычисления
выражения
-
условия возвращает true (правда), то выполнение
алгоритма идет по ветке «Да», в которую включе
ны
дополнительные выражения
-
действия. Если условие возвращает
false (ложь), то выполнение алгоритма идет по ветке «нет», т.е
продолжает выполняться основная ветка программы.


Ветвление if
-
else

Если выражение
-
условие возвращает true (правда), то
выполнение алгоритма идет по ветке «Да», если условие не
выполняется (false), то выполнение идет по ветке «Нет». При
любом результате выражения
-
условия нельзя верн
уться в
основную ветку программы, минуя дополнительные действия.


Ветвление if
-
then
-
else

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

elif
–

else) не следует путать с алгоритмической конструкцией
«Выбор».


Цикл while

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


Цикл do

В этом цикле первый раз условие проверяется лишь после
выполнения действий тела цикла. Если условие
возвращает true,
то выражения
-
действия повторяются снова. Каким бы ни было
условие, тело данного цикла хотя бы раз, но выполнится.


16


Цикл for

Данный цикл

также называют циклом «Для» (for). В его
заголовке указывается три параметра: начальное значение
переменной (от), конечно значение (до) и ее изменение с
помощью арифметической операции на каждом «обороте» цикла
(шаг).

Тема 2.3Машина Поста.


Задание 9.

Ре
шение задач по теме «Машина Поста».

1.

На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка
находится либо слева от массива, либо над одной из ячеек самого массива.

Решение
. (8 шагов)












2.

Даны два массива меток, которые находятся на

не
-

котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка
находится над крайней левой меткой первого массива.

Решение
. (10 шагов)









3.

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

Решение
. (10

шагов)






17


4.

На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается
над первой ячейкой левого массива.

Решение
. (17 шагов)









5.

На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка
р
асполагается над первой ячейкой массива.

Решение
. (13 шагов)








Задание 1
0
.

Запишите алгоритм и постройте блок
-
схему вычисления объема видеопамяти:












Задание 11
.


Определите требуемый объем видеопамяти для различных графических режимов экрана
монитора. Заполните таблицу.

Разрешающая
способность экрана

Глубина цвета (бит на точку)

4

8

16

24

32

640 на 480
















800 на 600
















1024 на 768
















1280 на 1024
















Задание 12
.

«Носители инфо
рмации»

1. Сформулируйте
определение носителя информации
______________________
____________

__________________________________________________________________________________

__________________________________________________________________________________

2. Назовите носители информации, использо
вавшиеся до появления бумаги
_____
___________

__________________________________________________________________________________
__________________________________________________________________________________


18

3.
На
рисуйте в виде петроглифа эволюцию носителей информации.







4.
Определение итерационного цикла______________________________________
___________

__________________________________________________________________________________
___________________________
_______________________________________________________

5. Определение массива_________________________________________________
_____________

__________________________________________________________________________________

6.
Определение элемента массива__
___________________
_____________________
___________

__________________________________________________________________________________

7.
Отладка алгоритма______________________
______________________________
____________

____________________________________
______________________________________________

__________________________________________________________________________________

8
.
Суть процесса исполнения алгоритма
______________________________
__________________

________________________________________
__________________________________________


Тема 2.4 Машина Тьюринга.


Задание 13.


Машина Тьюринга. Ознакомьтесь с теоретическим материалом и выполните практические
задания.

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

—

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

В каждой машине Тьюринга есть две части:

1)

неограниченная

в обе стороны

лента
, разделенная на ячейки;

2)

автомат

(головка для считывания/записи, управ
ляемая программой).

С каждой машиной Тьюринга связаны

два конечных алфавита
: алфавит входных
символов A = {a
0
, a
1
, ..., a
m
}и алфавит состояний Q = {q
0
, q
1
, ..., q
p
}. (С разными машинами
Тьюринга могут быть связаны разные алфавиты

A

и

Q
.) Состояние q
0
называ
ется

пассивным
.
Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние
q
1

называется

начальным
. Находясь в этом состоянии, машина начинает свою работу.

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

А

всегда входит
пустая буква

а
0
—

признак того, что ячейка пуста).

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



Автомат каждый раз “видит” только одну ячейку. В зависимости от того
, какую букву

ai


он видит, а также в зависимости от своего состояния

qj

автомат может выполнять
следующие действия:



· записать новую букву в обозреваемую ячейку;


19



· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться
неподвижным;



· перейти в
новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары
(
q
j
,

a
i
) машина Тьюринга выполняет команду, состоящую из трех операций с определенными
параметрами.

Программа для машины Тьюринга представляет собой таблицу, в

каждой клетке которой
записана команда.


Клетка (
q
j
,

a
i
) определяется двумя параметрами
—

символом алфавита и состоянием
машины. Команда представляет собой указание: куда п
ередвинуть головку чтения/записи,
какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения
направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или
“Н” (неподвижен).

После выполнения автомат
ом очередной команды он переходит в состояние

q
m
(которое
может в частном случае совпадать с прежним состоянием

q
j
). Следующую команду нужно
искать в

m
-
й строке таблицы на пересечении со столбцом

a
l

(букву

a
l
автомат видит после
сдвига).

Договоримся, что ког
да лента содержит входное слово, то автомат находится против
какой
-
то ячейки в состоянии

q
1. В процессе работы автомат будет перескакивать из одной
клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что
автомат должен перейт
и в состояние

q
0
. Эти клетки называются
клетками останова
. Дойдя до
любой такой клетки, машина Тьюринга
останавливается
.

Несмотря на свое простое устройство, машина Тьюринга может выполнять все
возможные преобразования слов, реализуя тем самым все возможны
е алгоритмы.

Пример.

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

Решение.

Машина должна прибавить единицу к последней цифре числа. Если последняя
цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для
данной машины Тьюринга может выглядеть так:


В этой машине Тьюринга

q
1

—

состояние изменения цифры,

q
0

—

состояние останова.
Если в состоянии

q
l

автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и
переходит в состояние

q
0
,
т.е. машина останавливается. Если же он видит цифру 9, то заменяет
ее на 0, сдвигается влево, оставаясь в состоянии

q
l
. Так продолжается до тех пор, пока автомат
не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями,
запишет 0

на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем
перейдет в состояние

q
0
, т.е. остановится.


20

Практические задания

1. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите
программу для машины Тьюринга, кото
рая каждый второй символ “+” заменит на “
–
”. Замена
начинается с правого конца последовательности. Автомат в состоянии

q
1

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

2. Дано число

n

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

n

на 1. Автомат в состоянии

q
1

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

3. Дана десятичная запись натурального числа

n

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

n

на 1. Автомат в состоянии

q
1

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

словами, что выполняется машиной в каждом
состоянии.

4. Дано натуральное число

n

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

n

на 1, при этом в выходном слове старшая цифра не должна быть 0. Например,
если входным словом было “10
0”, то выходным словом должно быть “99”, а не “099”. Автомат
в состоянии

q
1

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

5. Дан массив из открывающих и закрывающих скобок. Постро
ить машину Тьюринга,
которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.

Автомат в состоянии

q
1

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

6. Дана строка из букв “
a
” и “
b
”. Разработать машину Тьюринга, которая переместит все
буквы “
a
” в левую, а буквы “
b
”
—

в правую части строки. Автомат в состоянии

q
1 обозревает
крайний левый символ стр
оки. Кроме самой программы
-
таблицы, описать словами, что
выполняется машиной в каждом состоянии.

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

q
1

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

8. Даны два натуральных числа

m

и

n
, представленные в унарной системе счисления.
Соответствующие наборы символов “|” разделены пустой клеткой. Автома
т в
состоянии

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

m

и

n
. Кроме самой программы
-
таблицы, описать словами, что выполняется машиной в каждом состоянии.

9. Даны два нату
ральных числа

m

и

n
, представленных в унарной системе счисления.
Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в
состоянии

q
1

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

m

и

n
. Известно, что

m

�

n
. Кроме
самой программы
-
таблицы, описать словами, что выполняется машиной в каждом состоянии.

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

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




21


Тема 2.5 Нормальные алгоритмы Маркова

Задание 14.

Нормальные алгоритмы Маркова (далее

—

НАМ), введенные советским математиком
А.

А.

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

A
. Формулой подстановки в
алфавите

A

называется выражение типа

p

→

q
(простая подстановка, в эмуляторе обозначена как
-
>) или

p

↦

q

(заключительная подстановка, в эмуляторе обозначена как =>), где

p

и

q

—

некот
орые слова в алфавите

A
, называемые, соответственно, левой и правой частями формулы
подстановки. Каждый НАМ в алфавите

A

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

Применение НАМ к некоторому
слову

S

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

S
. Находится 1
-
е
вхождение левой части формулы в

S

и вместо этого вхождения подставляется правая часть
формулы. Получается новое слово

S
'
. Cо словом

S
'

производятся те же действия и т.д.

Данный процесс обрывается в 2
-
х случаях:



к очередному слову применена одна из заключительных формул
подстановки;



в слово не входит ни одна из левых частей формул подстановки.

Получаемое последнее слово яв
ляется результатом применения НАМ к исходному
слову

S
.

Примеры на составление нормальных алгоритмов Маркова

Пример 1.

В произвольном слове, состоящем из букв

{
a
,

b
,

c
}
, все подряд стоящие
одинаковые буквы заменить одной буквой (например, слово «abbbcaa» пр
ео
бразовать в «abca»).
Схема НАМ.
имеет вид:

1.
aa
→
a

2.
bb
→
b

3.
cc
→
c

Применение этой схемы с слову «abbbcaa» последовательно даст слова: «abbbca»,
«abbca» и «abca», после чего выполнение НАМ завершится. Для проверки данного алгоритма
загрузите его текст в эмул
ятор.

Пример 2.

Удвоить слово, состоящее из одинаковых символов (для определенности

—

«x»). Т.е. слово «x» надо преобразовать в «xx», слово «xx»

—

в «xxxx» и т.д.

Схема НАМ для этого примера намного сложнее, чем для примера 1. Нельзя
написать

x

→

xx
, т.к.
в этом случае на каждом шаге НАМ к слову будет добавляться символ «x»
и этот процесс будет бесконечным. Необходимо контролировать удвоение каждого символа
слова так, чтобы каждый символ удвоился только один раз. Для это введём маркер, с помощью
которого бу
дем обеспечивать контекст применения удваивающего правила.

1.

*
x

→

xx
*

2.

*

↦


3.


→

*

Последнее правило вводит «маркер» '*' (или «курсор»), который с помощью первого
правила «перескакивает» через текущий символ слова и удваивает его. Применение этой с
хемы,
например, к слову «xx» последовательно даст слова: (3) «*xx», (1) «xx*x», (1) «xxxx*», (2)
«xxxx» (в скобках указан номер применяемой формулы подстановки).

Пример 3.

Дано слово в алфавите

{
a
,

b
,

c
}
. Упорядочить буквы входного слова в
лексикографическ
ом порядке

1.

ba

→

ab

2.

ca

→

ac

3.

cb

→

bc


22


Задания для самостоятельного решения:

Принятые в тексте обозначения:



А

—

исходный алфавит алгоритмической схемы.



P

—

означает входное слово.



Λ

—

означает пустой символ для МТ или пустое слово для НАМ.

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


Базовые задачи

1.

Дан алфавит

A

=

{
a
,

b
,

c
}. Перенес
ти в начало все

a
.

2.

Дан алфавит

A

=

{
a
,

b
,

c
}. Упорядочить буквы в

P


по алфавиту.

3.

Дан алфавит

A

=

{*,

a
,

b
,

c
},

P


= *
Q

, где

*
∉
Q
. Получить

Q
*.

4.

Дан алфавит

A

=

{
a
,

b
,

c
}. Если входное слово

P


содержит букву

a

то написать

a
,
иначе

Λ

5.

Дан алфавит

A

=

{
a
,

b
,

c
}. Приписать к входному слову

P


букву

a
:

P


→
P

a
.

6.

Дан алфавит

A

=

{
a
,

b
,

c
}. Приписать к входному слову

P


слово

aba
:

P


→
P

aba
.

7.

Дан алфавит

A

=

{
a
,

b
,

c
}. Написать 1, если входное слово

P


чётной длины, иначе
написать 2.

8.

Дан алфавит

A

=

{
a
,

b
,

c
}. Удвои
ть последнюю букву входного слова

P


=

Q
ξ
:

P


→

Q

ξξ
.

9.

Дан алфавит

A

=

{
a
,

b
,

c
}. Приписать к слову

P


слева его первую букву.

10.

Дан алфавит

A

=

{
a
,

b
,

c
}. Переставить первую букву

P


в его конец.

11.

Дан алфавит

A

=

{
a
,

b
,

c
}. Удвоить каждую букву

P

.

12.

Дан алфави
т

A

=

{
a
,

b
,

c
}. Заменить последнее вхождение буквы

a

в

P


на

bb
. Если

a
∉
P

,
то оставить

P


без изменений.

13.

Дан алфавит

A

=

{
a
,

b
,

c
}

Удалить второе вхождение

a
.

14.

Дан алфавит

A

=

{
a
,

b
,

c
}. Если в

P


входит буква

a

ещё раз, тогда написать

a
, иначе

Λ
.

15.

Дан алф
авит

A

=

{
a
,

b
,

c
}. Приписать к концу

P


столько палочек, сколько раз
буква

b

входит в

P

. Пример:

abcbb

→

abcbb
|||
.

16.

Дан алфавит

A

=

{|�, },

P


= |||...||>. Входное слово

P


представляет собой запись
некоторого числа

n

в палочной системе счисления, в конце

которой стоит знак >. Дописать
число

n

в палочной системе счисления после знака > (дописать

n

палочек). Пример:
||||�

→

||||�||||.

17.

Дан алфавит

A

=

{|, −},

P


= |||...||
−
|||...||. Входное слово

P


представляет собой запись
некоторых чисел

n

и

m

в палочной системе счисления, разделённую знаком «
−
». Получить
запись модуля разности

n

и

m

в палочной системе счисления. Пример: |
−
|||

→

||.

18.

Дан алфавит

A

=

{|, *, =},

P


= |||...||*|||...||=. Входное слово

P


содержит

n

палочек слева от
знака * и

m

палоч
ек справа. В конце стоит знак =. Дописать справа от знака =

nm

палочек.
Пример: ||*|||=

→

||*|||=||||||.

19.

Дан алфавит

A

=

{
a
,

b
,

c
}. Если

P


=

abc
, то написать

a
, иначе

Λ
.

20.

Дан алфавит

A

=

{
a
,

b
}, входное слово

P


чётной длины. Стереть правую половину
слова

P

. Пример:

bab
baa

→

bab
.

21.

Дан алфавит

A

=

{
a
,

b
}. Обратить входное слово

P

. Пример:

babbaa

→

aabbab
.

22.

Дан алфавит

A

=

{0, 1}. Входное слово

P


представляет собой двоичную запись
некоторого числа

n
. Написать число

n

+

1

в двоичной системе счисления. Пример:

1011 → 1100
.

23.

Дан алфавит

A

=

{|}. Входное слово

P


представляет собой запись некоторого числа

n

в
палочной системе счисления. Написать двоичную запись числа

n
. Пример: |||||

→ 101
.

24.

Дан алфавит

A

=

{0, 1}. Входное слово

P


представляет собой двоичную запис
ь
некоторого числа

n
. Написать в двоичной системе счисления остаток от деления

n

на двоичное
число

11
2
. Пример:

101 → 10
.

Примечание
: Не смотря на то, что решение задачи в рамках двочиной системы счисления

23

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

25.

Дан алфавит

A

=

{
a
,

b
}. Удвоить входное слово

P

:

P

→
P

P

. Пример:

abb

→

abb
abb
.

Задание 15.

Выполните тестовые задания
№ 31
-
60

из
приложения.



24

Раздел
III

Основные положения и методика составления сложных алгоритмов.

Тема 3.1. Эволюция языков программирования. Системы программирования.


Задание 1.

Запишите определения
:

Нисходящее пошаговое проектирование________________________________________________

_____
_____________________________________________________________________________
__________________________________________________________________________________

Структ
у
рное программирование______________________________________________________

_____________
_____________________________________________________________________
__________________________________________________________________________________

Модульное программирование________________________________________________________

_____________________
_____________________________________________________________
__________________________________________________________________________________

Структурный контроль______________________________________________________________

_____________________________
_____________________________________________________

Ресурсы алгоритма__________________________________________________________________

__________________________________________________________________________________
Требования к алгоритму______________
_______________________________________________

__________________________________________________________________________________

Язык программирования_____________________________________________________________

__________________________________________
________________________________________

Задание 2.

Заполните схему классификации языков программирования.









Классификация ЯП


25

Задание 3.

Составить блок
-
схемы:

Линейный алгоритм

1.

Вычисление площади прямоугольника.

2.

Вычисление суммы четырех чисел.

3.

Вычисление произведе
ния трёх чисел.

4.

Вычисление площади треугольника.

5.

Вычисление частного двух чисел.

6.

Вычисление длины окружности.

7.

Вычисление площади круга.

8.

Вычисление площади квадрата.

9.

Вычисление площади параллелограмма.

10.

Вычисление заданных двух чисел и 18.

Ветвление

1.

По форме

фигуры определить, какая фигура: “квадрат”, “окружность”.

2.

Определить виды предложений.

3.

Найти значение функции
.

Дополнительное задание (составить блок
-
схем
ы):

1.

Пешеход шел по пересеченной местности. Его скорость движения по равнине v
1

км/ч, в
гору
—

v
2

км/ч и под гору
—

v
3

км/ч. Время движения соответственно t
1
, t
2

и t
3

ч. Какой
полный путь прошел пешеход?

2.

Решение квадратного уравнения.


Задание 4.

Запишите
определения:

Переменная________________________________________________________________________
__________________________________________________________________________________

Трассировка___________________________________________________________________
____
__________________________________________________________________________________

Ветвление_________________________________________________________________________
__________________________________________________________________________________

Алго
ритмический язык______________________________________________________________

__________________________________________________________________________________

Перечислите команды для работы с линейным алгоритмом_______________________________

__________
______________________________________________________
__________________

Запишите составляющие оценки алгоритма работы программы____________________________

__________________________________________________________________________________
_________________
_________________________________________________________________

Тема 3.2. Методика составления сложных алгоритмов

Задание
5
.

Основы работы с
MS

Visio

2010
.

Ознакомьтесь с основами
работы в программе
MS

Visio

2010.

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

1.

Разработать алгоритм,
который

присваивает

целой

переменной

A

значение
10

и

выводит

это значение на экран.

2.

Разработать алгоритм для

ввода

значения
величины

X
,

присваивания
величине

Y

значения

5.5
,

вычисления

значения величины

Z

= X
-

Y

и

вывода

значения величины

Z
.

Протестировать

алгоритм (составить таблицу значений)

для

X=5.5,

X=0

3.

Разработать алгоритм для ввода

четырёх целых чисел

и вычисления их

среднего
арифметического
.

Протестировать

алгоритм на исходных данных
-
5, 8,
-
1, 9.


26

4.

Разработать алгоритм для вычисления

дискриминанта

d

квадратного уравнения

ax
2

+

bx

+

c

= 0
.


5.

Разработать алгоритм для

вычисления

выражения:

S=(2x+y)(x
-
y).
Протестировать

алгоритм для следующих исходных данных:

1)

x=2,

y=1

2)

x=3,

y=0

6.

Из железной полосы дл
иной

L

метров нужно изготовить обруч. На соединение концов
уходит

D

метров полосы. Разработать схему алгоритма для вычисления

радиуса
R

обруча.

Протестировать

алгоритм для

L=5.8,

D=0.2

7.

Дано

натуральное

число

Х
. Вычислить

Y

=

X
5
. Разрешается использовать
то
лько

три

операции

умножения
. Разработать алгоритм для решения этой
задачи.

Протестировать

алгоритм для

X=
-
2

и

X=3
.


Тема 3.3. Методы определения сложности работы алгоритмов


Задание 6.

Изучите таблицу сложности алгоритма и выполните расчеты.

Рост временной

сложности алгоритма.

Алгоритм

Временная
сложность

Максимальный размер входных данных, для которых за
указанное время алгоритм может быть выполнен

1 с

1 мин


1 час

А
1

А
2

А
3

А
4

А
5

N

n log n

n
2

n
3

2
n

1000

140

31

10

9

6*10
4

4893

244

39

15

3
6
*10
6

2*10
5

189
7

153

21


Эффект десятикратного сокращения времени.

Алгоритм

Временная
сложность

Максимальный размер входных данных, для которых за
указанное время алгоритм может быть выполнен

до ускорения

после ускорения

А
1

А
2

А
3

А
4

А
5

N

n log n

n
2

n
3

2
n

S
1

S
2

S
3

S
4

S
5

10S
1

10S
2
-
S
2

3,16 S
3

2,15S
4

S
5
+3,3

Выполните расчеты временной сложности алгоритмов из задания 5.

Задание 7
.

Запишите на алгоритмическом языке задачи, предложенные в задании 5.

Задание 8
.

Выполните тестовые задания
№ 61
-
100 из
приложения.



27

Литератур
а


1.

Информатика и ИКТ. Учебник. 10 класс. Базовый уровень / Под ред. проф. Н. В.
Макаровой.
–

СПб.:Питер, 2008.
–

256с.

2.

Информатика. Задачник
-
практикум в 2т. Под ред. И. Г. Семакина, Е.К.Хеннера.
–

М.
Лаборатория Базовых Знаний, 20
1
1г.

3.

Информатика
:
Практик
ум. Под ред. И. Г. Семакина, Е.К.Хеннера.
–

М. Лаборатория
Базовых Знаний, 2011г

4.

Колмыкова Е.А., Кумскова И.А., Информатика, Учебное пособие для ССУЗ,
Издательство: Academia,2010

5.

Семакин И.Г., Хеммер Е.К. Информатика. 10 класс. М.: БИНОМ Лабор
а
тория знаний
,
2004.
–

165 с.

6.

Успенский В.А., Семенов А.Л. Теория алгоритмов: основные понятия и
приложения.
---

М.: Наука, 1987.

7.

Алгоритмы и программы решения задач на графах и сетях / Нечепуренко М.И.,
Попков В.К., Майнагашев С.М. и др.
---

Новосибирск: Наука, 1990.

8.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных
алгоритмов.
---

М.: Мир, 1979.остроение и анализ вычислительных алгоритмов



28

Приложение

Тест по курсу «Теория алгоритмов»

Специальность «Информатика и вычислительная техника»

1. Как назы
вается графическое представление алгоритма:


1) последовательность формул; 2) блок
-
схема; 3) таблица; 4) словесное
описание?

2. На рисунке представлена часть блок
-
схемы. Как называется такая вершина
:

1) предикатная; 2) объединяющая; 3) функциональная; 4)
сквозная?


3. На рисунке представлена часть блок
-
схемы. Как называется такая вершина:

1)

предикатная;

2)

объединяющая;

3)

функциональная;

4)

сквозная?

4. На рисунке представлена часть блок
-
схемы. Как она называется:

1)

альтернатива;

2)

итерация;

3)

вывод данных;

4)

следование?

5. На рисунке представлена часть блок
-
схем Как она
называется:

1)

альтернатива;

2)

композиция;

3)

цикл с предусловием;

4)

итерация?

6.

На рисунке представлена часть блок
-
схемы.

Как она называется:

1)

альтернатива;

2)

композиция;

3)

цикл с предусловием;

4)

цикл с постусловием?

7.

На рисунке представлена часть блок
-
схемы.

Как она
называется:

1)

альтернатива;

2)

композиция;

3)

цикл с постусловием;

4)

цикл с предусловием?

8.

Как называется конструкция блок
-
схемы, изображенная на
рисунке:

1)

выполнение операций;

2)

начало
-
конец алгоритма;

3)

вызов вспо
могательного алгоритма;

4)

ввод/вывод данных?

9.

Как называется конструкция блок
-
схемы, изображенная на
рисунке:

1)

выполнение операций;


29

2)

начало
-
конец алгоритма;

3)

вызов вспомогательного алгоритма;

4)

ввод/вывод данных?

10.

Как называет
ся конструкция блок
-
схемы, изо
б
раженная на рисунке:

1)

выполнение операций;

2)

начало
-
конец алгоритма;

3)

вызов вспомогательного алгоритма;

4)

ввод/вывод данных?

11.

Как называется конструкция блок
-
схемы, изображенная на рисунке:

1)

выполнение операций;

2)

начало
-
конец алгоритма;

3)

вызов вспомогательног
о алгоритма;

4)

ввод/вывод данных?

12.

Свойство алгоритма записываться в виде упорядоченной
совокупности отделенных друг от друга предписаний (директив):

1) понятность; 2) определенность; 3) дискретность; 4) массовость.


13.

Свойство алгоритма записываться в
виде только тех команд, которые находятся в
Системе Команд Исполнителя, называется:

1) понятность; 2) определенность; 3) дискретность; 4) результативность.


14.

Свойство алгоритма записываться только директивами однозначно и одинаково
интерпретируемыми раз
ными исполнителями:

1) дискретность; 2) понятность3) определенность; 4) результативность


15.

Свойство алгоритма, что при точном исполнении всех предписаний процесс

должен
прекратиться за конечное число шагов с определенным ответом на поставленную задачу:

1) понятность; 2) детерминированность; 3) дискретность; 4) результативность.


16.

Свойство алгоритма обеспечения решения не одной задачи, а целого класса

задач этого типа:

1) понятность; 2) определенность; 3) дискретность; 4) массовость.


17.

Что называют
служебными словами в алгоритмическом языке:

1)

слова, употребляемые для записи команд, входящих в СКИ;

2)

слова, смысл и способ употребления которых задан раз и навсегда;

3)

вспомогательные алгоритмы, которые используются в составе других алгоритмов;

4)

константы с по
стоянным значением?


18.

Рекурсия в алгоритме будет прямой, когда:

1)

рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к
которому в данном алгоритме имеется обращение;

2)

порядок следования команд определяется в зависимости от резуль
татов проверки некоторых
условий;

3)

команда обращения алгоритма к самому себе находится в самом алгоритме;

4)

один вызов алгоритма прямо следует за другим.


19.

Рекурсия в алгоритме будет косвенной, когда: алгоритма, к которому в данном
алгоритме имеется обраще
ние;

1)

порядок следования команд определяется в зависимости от результатов проверки некоторых
условий;

2)

команда обращения алгоритма к самому себе находится в самом алгоритме;


30

3)

один вызов алгоритма прямо следует за другим.


20.

Команда машины Поста имеет структ
уру
п
Km
,
где:

1)

п
—

действие, выполняемое головкой;
К
—

номер следующей команды, подлежащей
выполнению;
т
—

порядковый номер команды;

2)

п
—

порядковый номер команды;
К
—

действие, выполняемое головкой;
т
—

номер
следующей команды, подлежащей выполнению;

3)

п
—

по
рядковый номер команды;
К
—

номер следующей команды, подлежащей выполнению;
т
—

действие, выполняемое головкой;

4)

п
—

порядковый номер команды;
К
—

действие, выполняемое головкой;
т
—

номер клетки, с
которой данную команду надо произвести.


21.

Сколько существует

команд у машины Поста:

1)

2; 2) 4; 3) 6; 4) 8?


22.

В машине Поста останов будет результативным:

1)

при выполнении недопустимой команды;

2)

если машина не останавливается никогда;

3)

если результат выполнения программы такой, какой и ожидался;

4)

по команде «Стоп».


23.

В
машине Поста некорректным алгоритм будет в следующем случае:

1)

при выполнении недопустимой команды;

2)

результат выполнения программы такой, какой и ожидался;

3)

машина не останавливается никогда;

4)

по команде «Стоп».

24.

В машине Тьюринга рабочий алфавит:

1)

А
= {а
40

О,
Ь
А0

1, с
40

2, ...,
w
40

?};

2)

Л = {а
40

0, а
40

1, а
40

2, ..., а
40

?};

3)

Л = {а
40

0, а
41

0, о
42

0, ..., а
41

0};

4)

Л = {а,
0

0, а
20

0, о
3
о 0, ■•■, «ад 0}.


25.

В машине Тьюринга состояниями являются:

1){a
40
0, a
40

1,a
40
2, …,a
40
t};

2) {q
41
, q
42
, q
43
, …, q
4s
};

3){
q
41
, q
42
, q
43
, …, q
4s
, a
40

0, a
40

1, a
40
2,…,a
40
t};


4){
q
40
,
q
41
,
q
42
, …,
q
4
s
}.


26.

В машине Тьюринга предписание
L

для лентопротяжного механизма означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3)

остановить машину; 4) занести в яч
ейку символ.


27.

В машине Тьюринга предписание
R

для лентопротяжного механизма означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.


28.

В машине Тьюринга предписание
S

для лентопротяжного ме
ханизма означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.


29.

В алгоритме Маркова ассоциативным исчислением называется:

1)

совокупность всех слов в данном алфавите;


31

2)

совокупность всех допустим
ых систем подстановок;

3)

совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;

4)

когда все слова в алфавите являются смежными.


30.

В ассоциативном счислении два слова называются смежными:

1)

если одно из них может быть преобразовано
в другое применением подстановок;

2)

если одно из них может быть преобразовано в другое однократным применением допустимой
подстановки;

3)

когда существует цепочка от одного слова к другому и обратно;

4)

когда они дедуктивны.


31.

В алгоритме Маркова дана цепочка Р

Р,
Р
2

... Р„. Если слова
P
1
f

Р
2

Р
к
_!смежные, то цепочка называется:

1)

ассоциативной;

2)

эквивалентной;

3)

индуктивной;

4)

дедуктивной.


32.

В алгоритме Маркова дана цепочка Р Р, Р
2

...
Р
к
.
Если слова Р,, Р
2
, ..., Р
к
_, смежные и
цепочка существует и в обратную сторон
у, то слова
Р
\
лР
к

называют:

1)

ассоциативными;

2)

эквивалентными;

3)

индуктивными;

4)

дедуктивными.


33.

В алгоритмах Маркова дана система подстановок в алфавите Л = {а, Ь, с}:

abc

—

с

ba

—

cb

ca

—

ab

Преобразуйте с помощью этой системы слово
bacaabc
:
1)
cbc
; 2)
ccbcb
bc
;
3)
cbacba
;
4)
cbabc
.


34.

В алгоритмах Маркова дана система подстановок в алфавите
А =
{а,
Ь, с}:

cb

—

abc

Ьас
—

ас
cab

—

Ь

Преобразуйте с помощью этой системы слово
bcabacab
:
1)
ccb
;
2)
cab
;
3)
cbc
;
4)
bcaab
.



35.

Способ композиции нормальных алгорит
мов будет суперпозицией, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово
р,
содержащееся
i

пересечении областей определения алгоритмов
А и В;

3)

алгоритм
D

будет суперпозицией трех алгоритм
ов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В и С, а
для любого слова
р
из этого пересечения
D
(
p
)
=
А(р),
если

С(р)
=
е,
D
(
p
)
=
В(р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)

существует алгоритм
С,
являющийся с
уперпозицией алгоритмов
А
и Д

такой, что для любого входного слова
р С{р)
получается в результате

последовательного многократного применения алгоритма
А
до тех пор,

пока не получится слово, преобразуемое алгоритмом
В.


36.

Способ композиции нормальных алго
ритмов будет объединением, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово
р,
содержащееся в


32

пересечении областей определения алгоритмов
А и В;

3)

алгоритм
В
будет суперпозицией трех алгори
тмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В
и
С,
а для любого слова
р
из этого пересечения
D
(
p
)
—

A
(
p
),
если

С(р)
=
е,
D
(
p
) = В(р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)

существует алгоритм С, являющийся

суперпозицией алгоритмов
А
и Д

такой, что для любого входного слова
р С(р)
получается в результате

последовательного многократного применения алгоритма
А
до тех пор,

пока не получится слово, преобразуемое алгоритмом
В.

37.

Способ композиции нормальных алг
оритмов будет разветвлением, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово
р,
содержащееся в

пересечении областей определения алгоритмов
А
и
В;

3)

алгоритм
D

будет суперпозицией трех алго
ритмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В и С, а
для любого слова
р
из этого пересечения
D
(
p
) = А(р),
если

С(р)
=
е,
D
{
p
)
-

В{р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)

существует алгоритм С, являющий
ся суперпозицией алгоритмов
А и В,

такой, что для любого входного слова
р С{р)
получается в результате

последовательного многократного применения алгоритма
А
до тех пор,

пока не получится слово, преобразуемое алгоритмом
В.

38.

Способ композиции нормальных
алгоритмов будет итерацией, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово
р,
содержащееся в

пересечении областей определения алгоритмов
А
и
В;

3)

алгоритм
D

будет суперпозицией трех алгор
итмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В к С, а
для любого слова
р
из этого пересечения
D
{
p
)=
A
(
p
),
если

С(р)
=
е,
D
(
p
)
—

В(р),
если
С(р)
=
е,
где
е
—

пустая строка;4) существует алгоритм С,
являющий
ся суперпозицией алгоритмов
А и В,
такой, что для любого входного слова
р С(р)
получается в результате последовательного многократного применения алгоритма
А
до тех пор,
пока не получится слово, преобразуемое алгоритмом
В.

39

Свойство алгоритма записыватьс
я в виде упорядоченной совокупности отделенных
друг от друга предписаний (директив):

1)

понятность; 2) определенность; 3) дискретность; 4) массовость


40

Свойство алгоритма записываться в виде только тех команд, которые находятся в
Системе Команд Исполнителя
, называется:

1)

понятность; 2)определенность; 3) дискретность; 4) результативность.


41

Свойство алгоритма записываться только директивами однозначно и одинаково
интерпретируемыми разными исполнителями:

1) детерминированность; 2) результативность; 3) дискр
етность; 4) понятность.


42

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

1) детерминированность; 2) результативность; 3) дискретность;

4) понятность.


43

Свойство алгоритма обеспечения решения не одной задачи, а целого класса задач этого
типа
; 1) понятность; 2) детерминированность; 3) дискретность; 4) массовость.


44

Что называют служебными словами в алгоритмическом языке:


33

1.

слова, упот
ребляемые для записи команд, входящих в СКИ;

2.

слова, смысл и способ употребления которых задан раз и навсегда;

3.

вспомогательные алгоритмы, которые используются в составе других алгоритмов;

4.

константы с постоянным значением?


45

Рекурсия в алгоритме будет пря
мой, когда:

1.

рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к
которому в да
н
ном алгоритме имеется обращение;

2.

порядок следования команд определяется в зависимости от результатов проверки
некоторых условий;

3.

команда обращения алг
оритма к самому себе находится в самом алгоритме;

4.

один вызов алгоритма прямо следует за другим.


46

Рекурсия в алгоритме будет косвенной, когда:

1.

рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к
которому в да
н
ном алгоритме им
еется обращение;

2.

порядок следования команд определяется в зависимости от результатов проверки
некоторых условий;

3.

команда обращения алгоритма к самому себе находится в самом алгоритме;

4.

один вызов алгоритма прямо следует за другим.


47

Команда машины Поста
имеет структуру п
Km
, где:

1)

n

—

действие, выполняемое головкой; К
—

номер следующей команды, подлежащей
выполнению;
m

-

порядк
о
вый номер команды;

2)

n

-

порядковый номер команды; К
—

действие, выполняемое головкой;
m

—

номер
следующей команды, по
д
лежащей выпол
нению;

3)

n

—

порядковый номер команды; К
-

номер следующей команды, подлежащей
выполнению;
m

—

действие, выполняемое головкой;

4)

n

—

порядковый номер команды; К
—

действие, выполняемое головкой;
m

—

номер
клетки, с которой данную команду надо произвести.


48

Сколько существует команд у машины Поста
: 1) 2; 2) 4; 3) 6; 4) 8?


49

В машине Поста останов будет результативным
:

1)

при выполнении недопустимой команды;

2)

если машина не останавливается никогда;

3)

если результат выполнения программы такой, какой и ожидался;

4)

по

команде «Стоп».


50

В машине Поста некорректным алгоритм будет в следующем случае:

1)

при выполнении недопустимой команды;

2)

результат выполнения программы такой, какой и ожидался;

3)

машина не останавливается никогда;

4)

по команде «Стоп».


51

В машине Тьюринга р
абочий алфавит:

1)
А

= {a
40

0, b
40

1, c
40

2, … , w
40

t}; 2)
А

= {a
40

0, a
40

1, a
40

2, … , a
40

t};

3)
А

= {a
40

0, a
41

0, a
42

0, … , a
4t

0}; 4)
А

= {a
10

0, a
20

0, a
30

0, … , a
90

0}


52

В машине Тьюринга состояниями являютс
я:

1){a
40
0, a
40

1,a
40
2, …,a
40
t}; 2) {q
41
, q
42
, q
43
, …, q
4s
};

3){q
41
, q
42
, q
43
, …, q
4s
, a
40

0, a
40

1, a
40
2,…,a
40
t}; 4){q
40
, q
41
, q
42
, …, q
4s
}.



34

53

В машине Тьюринга предписание
L

для лентопротяжного механизма оз
начает:

1)

переместить ленту вправо; 2) переместить ленту влево; 3) остановить машину;

4) занести в ячейку символ.


54

В машине Тьюринга предписание
R

для лентопротяжного механизма означает
:

1)

переместить ленту вправо; 2) переместить ленту влево; 3) остановит
ь машину;

4) занести в ячейку символ.


55

В машине Тьюринга предписание
S

для лентопротяжного механизма
означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.


56

В алгоритме Маркова асс
оциативным исчислением называется:

1)

совокупность всех слов в данном алфавите;

2)

совокупность всех допустимых систем подстановок;

3)

совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;

4)

когда все слова в алфавите являются смежными.


57

В ассоциативном счислении два слова называются смежными:

1)

если одно из них может быть преобразовано в другое применением подстановок;

2)

если одно из них может быть преобразовано в другое однократным применением
допустимой подстановки;

3)

когда существует цеп
очка от одного слова к другому и обратно;

4)

когда они дедуктивны.


58

В алгоритме Маркова дана цепочка Р
P
1

Р
2

... Р
к
, Если слова
P
1

, Р
2

,..., Р
к
-
1
, смежные, то
цепочка называется:

1)

ассоциативной; 2) эквивалентной; 3) индуктивной; 4) дедуктивной
.


59

В алгоритме Маркова дана цепочка Р
P
1

Р
2

... Р
к
,. Если слова
P
1

, Р
2

,..., Р
к
-
1
, смежные и
цепочка существует и в обра
т
ную сторону, то слова Р и Р
к

называют:

1)

ассоциативными; 2) эквивалентными; 3) индуктивными; 4) дедуктивными.


60

В алгори
тмах Маркова дана система подстановок в алфавите А = {а,
b
, с}:

abc

—

с;


ba

—

cb
;


са
—

а
b
.

Преобразуйте с помощью этой системы слово
bacaabc
:

1)
cbc
; 2)
ccbcbbc
; 3)
cbacba
; 4)
cbabc
.


61

В алгоритмах Марков
а дана система подстановок в алфавите А = {а,
b
, с}:

cb
—

ab
с
;


bac
—

ac;


са
b
—

b.

Преобразуйте с помощью этой системы слово
bcabacab
:

1)

ccb
; 2)
cab
; 3)
cbc
; 4)
bcaab
.



62

Способ композиции нормальных алгоритмов будет суперпозицией, если:

1)

выходно
е слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алг
о
ритмов А и В;

3)

алгоритм
D

будет суперпозицией трех алгоритмов А В С, причем область определения
D

является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения
D
(
p
)=
A
(
p
), если С(р) = е,
D
(
p
) = В(р), если С(р) = е, где е
—

пустая строка;

4)

существует алгоритм С, являющийся суперпозицией алгоритмов А и
B

такой, ч
то для

35

любого входного слова р С(р) получается в результате последовательного многократного
применения алгоритма А до тех пор, пока не пол
у
чится слово, преобразуемое алгоритмом В.


63

Способ композиции нормальных алгоритмов будет объединением, если:

1)

выход
ное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алг
о
ритмов А и В;

3)

алгоритм
D

будет суперпозицией трех алгоритмов А В С, причем область определения

D

является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения
D
(
p
) =
A
(
p
), если С(р) = е,
D
(
p
) = В(р), если С(р) = е, где е
—

пустая строка;

4)

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


64

Способ композиции нормальных алгоритмов будет разветвлением, если:

1) выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алг
о
ритмов А и В;

3)

алгоритм
D

будет суперпозицией трех алгоритмов
A

B

C
, причем область оп
ределения
D

является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения
D
(
p
) = А(р), если С(р) = е,
D
(
p
)
—

В(р), если С(р) = е, где е
—

пустая
строка;

4)

существует алгоритм С, являющийся суперпозицией алгоритмов А

и В такой, что для
любого входного слова р С(р) получается в результате последовательного многократного
применения алгоритма А до тех пор, пока не пол
у
чится слово, преобразуемое алгоритмом В.


65

Способ композиции нормальных алгоритмов будет итерацией,
если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения а
л
горитмов А и В;

3)

алгоритм
D

будет суперпозицией трех алгоритмов
A

B

C
, причем область
определения
D

является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения

D
(
p
) = А(р), если С(р) = е,
D
(
p
)
—

В(р), если С(р) = е, где е
—

пустая строка;

4)

существует алгоритм С, являющийся суперпозицией алгоритмов

А и В такой, что для
любого входного слова р С(р) получается в результате последовательного многократного
применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

66.
Выбери правильный ответ

Команда машины Поста имеет стру
ктуру nKm, где:



n
-

действие, выполняемое головкой; K
-

номер следующей команды, подлежащей
выполнению; m
-

порядковый номер команды



n
-

порядковый номер команды; K
-

действие, выполняемое головкой;m
-

номер следующей
команды, подлежащей выполнению



n
-

порядковый номер команды; K
-

номер следующей команды, подлежащей выполнению;
m
-

действие, выполняемое головкой



n
-

порядковый номер команды; K
-

действие, выполняемое головкой; m
-

номер клетки, с
которой данную команду надо произвести

67. Выбер
и правильный ответ

Сколько существует команд у машины Поста?



2



4



6


36



8

68. Выбери правильный ответ

В машине Поста останов будет результативным:



При выполнении недопустимой команды



Если машина не останавливается никогда



Если результат вып
олнения программы такой, какой и ожидался



По команде "Стоп"

69. Выбери правильный ответ

В машине Поста некорректным алгоритм будет в следующем случае:



При выполнении недопустимой команды



Результат выполнения программы такой, какой и ожидался



Маши
на не останавливается никогда



По команде "Стоп"

70. Выбери правильный ответ

В машине Тьюринга предписание L для лентопротяжного механизма означает:



Переместить ленту вправо



Переместить ленту влево



Остановить машину



Занести в ячейку символ

71.
Выбери правильный ответ

В машине Тьюринга предписание R для лентопротяжного механизма означает:



Переместить ленту вправо



Переместить ленту влево



Остановить машину



Занести в ячейку символ

72. Выбери правильный ответ

В машине Тьюринга предписание

S для лентопротяжного механизма означает:



Переместить ленту вправо



Переместить ленту влево



Остановить машину



Занести в ячейку символ

73. Выбери правильный ответ

В алгоритме Маркова ассоциативным исчислением называется:



Совокупность всех сло
в в данном алфавите



Совокупность всех допустимых подстановок



Совокупность всех слов в данном алфавите вместе с допустимой системой подстановок



Когда все слова в алфавите являются смежными

74.Выбери правильный ответ

В ассоциативном исчислении два с
лова называются смежными:



Если одно из них может быть преобразовано в другое применением подстановок



Когда существует цепочка от одного слова к другому и обратно



Когда они дедуктивны



Если одно из них может быть преобразовано в другое однократны
м применением
допустимой подстановки

75. Выбери правильный ответ

В алгоритме Маркова дана цепочка Р Р1, Р2,..., Рn. Если слова Р1, Р2,..., Рn смежные, то цепочка
называется:



Ассоциативной



Эквивалентной


37



Индуктивной



Дедуктивной

76. Выбери правиль
ный ответ

В алгоритме Меркова дана цепочка Р Р1, Р2,...Рк. Если слова Р1, Р2,...,Рк смежные и цепочка
существует и в обратную сторону, то слова Р1 и Рк называют:



Ассоциативными



Эквивалентными



Индуктивными



Дедуктивными

77.Выбери правильный ответ

В алгоритмах Маркова дана система подстановок в алфавите Л={a,b,c}: abc
-

c; ba
-

cb; ca
-

ab.
Преобразуйте с помощью этой системы слово bacaabc



cbc



ccbcbbc



cbacba



cbabc

78. Выбери правильный ответ

В алгоритмах Маркова дана система подстановок

в алфавите A={a, b, c}: cb
-

abc; bac
-

ac; cab
-

b. Преобразуйте с помощью этой системы слово bcabacab:



ccb



cab



cbc



bcaab

79.
Вы
бери правильный ответ

Способ композиции нормальных алгоритмов будет суперпозицией, если:



Существует алгоритм С,

преобразующий любое слово р, содержащееся в пересечении
областей определения алгоритмов А и В



Выходное слово первого алгоритма является входным для второго



Алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D
является пер
есечением областей определения алгоритмов A B и C, а для любого слова р из
этого пересечения D(p)= A(p), C(p)=e, D(p)=B(p), если C(p)=е, где е
-

пустая строка



Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для
любого входног
о слова р С(р) получается в результате последовательного многократного
применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В


80. Выбери правильный ответ

Способ композиции нормальных алгоритмов будет объединением, если:



Входное слово первого алгоритма является входным для второго



Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алгоритмов А и В



Алгоритм В будет суперпозицией трех алгоритмов АВС, причем область опред
еления D
является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения D(р)=А(р), C(p)=e, D(p)=B(p), если С(р)=е, где е
-

пустая строка



Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, чт
о для
любого входного слова р С(р) получается в результате последовательного многократного
применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В

81. Выбери правильный ответ

Способ композиции нормальных алгоритмов будет разв
етвлением, если:



Выходное слово первого алгоритма является входным для второго


38



Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алгоритмов А и В



Алгоритм Д будет суперпозицией трех алгоритмов АВС,

причем область определения Д
является пересечением областей определения алгоритмов А В и С, а для любого слова р из
этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е
-

пустая строка



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

82. Выбери правильный ответ

Способ композиции норма
льных алгоритмов будет итерацией, если:



Выходное слово первого алгоритма является входным для второго



Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении
областей определения алгоритмов А и В



Алгоритм Д будет суперпозици
ей трех алгоритмов АВС, причем область определения Д
является пересечением областей определения алгоритмов А В С, а для любого слова р из этого
пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е
-

пустая строка



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

83.

В машине Тьюринга предписа
ние
L

для лентопротяжного механизма означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3)

остановить машину; 4) занести в ячейку символ.


84.

В машине Тьюринга предписание
R

для лентопротяжного механизма означает:

1) переместить ленту вправ
о; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку символ.


85.

В машине Тьюринга предписание
S

для лентопротяжного механизма означает:

1) переместить ленту вправо; 2) переместить ленту влево;

3) остановить машину; 4) занести в ячейку

символ.


86.

В алгоритме Маркова ассоциативным исчислением называется:

1.

совокупность всех слов в данном алфавите;

2.

совокупность всех допустимых систем подстановок;

3.

совокупность всех слов в данном алфавите вместе с допустимой системой

подстановок;

4.

когда все
слова в алфавите являются смежными.


87.

В ассоциативном счислении два слова называются смежными:

1.

если одно из них может быть преобразовано в другое применением подстановок;

2.

если одно из них может быть преобразовано в другое однократным применением
допусти
мой подстановки;

3.

когда существует цепочка от одного слова к другому и обратно;

4.

когда они дедуктивны.


88.

В алгоритме Маркова дана цепочка Р Р,
Р
2

... Р„. Если слова
P
1
f

Р
2

Р
к
_!смежные, то цепочка называется:

1.

ассоциативной;

2.

эквивалентной;

3.

индуктивной;

4.

деду
ктивной.



39

89.

В алгоритме Маркова дана цепочка Р Р, Р
2

...
Р
к
.
Если слова Р,, Р
2
, ..., Р
к
_,

смежные и
цепочка существует и в обратную сторону, то слова
Р
\
лР
к

называют:

1.

ассоциативными;

2.

эквивалентными;

3.

индуктивными;

4.

дедуктивными.


90.

В алгоритмах Маркова да
на система подстановок в алфавите Л = {а, Ь, с}:

abc
—

с

ba
—

cb

ca
—

ab

Преобразуйте с помощью этой системы слово
bacaabc
:
1)
cbc
; 2)
ccbcbbc
;
3)
cbacba
;
4)
cbabc
.


91.

В алгоритмах Маркова дана система подстановок в алфавите
А =
{а,
Ь, с}:

cb

—

abc

Ьас
—

ас
cab

—

Ь

Преобразуйте с помощью этой системы слово
bcabacab
:
1)
ccb
;
2)
cab
;
3)
cbc
;
4)
bcaab
.


92.

Способ композиции нормальных алгоритмов будет суперпозицией, если:

1)выходное слово первого алгоритма является входным для второго;

2)существует алгоритм

С, преобразующий любое слово
р,
содержащееся пересечении областей
определения алгоритмов
А и В;

3)алгоритм
D

будет суперпозицией трех алгоритмов
ABC
,
причем область определения
D

является пересечением областей определения алгоритмов
А В и С, а
для любого
слова
р
из этого
пересечения
D
(
p
)
=
А(р),
если
С(р)
=
е,
D
(
p
)
=
В(р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)существует алгоритм
С,
являющийся суперпозицией алгоритмов
А
и Д такой, что для любого
входного слова
р С{р)
получается в результате

последователь
ного многократного применения алгоритма
А
до тех пор,

пока не получится слово, преобразуемое алгоритмом
В.


93

Способ композиции нормальных алгоритмов будет объединением, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгор
итм С, преобразующий любое слово
р,
содержащееся в

пересечении областей определения алгоритмов
А и В;

3)

алгоритм
В
будет суперпозицией трех алгоритмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В
и
С,
а для любо
го слова
р
из этого пересечения
D
(
p
)
—

A
(
p
),
если

С(р)
=
е,
D
(
p
) = В(р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)

существует алгоритм С, являющийся суперпозицией алгоритмов
А
и Д

такой, что для любого входного слова
р С(р)
получается в результате

последовател
ьного многократного применения алгоритма
А
до тех пор,

пока не получится слово, преобразуемое алгоритмом
В.


94.

Способ композиции нормальных алгоритмов будет разветвлением, если:

1)

существует алгоритм С, преобразующий любое слово
р,
содержащееся в

пересечен
ии областей определения алгоритмов
А
и
В;

2)

алгоритм
D

будет суперпозицией трех алгоритмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В и С, а
для любого слова
р
из этого пересечения
D
(
p
) = А(р),
если

С(р)
=
е,
D
{
p
)
-

В{р),
если
С(р)
=
е,
где
е
—

пустая строка;

3)

существует алгоритм С, являющийся суперпозицией алгоритмов
А и В,

такой, что для любого входного слова
р С{р)
получается в результате

последовательного многократного применения алгоритма
А
до тех пор,


40

пока

не получится слово, преобразуемое алгоритмом
В.


95.

Способ композиции нормальных алгоритмов будет итерацией, если:

1)

выходное слово первого алгоритма является входным для второго;

2)

существует алгоритм С, преобразующий любое слово
р,
содержащееся в

пересечен
ии областей определения алгоритмов
А
и
В;

3)

алгоритм
D

будет суперпозицией трех алгоритмов
ABC
,
причем область

определения
D

является пересечением областей определения алгоритмов

А В к С, а
для любого слова
р
из этого пересечения
D
{
p
)=
A
(
p
),
если

С(р)
=
е,
D
(
p
)
—

В(р),
если
С(р)
=
е,
где
е
—

пустая строка;

4)

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


96.

Свойство алгоритма записываться в виде упорядоченной совокупности отделенных
друг от друга предписаний (директив):

1) понятность; 2) определенность; 3) дискретность; 4) массовость
.


97.

Свойство алгоритм
а записываться в виде только тех команд, которые находятся в
Системе Команд Исполнителя, называется:

1) понятность; 2) определенность; 3) дискретность; 4) результативность.


98.

Свойство алгоритма записываться только директивами однозначно и одинаково
инте
рпретируемыми разными исполнителями:

1) понятность; 2) определенность; 3) дискретность; 4) результативность.

99.Свойство алгоритма, что при точном исполнении всех предписаний процесс

должен прекратиться за конечное число шагов с определенным ответом на пос
тавленную
задачу:

1) понятность; 2) детерминированность; 3) дискретность; 4) результативность.


100.

Свойство алгоритма обеспечения решения не одной задачи, а целого класса

задач этого типа:

1) понятность; 2) определенность; 3) дискретность; 4) массовость.