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

Чтобы посмотреть этот 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) массовость.