Теория вычислительных процессов

Федеральное агентство связи

ФГОБУ ВПО «Сибирский государственный университет

телекоммуникаций и информатики»

Уральский технический институт связи и информатики (филиал)

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

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

для студентов заочной формы нормативного срока обучения

на базе среднего (полного) общего образования направления

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

в соответствии с требованиями ФГОС ВПО 3 поколения

Екатеринбург

2011

ББК 32.973.202

УДК 004.7

Рецензент: к. т.н., доцент кафедры ИСиТ

Теория вычислительных процессов: Методические указания по выполнению домашней контрольной работы / . — Екатеринбург: УрТИСИ ФГОБУ ВПО «СибГУТИ» 2011 — 19с.

Методические указания предназначены для выполнения домашней контрольной работы по дисциплине «Теория вычислительных процессов» студентами заочной формы обучения на базе среднего (полного) общего образования по направлению 230100 «Информатика и вычислительная техника».

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

Рекомендовано НМС УрТИСИ ФГОБУ ВПО СибГУТИ в качестве методических указаний по выполнению домашней контрольной работы по дисциплине «Теория вычислительных процессов» студентами заочной формы обучения на базе среднего (полного) общего образования по направлению 230100 «Информатика и вычислительная техника»

ББК 32.973.202

УДК 004.7

Кафедра информационных систем и технологий

Ó УрТИСИ ФГОБУ ВПО «СибГУТИ», 2011

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 4

Содержание дисциплины.. 5

Общие указания по оформлению домашней контрольной работы.. 11

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

Варианты заданий домашней контрольной работы.. 17

ЛИТЕРАТУРА.. 19

ВВЕДЕНИЕ

Методические указания по выполнению домашней контрольной работы составлены в соответствии с рабочей программой по дисциплине «Теория вычислительных процессов» предназначены для студентов заочной формы обучения на базе среднего (полного) общего образования по направлению 230100 «Информатика и вычислительная техника».

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

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

Содержание дисциплины

1. Цели и задачи дисциплины

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

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

2. Место дисциплины в структуре ООП

Дисциплина «Теория вычислительных процессов» относится к числу дисциплин профессионального цикла вариативной части ООП для подготовки бакалавров по направлению 230100 «Информатика и вычислительная техника».

Теоретической основой дисциплины «Теория вычислительных процессов» являются основные положения дисциплин: «Дискретная математика», «Математическая логика и теория автоматов», «Структуры и алгоритмы обработки данных».

Рабочая программа по дисциплине «Теория вычислительных процессов» предназначена для подготовки по направлению 230100 «Информатика и вычислительная техника» на базе среднего (полного) общего образования и соответствует требованиям Государственного образовательного стандарта ВПО направления подготовки бакалавра по специальности 230100 «Информатика и вычислительная техника».

3. Требования к результатам освоения дисциплины

Перечень формируемых компетенций

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

·  способностью самостоятельно приобретать с помощью информационных технологий и использовать в практической деятельности новые знания и умения, в том числе в новых областях знаний, непосредственно не связанных со сферой деятельности (ОК-6);

·  способностью к разработке моделей различных технологических процессов и проверке их адекватности на практике; готовностью использовать пакеты прикладных программ анализа и синтеза телекоммуникационных систем и сетей (ПК-2).

В результате освоения дисциплины студент должен:

Знать:

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

·  новые способы формального описания языков программирования;

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

·  конструктивные принципы построения, алгоритмы и способы реализации сетей Петри;

·  способы формальной спецификации и верификации.

Уметь:

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

·  разрабатывать алгоритмы функционирования трансляторов и компиляторов;

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

·  использовать методы моделирования и средства формализации, алгоритмизации и реализации модели на ЭВМ.

Иметь навыки:

·  построения алгоритмов, применения методов моделирования.

4. Объем дисциплины и виды учебной работы

Общая трудоемкость дисциплины составляет 4 зачетные единицы.

Виды учебной работы, формы контроля	Всего, час.	Учебные семестры
144	N4
Общая трудоемкость по учебному плану	144	144
Аудиторные занятия	16	16
Лекции (Л)	8	8
Практические занятия (ПЗ)	2	2
Лабораторные работы (ЛР)	8	8
Самостоятельная работа студентов (СРС)
объем в часах	126	126
Работа домашняя (РД)
Подготовка к аудиторным занятиям (ПАЗ)
Вид промежуточного контроля
Курсовой проект (КП)
Трудоемкость в зачетных единицах	4	4

5. Содержание дисциплины

5.1 Содержание разделов дисциплины

5.1.1 Вычислительные процессы

1 Программные продукты и их основные характеристики. Структура жизненного цикла программ

1.  Модели вычислительных процессов.

