2004-gre-cs-practice-book.pdf/Q62 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: « == Вопрос: Q62-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…»)
 
Строка 1: Строка 1:
 
 
== Вопрос: Q62-4c9f66 ==
 
== Вопрос: Q62-4c9f66 ==
  
<i>Тут вставьте перевод вопроса.
+
Какие из следующих задач решаются за полиномиальное время, при общепринятой гипотезе <m>P \ne NP</m>?
Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 возможности разметки],  
+
 
включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz .  
+
# Дана [https://en.wikipedia.org/wiki/Combinational_logic логическая схема] с ''n'' входами и ''m'' выходами и <m>n^2</m> вентилями, где каждый вентиль является либо ''AND'', ''OR'', или ''NOT'', и заданы ''m'' значений <m>c_1,...,c_m</m> в качестве выходных данных или определяют, что <m>c_1,...,c_m</m> не является возможным выходным сигналом схемы
Потом конечно сотрите инструкции, которые тут курсивом.</i>
+
# Учитывая ''n'' на ''n'' матриц ''A'' с рациональными числовыми элементами, либо найдите точное значение, обратное <m>A^{-1}</m> для ''A'', либо определите, что <m>A^{-1}</m> не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел ''a/b'' (<m>b \ne 0</m>), где ''a'' и ''b'' выражены в двоичной системе счисления)
 +
# Задан ориентированный граф с узлами, пронумерованными <m>1,2,...,n</m>, и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла ''n'', либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)
  
 
=== Ответы ===
 
=== Ответы ===
<i>Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так
+
* Только 1
(префикс «Правильный ответ:» — это дословно, для правильного ответа)</i>
+
* Только 2
 
+
* Только 3
* Правильный ответ: тут реально правильный ответ
+
* 1 и 2
* неправильный ответ
+
* Правильный ответ: 2 и 3
* еще какой-то неправильный ответ
+
* еще какой-то неправильный ответ
+
* еще какой-то неправильный ответ
+
 
+
<i>Если ответы длинные, многострочные, или там графы, используйте
+
[https://wiki.4intra.net/MediawikiQuizzer/ru#.D0.9E.D1.82.D0.B2.D0.B5.D1.82.D1.8B способ задания ответов разделами],
+
Но такое очень редко встречается. </i>
+
 
+
  
 
=== Объяснение ===
 
=== Объяснение ===
<i>Сначала заполните номер страницы с этим вопросом
+
{{cstest-source|2004-gre-cs-practice-book.pdf|41|62}}
{{cstest-source|2004-gre-cs-practice-book.pdf|тут-номер-страницы-с-вопросом-62|62}}
+
  
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ правильный.</i>
+
* 1 — Circuit-SAT, NPC
 +
* Обратную матрицу посчитать полно полиномиальных алгоритмов, в школе проходили как через детерминант на худой конец.
 +
* Любой алгоритм для кратчайших путей максимум куб по времени.
  
{{question-ok|}}
+
{{question-ok|[[Участник:StasFomin|StasFomin]] 06:33, 16 декабря 2024 (UTC)}}

Версия 06:33, 16 декабря 2024

Вопрос: Q62-4c9f66

Какие из следующих задач решаются за полиномиальное время, при общепринятой гипотезе ?

  1. Дана логическая схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
  2. Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
  3. Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)

Ответы

  • Только 1
  • Только 2
  • Только 3
  • 1 и 2
  • Правильный ответ: 2 и 3

Объяснение

Исходники — вопрос 62 на 41 странице книги «2004-gre-cs-practice-book.pdf»

  • 1 — Circuit-SAT, NPC
  • Обратную матрицу посчитать — полно полиномиальных алгоритмов, в школе проходили как через детерминант на худой конец.
  • Любой алгоритм для кратчайших путей максимум куб по времени.