Экзаменационные билеты № 1-30 по курсу «Теория вычислительных процессов и структур»

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 1.

1.  Три основные направления исследований, связанные с доказательством правильности программ

2.  Доказательство правильности программ, содержащих обращение к подпрограммам.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 2.

1.  Математическая индукция. принцип простой индукции.

2.  Доказательство частичной и полной правильности как часть процесса программирования. Программирование сверху-вниз и снизу-вверх.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 3.

1.  Математическая индукция. принцип модифицированной простой индукции.

2.  Понятие рекурсивной программы. Пример рекурсивной программы.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 4.

1.  Математическая индукция. Строгая версия математической индукции: принцип строгой индукции.

2.  Доказательство правильности рекурсивных программ.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 5.

1.  Математическая индукция. Обобщенная индукция: принцип обобщенной индукции.

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

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 6.

1.  Инварианты цикла при доказательстве правильности программ.

2.  доказательство правильности программ методом структурной индукции.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 7.

1.  Основные принципы доказательства правильности для блок-схем с использованием индукции.

2.  Структурная индукция для нерекурсивных программ.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 8.

1.  Метод индуктивных утверждений как обобщение доказательства правильности с использованием индукции

2.  Рекурсивные программы: списки. Проверки и функции работы со списками.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 9.

1.  Сокращенные доказательства правильности.

2.  Управляющие структуры.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 10.

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

2.  Структуры данных. Стандартные и абстрактные структуры.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 11.

1.  Теорема о частичной правильности.

2.  Списки. Виды списков. Операции со списками.

3.   

4.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 12.

1.  Формализация доказательства с помощью индуктивных утверждений. Множество условий верификации.

2.  Линейные списки. Виды линейных списков. Операции с ними.

3.  .

4.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 13.

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

2.  Нелинейные списки. Виды нелинейных списков. Операции с ними.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 14.

1.  Математическая индукция. Обобщенная индукция: принцип обобщенной индукции.

2.  Аксиоматический подход к доказательству частичной правильности. Его идентичность методу индуктивных утверждений.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 15.

1.  Три основные направления исследований, связанные с доказательством правильности программ.

2.  Нелинейные списки. Виды нелинейных списков. Операции с ними.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 16.

1.  Математическая индукция. принцип простой индукции.

2.  Линейные списки. Виды линейных списков. Операции с ними.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 17.

1.  Математическая индукция. принцип модифицированной простой индукции

2.  Списки. Виды списков. Операции со списками.

Задачи:

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 18.

1.  Математическая индукция. Строгая версия математической индукции: принцип строгой индукции.

2.  Структуры данных. Стандартные и абстрактные структуры.

3.  Определить язык, распознаваемый данным конечным автоматом

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

__________________________________________________________________________________________________

Экзаменационный билет
по курсу «Теория вычислительных процессов и структур»

Вариант № 19.

4.  Три основные направления исследований, связанные с доказательством