2011-gre-cs-practice-book.pdf/Q18 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q18-08c765 == | == Вопрос: Q18-08c765 == | ||
Предположим, что профессор X разрабатывает новую модель вычислений, называемую нейтронной машиной. Что из | Предположим, что профессор X разрабатывает новую модель вычислений, называемую нейтронной машиной. Что из | ||
| − | следующего будет следствием тезиса Чёрча-Тьюринга? | + | следующего будет следствием [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D1%91%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 тезиса Чёрча-Тьюринга]? |
=== Ответы === | === Ответы === | ||
| − | + | * Ни одна нейтронная машина не может решить задачу коммивояжёра за полиномиальное время. | |
| − | + | * Ни одна нейтронная машина не может решить задачу максимального соответствия для двудольных графов за полиномиальное время. | |
| − | + | * Ни одна нейтронная машина не может определить, содержит ли десятичное разложение 7 последовательных семерок. | |
| − | + | * Ни одна нейтронная машина не может смоделировать данную машину Тьюринга за полиномиальное время. | |
| − | + | * Правильный ответ: Ни одна нейтронная машина не может определить за полиномиальное время, останавливается ли данная машина Тьюринга, если ее входная лента изначально пуста. | |
| − | + | ||
=== Объяснение === | === Объяснение === | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|23|18}} | {{cstest-source|2011-gre-cs-practice-book.pdf|23|18}} | ||
| − | + | * «…задачу коммивояжёра за полиномиальное время…» — Это утверждение не относится к тезису Чёрча-Тьюринга. Мы вообще ещё не знаем можно ли решить эту задачу за полиномиальное время или нет. | |
| − | + | * «… двудольных графов за полиномиальное время …» — Эта задача может быть решена за полиномиальное время с помощью алгоритмов, таких как алгоритм Хопкрофта-Карп. Поэтому это утверждение неверно. | |
| − | + | * «… содержит ли десятичное разложение 7 последовательных семерок …» Это задача, которую можно решить за полиномиальное время, и не требует сложных вычислений. Поэтому это утверждение неверно. | |
| − | + | * «… смоделировать данную машину Тьюринга за полиномиальное время …» Это утверждение неверно, так как машины Тьюринга могут имитировать друг друга, но это может занять больше времени, чем полиномиальное, в зависимости от конкретной реализации. | |
| − | + | * «… останавливается ли данная машина Тьюринга…» Это утверждение связано с проблемой остановки, которая является неразрешимой. Таким образом, это утверждение является следствием тезиса Чёрча-Тьюринга. | |
| + | |||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:32, 19 декабря 2024 (UTC)}} | ||
| − | + | [[Категория:Теория сложности]] | |
| − | + | ||
Текущая версия на 15:33, 19 декабря 2024
Вопрос: Q18-08c765
Предположим, что профессор X разрабатывает новую модель вычислений, называемую нейтронной машиной. Что из следующего будет следствием тезиса Чёрча-Тьюринга?
Ответы
- Ни одна нейтронная машина не может решить задачу коммивояжёра за полиномиальное время.
- Ни одна нейтронная машина не может решить задачу максимального соответствия для двудольных графов за полиномиальное время.
- Ни одна нейтронная машина не может определить, содержит ли десятичное разложение 7 последовательных семерок.
- Ни одна нейтронная машина не может смоделировать данную машину Тьюринга за полиномиальное время.
- Правильный ответ: Ни одна нейтронная машина не может определить за полиномиальное время, останавливается ли данная машина Тьюринга, если ее входная лента изначально пуста.
Объяснение
Исходники — вопрос 18 на 23 странице книги «2011-gre-cs-practice-book.pdf»
- «…задачу коммивояжёра за полиномиальное время…» — Это утверждение не относится к тезису Чёрча-Тьюринга. Мы вообще ещё не знаем можно ли решить эту задачу за полиномиальное время или нет.
- «… двудольных графов за полиномиальное время …» — Эта задача может быть решена за полиномиальное время с помощью алгоритмов, таких как алгоритм Хопкрофта-Карп. Поэтому это утверждение неверно.
- «… содержит ли десятичное разложение 7 последовательных семерок …» Это задача, которую можно решить за полиномиальное время, и не требует сложных вычислений. Поэтому это утверждение неверно.
- «… смоделировать данную машину Тьюринга за полиномиальное время …» Это утверждение неверно, так как машины Тьюринга могут имитировать друг друга, но это может занять больше времени, чем полиномиальное, в зависимости от конкретной реализации.
- «… останавливается ли данная машина Тьюринга…» Это утверждение связано с проблемой остановки, которая является неразрешимой. Таким образом, это утверждение является следствием тезиса Чёрча-Тьюринга.