Контрольные вопросы

1. В каких случаях вычислительный процесс не является алгоритмом?

2. В чём суть проблемы алгоритмической неразрешимости? Почему проблема алгоритмической неразрешимости более трудная, чем проблема алгоритмической разрешимости?

3 Из чего следует необходимость уточнения понятия алгоритма? Каковы подходы к его уточнению?

4. Какие виды обработки данных знаете Вы?

5. Каковы формы представления алгоритмов? Что у них общего и чем они отличаются?

6. Какие основные блоки, используемые в СА, Вы знаете?

7. Какова последовательность действий при решении задачи на ЭВМ?

8. Что такое структуры управления вычислительным процессом? Как они связаны с базовыми фрагментами СА?

9. Какие виды вычислительных процессов и алгоритмов Вы знаете?

10. Чем отличается тестирование программы от её отладки?

11. Как Вы понимаете неоднозначность СА? Что означает термин интерпретация СА?

1 Диофантово уравнение имеет вид xⁿ + yⁿ = zⁿ, где n – целое. Требуется найти целочисленное решение для произвольного n. Найти такое решение в общем виде не удаётся.

2 Существует теорема о том, что для раскраски любого планарного графа необходимо не более чем 4 краски. Однако доказать эту теорему в общем виде не удаётся.

1 Строго говоря, схема рис. В.2,в не является структурой управления, так как использует оператор goto.

14