Какие из следующих утверждений о работе алгоритма Дейкстры верны?

А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.

Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).

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

Правильный ответ:

• # Пусть корень ориентированного дерева T имеет 4-х сыновей, а каждая из остальных внутренних вершин имеет два или три сына, при этом число вершин с 2-я сыновьями вдвое превосходит число вершин с 3-я. Сколько всего вершин в T, если известно, что число его листьев равно 36?
• # Детектив Ш. Холмс подозревает в совершении преступления трех лиц: Джонса, Брауна и Карта. Он установил, что если Джонс не преступник, то Браун является преступником ;кто-то один из пары Джонс, Карт является преступником, но не оба вместе;Браун и Карт вместе не совершали преступление. Какие из следующих выводов он может сделать из установленных фактов: Джонс является преступником.Браун является преступником.Карт является преступником.Преступник действовал в одиночку.
• # Какие из следующих элементарных конъюнкций являются максимальными для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f=(1011 1010). I ) ¬ X∧Y ∧ Z , II) ¬Z, III) ¬ X∧Y , IV) ¬Y, V) X ∧ ¬Z
• # Какие из следующих формул логики предикатов являются тождественно истинными? ( ∀x P(x) →​ ∀x Q(x) ) →​ ∀x ( P(x) →​ Q(x) )∀x ( P(x) →​ Q(x) ) →​ ( ∀x P(x) →​ ∀x Q(x) )(∃x P(x) →​ ∃x Q(x) ) →​ ∃x ( P(x) →​ Q(x) )
• # Пусть база данных включает отношение Счет(Номер,Товар,Дата,Сумма). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибут Номер является ключом отношения. Ф1 = ∀n∃t∃d∃s (Счет (n,t,d,s) →​ ∃t1∃d1∃s1 (Счет (n,t1,d1,s1) →​ (t=t1 ∧ d=d1 ∧ s=s1)))Ф2 = ∀n∀t∀d∀s∀n1∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ Счет (n1,t1,d1,s1) ∧ (t≠t1 ∨ d≠d1 ∨ s≠s1)) →​ (n ≠ n1))Ф3 = ∀n∀t∀d∀s∀t1∀d1∀s1 ((Счет (n,t,d,s) ∧ (Счет (n,t1,d1,s1)) →​ (t=t1 ∧ d=d1 ∧ s=s1)))