Тесты по курсу «информатика»



Скачать 130.91 Kb.
Дата15.01.2013
Размер130.91 Kb.
ТипТесты

Приложение к курсу лекций




Профессор Л. Н. Столяров




КОНТРОЛЬНЫЕ ТЕСТЫ ПО КУРСУ «ИНФОРМАТИКА»


(для студентов 2 курса ФОПФ)


Кафедра информатики МФТИ – 2004 г.

Теоретические основы CS. Тесты.

  1. Теория отношений.




    1. Заданы множества



Отметить истинное утверждение:

а).

б).

в).
Отметить истинное утверждение:

а).

б).

в).
1.3. Заданы множества и , на декартовом произведении

заданы два бинарных отношения:





Отметить следующее истинное утверждение:

a).

б).

в).

Теоретические основы CS. Тесты.

  1. Теория отношений.


1.4. На множестве задано бинарное отношение α из , где «gif" name="object23" align=absmiddle width=12 height=13>» операция приписывания символа

.

Отметить траекторию (последовательность символов) не принадлежащую

:

а).

б).

в).
1.5. На множестве слов в алфавите задан язык , где «» – операция конкатенакции, а «» – операция итерации.

Отметить слово, не принадлежащее языку L:

а). b

б). abb

в). aabba

Теоретические основы CS.Тесты.

  1. Теория алгоритмов. Машины Тьюринга.


2.1. Недетерминированная МТ определяется алфавитом входной ленты

;

действий {R – движение вправо, L – движение влево, stop – остановка};

состояний

программой .

МТ на пустой ленте, начиная работу из s0 и заканчивая в sk порождает слова языка L из .

Отметить слова, которые не порождаются этой МТ:

а). bbbb

б). bbaaa

в). baba

2.2. Для распознавания слов языка построены две машины Тьюринга с программами:













МТ1 и МТ2 начинают работу с маркера начала слова  и заканчивают в состоянии sk, когда лента пуста.

Отметить истинные утверждения:

а). 1распознаёт L

б). 2 распознаёт L

в). 1 2 не распознают L

Теоретические основы CS.Тесты.

  1. Теория алгоритмов. Машины Тьюринга.


2.3. Для преобразования слов построены две машины Тьюринга с программами:





Отметить истинные утверждения:

а). 1 преобразует, а 2 не преобразует

б). 1 не преобразует, а 2 преобразует

в). 1 и 2 преобразуют

Теоретические основы CS. Тесты.

  1. Информационная структура алгоритмов (ИСА). Рекурсивные функции. Процессорные реализации.




    1. Функция Фибоначчи, заданная примитивно–рекурсивной схемой подстановок:







реализуется в специальном процессоре с единственной операцией «+» и разделяемыми (общими) регистрами. Какое минимальное количество регистров может иметь процессор?

а). 2 регистра

б). 3 регистра

в). 4 регистра

Показать на графе ИСА функции Фибоначчи.


    1. Функция задана формулой

и реализована в процессоре, имеющим два независимых вычислителя («+» и «*») и общие (разделяемые) регистры. Какое минимальное количество регистров может иметь процессор?

а). 2 регистра

б). 3 регистра

в). 4 регистра

Показать на графе ИСА.

Теоретические основы CS. Тесты.

  1. Информационная структура алгоритмов (ИСА). Рекурсивные функции. Процессорные реализации.




    1. Система из двух функций и , связанных взаимными подстановками

;

, вычисляются параллельно на вычислительной системе, состоящей из двух микропроцессоров (один вычисляет О1, другой – О2) за 4 такта. Отметить правильное двухпроцессорное разложение для заданной системы функций:

а).

б).

в).

Показать на графе ИСА.

3.4. Система из двух функций и , связанных взаимными подстановками , вычисляются параллельно на вычислительной системе, состоящей из двух микропроцессоров (один вычисляет О1, другой – О2) с разделяемыми общими регистрами за 4 такта.

Указать минимальное количество регистров для реализации этой системы функций:

а). 2 регистра

б). 3 регистра

в). 4 регистра

Показать на графе ИСА.

Теоретические основы CS. Тесты.

  1. Информационная структура алгоритмов (ИСА). Рекурсивные функции. Процессорные реализации.


3.5. Система из двух функций и , связанных взаимными подстановками ;

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

а). 2 регистра

б). 3 регистра

в). 4 регистра

Показать на графе ИСА.

Теоретические основы CS. Тесты.

  1. Функции алгебры логики. Тождественные преобразования.




    1. Отметить верное равенство:

а).

б).

в).

    1. Отметить верное равенство:

а).

б).

в).

4.3. Функция задана подстановками из штрихов Шеффера и реализована полиномом Жегалкина.

Отметить верное равенство:

а).

б).

в).

    1. Операция поразрядного суммирования задана формулами, где pi – функция переноса, ci – функция суммы, – одноразрядные бинарные числа. Указать формулы, которые не реализуют эту операцию:

а).



б). ;



в). ;



Теоретические основы CS. Тесты.

  1. Классы Поста. Полные наборы функций алгебры логики.


5.1. Отметить верное утверждение:

а). Функция относится к классам

б). Функция относится к классам

в). Функция относится к классам
5.2. Отметить неполный набор функций:

а).

б).

в).
5.3. Отметить правильную принадлежность функции к классам Поста:





P0

P1

S

L

M

а).

-

+

+

-

+

б).

+

-

-

+

-

в).

+

+

+

+

-




    1. Отметить правильную принадлежность функции к классам Поста:






P0

P1

S

L

M

а).