Понятие процесса. Концепция организации процесса. Параллельные и последовательные процессы с учетом разделения ресурсов. Модельные интерпретации – генерация объектных моделей. Методы структурирования состояний.

2.  Взаимодействие процессов.

Процесс взаимодействия. Законы последовательных и параллельных взаимодействующих процессов. Обмен сообщениями. Предметная интерпретация моделей.

3.  Виды ресурсов и их использование.

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

5.1.2 Семантическая теория программ

1.  Семантика языка программирования.

Семантическое построение языка программирования и перевод. Контекстно-зависимые свойства языка. Понятие атрибута. Атрибутные транслирующие грамматики и перевод. Дерево вывода в атрибутной транслирующей грамматике. Вычисление значений атрибутов. Построение схем программ.

2.  Методы лексического анализа языка.

Лексический анализатор. Построение диаграммы лексического анализатора. Включение семантики в диаграмму лексического анализатора. Реализация лексического анализатора.

3.  Методы синтаксического анализа языка.

Синтаксический анализ языков. Нисходящие и восходящие методы синтаксического анализа. Метод рекурсивного спуска.

4.  Верификация программ.

Понятие верификации и поиск ошибок. Правильность работы программы. Методы доказательства правильности программ. Метод индуктивных утверждений Флойда. Доказательное программирование. Символьное выполнение. Абстрактная интерпретация. Правила верификации К. Хоара.

5.1.3 Сети Петри

1.  Особенности использования сетей высокого уровня.

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

2.  Моделирование систем на основе сетей Петри.

Правила выполнения сетей Петри. События и условия. Одновременность процессов и конфликты. Моделирование параллельных систем взаимодействующих процессов. Протоколы и интерфейсы.

3.  Способы реализации и применение сетей Петри.

Способы и методы, особенности реализации и организации построения сетей Петри. Области применения, принципы построения, алгоритмы поведения.

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

1 Работа в группе

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

5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	№ разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин
1	2	3	4	5	6	7	8	…
1
2
3

5.3. Разделы дисциплин и виды занятий

№ п/п	Наименование раздела дисциплины	Лекц	Лаб. зан.	Практич	СРС	Всего час.
I	Вычислительные процессы	2			28	30
II	Семантическая теория программ	2	6		34	42
III	Сети Петри	2	2	2	34	40
IV	Перспективные направления исследований формальных средств моделирования вычислительных процессов и структур	2			30	32
	Итого по дисциплине	8	8	2	126	144

6. Практические занятия и самостоятельная работа

6.1 Лабораторный практикум

№ п/п	№ раздела дисциплины	Тематика практических занятий (семинаров)	Трудоемкость (час.)
1.	II	Интерпретация стандартных схем программ Построение транслятора	2
2.	II	Высказывания. Вычисление и исчисление высказываний	2
3.	II	Методы нисходящего анализа Методы восходящего анализа Реализация методов верификации программ.	2
4.	III	Реализация и исследование сетей Петри.	2

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

№ п/п	№ раздела дисциплины	Тематика практических занятий (семинаров)	Трудоемкость (час.)
1.	III	Анализ сети Петри на основе матричных уравнений.	2

7. Учебно-методическое обеспечение

а) Основная литература

1  Молчанов программное обеспечение. – СПб.: Питер, 2006. – 395с.

2  Свердлов программирования и методы трансляции. – СПб.: Питер, 2007. – 637с.

3  Компьютерные сети. – СПб.: Питер, 2008 – 991с.

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

1.  Сырецкий . Фундаментальный курс. Том 1, 2. – Москва, 2005- 234с.

2.  Душин основных информационных процессов и систем. – Москва, 2009 – 348 с.

3.  Русская компьютерная библиотека. URL: http://www. rusdoc. ru

в) программное обеспечение

1.  Ms Office.

2.  Среда программирования Delphi.

8. Материально-техническое обеспечение дисциплины:

Компьютерный класс, оборудованный персональными компьютерами с установленным программным обеспечением, соответствующим дисциплине и проекционным экраном.

9. Методические рекомендации по организации изучения дисциплины:

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

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

Общие указания по оформлению домашней контрольной работы

Для успешного усвоения студентами курса «Теория вычислительных процессов» программой предусмотрена домашняя контрольная работа (ДКР).

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

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

При выполнении домашней контрольной работы необходимо придерживаться следующих требований:

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

2  Оформлять с соблюдением требований ГОСТ ЕСКД.

3  Ответы должны быть краткими, развернутыми по существу вопроса.

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

5  Формулы необходимо пояснять.

6  После выполнения работы нужно привести список использованной литературы, поставить дату и подпись.

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

8  Оформить работу необходимо отдельным документом на листах формата А4, в отпечатанном виде в отдельной папке.

