Задачи с ответами (2012), страница 6

Ни одно из приведенных выше утверждений в общем случае не является верным,потому что..._____________________________________________________________________Задача 13(3 балла)К каким задачам из теории графов сводится решение задачи model checking длятемпоральной логики PLTL?1.К задаче проверки ацикличности ориентированных графов2.К задаче проверки раскраски ориентированных графов3.К задаче выделения компонет сильной связности в ориентированных графах4.К задаче проверки достижимости заданного подграфа из заданной вершины вориентированных графах5.К задаче выделения в графе максимального полного подкрафа(клики)6.К задаче проверки изоморфизма ориентированных графовКажется, так, потому что мы ищем бесконечный радужный маршрут в графе:компоненту сильной связности с вершинами всех цветов + достижимость этойкомпоненты из нужной вершины.

//По-моему 2 ещё.Задача 13(3 балла)Из логической программы P(содержащей операторы отсечения и отрицания)с запросом G были удалены все операторы отсечения, в результате чегообразовалась новая программа P'. Какие из приведенных ниже утверждений будутвсегда верны и почему?1. Всякое успешное вычисление запроса G к программе P будет также являтьсяуспешным вычислением запроса G к программе P', потому что...2. Всякое успешное вычисление запроса G к программе P' будет также являтьсяуспешным вычислением запроса G к программе P, потому что...3. Всякий вычислимый ответ на запрос G к программе P будет также являтьсявычислимым ответом на запрос G к пгрограмме P', потому что...4.

Всякий вычислимый ответ на запрос G к программе P’ будет также являтьсявычислимым ответом на запрос G к пгрограмме P, потому что...5. Ни одно из приведенных выше утверждений в общем случае неверно.1 и 2 точно не верно. 2 - понятно, из-за возможности найти ответ в той частипрограммы, где было отсечение, а 1 - из-за взаимодействия отсечения и not. Про этосам Захаров говорил на апелляции, там может в какой-то ветви not из-за отрицаниянайтись правильный ответ и все перевернется!3 и 4 надо проверить. Но мне кажется, что ответ 5.// на апелляции сказал ответ 5.Задача 13(3 балла)Существует ли такой алгоритм, который получив на входе произвольную формулулогики предикатов, предваренная нормальная форма которой имеет вид∀x1 ∀x2 ...

∀x3 Ф(x1,..xn),где Ф(x1,... xn) - бескванторная матрица,выдает на входе 0, если эта формула общезначима, и 1, если эта форма необщезначима?1.Такого алгоритма не существует, потому что...2.Такой алгоритм существует, и вот его описание...2 - Алгоритм - Табличный вывод.___________________________________________________________вопрос: если бы я сначала L(любое) применил а потом R(любое) так щас на бумажкесоображузначит: применяем L(любое) к T2=> T3= <(), P( t ) v R( y ) | Vx P(x),R(y)>к T3 применяем R(любое) =>T4= <(), P( t ) v R( y ) | P(c),R(y)>т.е у нас разные термы, а на картинке из-за другого порядка выполнения правилT4= <(), P( с1 ) v R( y ) | P(c1),R(y)>ну мля если бы все было детерминировано то на этомбы закончился курс епта.??? не понял//типа надо думать, чтоб не запороться +1ну там думать мало где надо, в основном алгоритмы в задачах, главное - внимательно делать, авот с этим у меня например вечно проблемы - к счастью, обошлось в этот раз ._.ЗаЧеМ оПеРаТоРы оТсЕчЕнИя И оТрИцАнИя В зАпРоСе К пРоГрАмМе???!?!?!так, в слайдах всё про это идеально сказано! пизже и ровнее некуда.