-

-

+

-

-

б).

+

-

+

+

+

в).

+

+

-

+

+


Теоретические основы CS. Тесты.

  1. Минимальное представление функций алгебры логики. Минимальные ДНФ. Диаграммы Вейча.


6.1. Функция от переменных задана диаграммой Вейча:

5

1

3

7

4

0

2

6


Указать ДНФ, которая соответствует заданной диаграмме Вейча:

а).

б).

в).
6.2. Задана функция от переменных, которая представима в виде минимальной ДНФ: x2.

Какая диаграмма Вейча соответствует этой функции?

1.

5

1

3

7

4

0

2

6

2.

5

1

3

7

4

0

2

6

3.

5

1

3

7

4

0

2

6


6.3. На диаграмме Вейча (6.1) задана функция от переменных .

Отметить правильную принадлежность этой функции к классам Поста:




P0

P1

S

L

M

а).

+

+

-

+

-

б).

-

-

+

+

-

в).

+

+

-

-

-


Теоретические основы CS. Тесты.

  1. Исчисление высказываний. Выводимость, следование.


7.1. Указать, какие формулы являются теоремами исчисления высказываний (ИВ)



.

а). F1теорема ИВ

б). F2теорема ИВ

в). F1 и F2 теоремы ИВ
7.2. Заданы формулы

.

Указать истинные утверждения:

а). Из F1 и F2 выводима F4

б). Из F1 и F3 выводима F4

в). Из F2 и F2 выводима F4
7.3. Отметить формулы, которые не являются тавтологиями:

а).

б).

в).

Теоретические основы CS. Тесты.

8. Исчисление предикатов. Теория классов.
8.1. Какие схемы силлогизмов в теории классов не являются тождественно истинными?

а). В первой фигуре ААЕ

б). Во второй фигуре АЕО

в). В четвертой фигуре IAI
8.2. Какие схемы силлогизмов теории классов являются истинными в третьей фигуре?

а). ААА

б). AIE

в). ОАО
8.3. Для каких схем силлогизмов в теории классов истинны утверждения:





I

II

III

IV

а). ААА тождественно истинны в фигурах

+

+

-

-

б). ЕАЕ тождественно истинны в фигурах

+

+

-

+

в). ЕАО тождественно истинны в фигурах

+

+

+

+


Теоретические основы CS. Тесты.

  1. Конечные автоматы. Автоматические грамматики.

Регулярные выражения.
9.1. Указать регулярное выражение, которое распознаёт конечный автомат с правилами

.

а).

б).

в).
9.2. Указать, какой язык порождает автоматная грамматика



а).

б).

в).
9.3. Указать какие слова не допускает (не распознаёт) конечный автомат с правилами

.

а). abaab

б). aab

в). baab
9.4. Указать, какое слово не порождает автоматная грамматика

а). bbb

б). ababa

в). babab

Теоретические основы CS. Тесты.

10. Магазинные автоматы. Контекстно–свободные грамматики.
10.1. Указать, какое из приведенных слов порождает КС–грамматика с правилами

.

а).

б).

в).
10.2. Указать, какое из приведенных слов не допускает (не распознаёт) магазинный автомат с правилами





.

а).  ((( )))

б).  ((а + а + а) + а)

в).  а((а + а) + а)


Похожие:

Тесты по курсу «информатика» iconРуководство по выполнению лабораторных работ по курсу "Информатика "
Данное руководство призвано оказать помощь при выполнении лабораторных работ по курсу “Информатика” студентами очной и очно-зачной...
Тесты по курсу «информатика» iconТема Социальная информатика
Методические указания для самостоятельной работы студентов по курсу «информатика»
Тесты по курсу «информатика» iconРабочая программа по курсу "Информатика" Специальность: 010501 «Прикладная математика и информатика»
Для многих дальнейших предметов, связанным с информационными технологиями, знания, полученные в ходе изучения информатики, являются...
Тесты по курсу «информатика» iconМетодические рекомендации по выполнению расчетного задания по курсу «Информатика» для студентов специальностей 200106 «Информационно-измерительная техника и технологии»
Методические рекомендации предназначены в качестве руко-водства к самостоятельной работе студентов первого курса технических специальностей,...
Тесты по курсу «информатика» iconСписок вопросов к экзамену по курсу “Информатика и программирование”
Информатика. Этапы решения задач. Алгоритм. Программа. Языки программирования, их характеристика. Синтаксис, семантика, прагматика....
Тесты по курсу «информатика» iconПрограмма по курсу: логика и информатика по выбору
Информатика требует соединения фундаментальной теории и серьезной практики. Необоснованные «новые» решения стали страшнейшим врагом...
Тесты по курсу «информатика» iconКнига содержит набор сведений, изложенных в лаконичной форме и позволяющих получить ответы на основные вопросы по курсу «Информатика»
Информатика: Учеб пособие / В. А. Каймин. 2-e изд. М.: Риор, 2011. 124 с.: 70x100 1/32. (Карманное учебное пособие). (обложка, карм...
Тесты по курсу «информатика» iconМетодические разработки по курсу «Теория вероятностей» для студентов, обучающихся по специальности "Прикладная информатика"
Методы вычислений вероятностей случайных событий: Методические разработки по курсу «Теория вероятностей и математическая статистика»...
Тесты по курсу «информатика» iconТесты по курсу «Философия»
С. П. Батурин, доцент Кемеровского института (филиала) ргту, кандидат исторических наук
Тесты по курсу «информатика» iconОбразовательная программа по курсу: «Прикладная информатика и моделирование»

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org