9  Исходные файлы программы и ДКР, оформленную в электронном виде записать на диск и вложить в папку с подготовленным отпечатанным вариантом ДКР.

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

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

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

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

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

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

Множества символов полного базиса:

1.  Х = {x, х1, х2..., у, у1 у2..., z, z1, z2...} - множество символов, называемых переменными;

2.  F = {f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)...} - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

3.  Р = {р(0), р(1), р(2)...; q(0), q(1), q(2)...; } - множество предикатных символов; р(0), q(0) - ; нульместные символы называют логическими константами;

4.  {start, stop, ..., := и т. д.} - множество специальных символов.

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

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

2.  слово τ вида f(n)(τ1, τ2, ..., τn), где τ1, τ2, ..., τn - термы, является термом;

3.  те и только те слова, о которых говорится в п. п. 1,2, являются термами.

Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1, τ2,..., τn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2)(f(2)(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

1.  начальный оператор - слово вида start(х1, х2...хк), где k ≥0, а х1, х2...хк - переменные, называемые результатом этого оператора;

2.  заключительный оператор - слово вида stop(τ1, τ2,..., τn), где n ≥ 0, а τ1, τ2,..., τn - термы; вхождения переменных в термы τ называются аргументами этого оператора;

3.  оператор присваивания - слово вида х := τ, где х – переменная (результат оператора), а τ - терм; вхождения переменных в термы называются аргументами этого оператора;

4.  условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;

5.  оператор петли - односимвольное слово loop.

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

Подклассы используют ограниченные базисы. Так, например, подкласс V1 имеет базис: {х1, х2}, {а, f(1)}, {p(1)}, {start, stop, (,),:=, ,} и множество операторов {start(х1, х2); х1:=f(x1), x2:=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop(х1, х2)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

Графовая форма стандартной схемы

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

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

1.  Начальная вершина (ровно одна) помечена начальным оператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.

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

3.  Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.

4.  Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).

5.  Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.

Конечное множество переменных схемы S составляют ее память ХS.

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

Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2,...). Начальная вершина всегда помечается меткой 0.

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

Пример правильной ССП S1 в графовой форме приведен на рисунке 1.

Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины.

Линейная форма стандартной схемы

Для использования линейной формы СПП множество специальных символов расширим дополнительными символами {:, goto, if, then, else}. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

1.  если выходная дуга начальной вершины с оператором start(х1,..., хn) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(х1,..., хn) goto L;

2.  если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=τ, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: x:= τ goto L1;

3.  если вершина с меткой L - заключительная вершина с оператором stop(τ1,...τm), то ей соответствует инструкция:

L: stop(τ1,..., τm);

4.  если вершина с меткой L - распознаватель с условием р(τ1,...τk), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция:

L: if р(τ1,...τk) then L1 else L0;

5.  если вершина с меткой L - петля, то ей соответствует инструкция:

L: loop.

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

0: start(х) goto 1, start(х),

1: у:=а goto 2, у:=а,

2: if р(х) then 5 else 3, 2: if р(х) then 5 else 3,

3: у:=g(x, y) goto 4, 3: у:=g(x, y),

4: х:=h(x) goto 2, х:=h(x) goto 2,

5: stop(у). 5: stop(у).

Рисунок 1 - Полная и сокращенная линейные формы ССП

Интерпретация стандартных схем программ

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

Понятие можно ввести следующим образом:

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

1.  каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

2.  каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;

3.  каждому функциональному символу f (n) - всюду определенную функцию F(n) = I(f (n));

4.  каждой логической константе р(0) - один символ множества {0,1};

5.  каждому предикатному символу р(n) - всюду определенный предикат P (n) = I(p(n)).

Пара (S, I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).

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

Состоянием памяти программы (S, I) называют функцию W: XS D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма τ при интерпретации I и состоянии памяти W (обозначим τI(W)) определяется следующим образом:

1.  если τ = х, x – переменная, то τI(W) = W(x);

2.  если τ = a, a – константа, то τI(W) = I(a);

3.  если τ = f(n)(τ1, τ2..., τn), то τI(W) = I(f (n))(τ1I(W), τ2I(W),..., τnI(W)).

Аналогично определяется значение теста p при интерпретации I и состоянии памяти W или pI(W): если p = р(n)(τ1, τ2,..., τn), то pI(W) = I(p(n))(τ1I(W), τ2I(W),... τnI(W)), n ≥ 0.

Конфигурацией программы называется пара U = (L, W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которая называется протоколом выполнения программы (ПВП).

Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S, I) определяем следующим образом (ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui = (ki, Wi)): U0 = (0, W0), W0 – начальное состояние памяти схемы S при интерпретации I.

Пусть Ui = (ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stop(τ1, τ2... τn), то Ui - последняя конфигурация, так что протокол конечен. В этом случае считается, что, программа (S, I) останавливается, а последовательность значений τ1I(W), τ2I(W),..., τnI(W) является результатом val(S, I) выполнения программы (S, I). В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация Ui+1 = (ki+1, Wi+1), причем

1.  если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

2.  если О - оператор присваивания х:= τ, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(х) = τ1(Wi);

3.  если О - условный оператор p и pI(Wi) = Δ, где Δ {0,1}, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

4.  если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.

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

Пусть даны две интерпретации СПП. Интерпретация (S1, I1) задана так:

область интерпретации D1 Nat - подмножество множества Nat целых неотрицательных чисел;

  1)  I1(x)=4; I1(y)=0; I1(a)=1;

  2)  I1(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2;

  3)  I1(h)=H, где H - функция вычитания единицы, т. е. H(d)= d - 1;

  4)  I1(p)=P1, где P1 - предикат «равно 0», т. е. P1(d)=1, если d=0.

