Главная > Вопросы к экзамену


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

1. В чем состоит основная идея алгоритмического метода «разделяй и властвуй» ?

  • Задача разбивается на приоритеты по важности решения.

  • Задача выполняется сверху донизу а потом проверяется выполнение снизу доверху.

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

  • Задача выполняется поэтапно с выбором оптимального решения на каждом этапе.

2. Какие принципы позволяют распознать, определяет ли «жадный» алгоритм оптимальное решение применительно к данной задаче?

Принципы «разделяй и властвуй».

Принципы разрешимости.

+ Принцип жадного выбора и свойство оптимальности для подзадач.

Принципы достаточности и необходимости.

3. Что подразумевается в теории алгоритмов когда говорят, что время выполнения программы T(n) имеет порядок О(n2 ) ?

 c>0  n0>0 : n  n0  T(n)  cn2

 c>0  n0>0 : n  n0  T(n)  cn2

 c>0  n0>0 : n  n0  T(n)  cn2

 c>0  n0>0 : n  n0  T(n)  cn2

4. Какое соотношение принято между классами задач P, NP и NPC в теории алгоритмов?

(P=NP)  NPC.

(NP=NPC)  P.

(P=NPC)  NP.

(P≠NP)  NPC.

(P≠NPC) NP.

5. С чем связана возможность использования жадных алгоритмов Крускала и Прима для поиска оптимальных остовых ( покрывающих )деревьев графа?

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

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

С тем, что граф можно задать матрицей смежности.

С тем, что граф можно задать матрицей инцидентности.

6. При условии, что полное бинарное дерево имеет 128 листьев, определите :

1) высоту этого дерева; 2) количество вершин.

1) – 7; 2) – 127.

1) - 7; 2) – 95.

1) – 9; 2) – 127.

1) – 9; 2) – 95.

1) – 8; 2) – 127.

1) - 8; 2) – 95.

7. Пусть задан двуместный предикат P(x,y) : «x любит y». Как с помощью логики предикатов представить фразу – « Каждого человека кто-то любит» ?

xyP(x,y).

xyP(x,y).

yxP(x,y).

xyP(x,y).

8. Что составляет сигнатуру алгебраической системы?

  1. Множества и операции над ними.

  2. Отношения и их свойства.

  3. Символьная матлогика.

  4. Символы алгебраических операций и отношений.

9. Какого типа является алгебраическая система { N; +,-; < } ?

    • < 2, 1; 1 >

    • + < 2, 2; 2 >

    • < 2, 1 >

    • < 2, 2 >

10. Какой высоты возможно построить двоичное дерево поиска на множестве ключей

{ 4,10,1,5,21,16,17 } ?

Возможные высоты – 2, 3, 4, 5, 6.

Возможные высоты – 2, 3, 4, 5, 6,7

Возможные высоты – 2, 3, 4, 5

Возможные высоты – 1, 2, 3, 4, 5

11. Множество А состоит из 3-х элементов, множество В – из двух. Сколько существует : 1) инъекций А в В; 2) сюръекций А в В; 3) инъекций В в А; 4) сюръекций В в А ?

  1. 1) – 0; 2) – 6; 3) – 6; 4) – 0.

  2. 1) – 3; 2) – 6; 3) – 6; 4) – 3.

  3. 1) – 3; 2) – 3; 3) – 3; 4) – 3.

  4. 1) – 0; 2) – 0; 3) – 6; 4) – 6.



Скачать документ

Похожие документы:

  1. По курсу «математический анализ» для специальности 090105 «комплексное обеспечение информационной безопасности автоматизированных систем» (иб)

    Рабочая программа
    ... вопросах математического анализа; основные положения теории пределов и непрерывных функций, теории числовых и функциональных рядов, теории ... покурсу математического анализа / Провоторова Е.Н., Фролов С.Ю., Федулов К.Н. // ИБ Алгоритмы ... тестирования ...
  2. Русская логика в информатике (Букварь математической логики)

    Документ
    ... современных матлогиков в ... вопрос, пройдя тестированиепо ... ознакомительного курса. Пятиклассники ... 0, Y – движение равномерно, Z - движение прямолинейно. Тогда поалгоритму “Импульс” получим: (x  yz)  (x’  (y’+z’)) = (x’+yz) ... третьих, потеории великого ...
  3. КОНСПЕКТ ПО РУССКОЙ ВЕРОЯТНОСТНОЙ ЛОГИКЕ

    Конспект
    ... обвиняет современных матлогиков в невежестве ... в этом вопросе ничто не ... пройдя тестированиепо нижеприведённому ... логика» и академика. Поалгоритму ТВАТ построим диаграммы ... . В-третьих, потеории великого русского физиолога ... курсы лекций по русской ...
  4. МИНИМУМ ПО РУССКОЙ ВЕРОЯТНОСТНОЙ ЛОГИКЕ

    Решение
    ... тестирование любого «корифея» по ... в интересные вопросы, поставленные там ... теории (“Толковый математический словарь” – М.: Рус.яз., 1989 – 244с.). Докажем с помощью алгоритма ... Решение. X – курс акций падает Y ... всю безмозглость матлогиков. Рассмотрим ...
  5. РУССКАЯ ЛОГИКА – ИНДИКАТОР ИНТЕЛЛЕКТА

    Документ
    ... , пройдя тестированиепо нижеприведённому вопроснику ... части 2 могут возникнуть вопросыпо 4-значной и 6- ... Решение. X – курс акций падает Y ... теорем, которые легко выводятся поалгоритму ... в целом: матлогика - фундамент математики, а матлогику (РЛ) никто ...

Другие похожие документы..