Программа (S1, I1) вычисляет 4!.

Интерпретация (S1, I2) задана следующим образом:

область интерпретации D2=V*, где V = {a, b, c}, V* - множество всех возможных слов в алфавите V.

  1)  I2(x)=abc;

  2)  I2(y)=e, где e - пустое слово;

  3)  I2(a)= e;

  4)  I2(g)=CONSTAR;

  5)  I2(h)=CDR;

  6)  I2(p)=P2, где P2 - предикат «равное e», т. е. P2(a)=1, если a=e.

Программа (S1, I2) преобразует слово abc в слово cba (рисунок 1, в).

ПВП (S1, I1) и (S1, I2) конечен, результат - 24 и - cba (таблица 1.1 и 1.2).

Таблица 1.1.

Конфигурация	U0	U1	U2	U3	U4	U5	U6	U7	U8	U9	U10	U11	U12	U13
Метка	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Значения	x	4	4	4	4	3	3	3	2	2	2	1	1	1	0
	y	0	1	1	4	4	4	12	12	12	24	24	24	24	24

Таблица 1.2

Конфигурация

U0

U1

U2

U3

U4

U5

U6

U7

U8

U9

U10

U11

U12

Метка

0

1

2

3

4

5

6

7

8

9

10

11

12

Значения

x

abc

abc

abc

abc

bc

bc

bc

c

c

c

e

e

e

y

e

e

e

a

a

a

ba

ba

ba

cba

cba

cba

cba

Варианты заданий домашней контрольной работы

Задание включает в себя следующие части, общие для всех вариантов:

1. Написать программу решения задачи в зависимости от варианта (блок-схема, листинг, скомпилированный файл с расширением *exe ). Задачи приведены ниже. Язык разработки выбирается по согласованию с преподавателем.

2. Описать базис ССП (Стандартная Схема Программы).

3. Составить ССП в линейной и графовой форме.

4. Указать интерпретацию ССП и представить протокол тестового выполнения программы.

Задачи:

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

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

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

4.  Начиная с центра, обойти по спирали все элементы квадратной матрицы размером 13х13 (распечатывая их в порядке обхода).

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

6.  Задано множество М точек на плоскости. Определить, верно ли, что для каждой точки А €М существует точка B €М (A≠ В) такая, что не существует двух точек множества М, лежащих по разные стороны от прямой АВ.

7.  По заданной квадратной матрице размером 10×10, построить вектор длиной 19, элементы которого - максимумы элементов, диагоналей, параллельных главной диагонали.

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

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

10.  Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границы. Определить площадь многоугольника.

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

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

13.  Вводится последовательность, состоящая из N пар символов (ai, bi). Каждая пара определяет порядок предшествования символов, например, пара (b, с) означает, что символ "b" предшествует символу "с". Из порядка (b, с) и (с, a) следует порядок (b, a). Необходимо определить, является ли введенная последовательность полной, т. е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования.

14.  По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S - тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

Ответить на вопросы (являются общими для всех вариантов):

1  Что называется Стандартной схемой программ?

2  Какие составляющие включает в себя базис ССП?

3  Каким образом строиться графовая форма программы?

4  Какие ключевые моменты необходимо отразить при построении линейной формы программы?

5  Что исследуется при построении интерпретации ССП?

ЛИТЕРАТУРА

Основная:

1.  Рабинович вычислительных процессов. : учебник / . НГТУ, 2007 – 228 с.

Дополнительная:

2.  Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. – М.: Мир, 1984. – 264 с.

3.  Языки программирования: разработка и реализация/ Под общей ред. А. Матросова. – СПб.: Питер, 2002. – 688 с.

4.  Взаимодействующие последовательные процессы: Пер. с англ. – М.:Мир, 1989. – 264 с.

5.  Русская компьютерная библиотека. URL: http://www. rusdoc. ru