Студопедия
Обратная связь

Сколько стоит твоя работа?
Тип работы:*
Тема:*
Телефон:
Электронная почта:*
Телефон и почта ТОЛЬКО для обратной связи и нигде не сохраняется.

Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации

Контрольные вопросы и задания

1. С чем связана необходимость точного определения понятия «алгоритм»?

2. Почему приведенное в п.7.1. определение алгоритма названо «нестрогим»?

3. Можно ли считать алгоритмом: (а) правила правописания; (b) законы физики; (с) математические формулы; (d) статьи уголовного кодекса. Ответы обоснуйте.

4. На какие свойства алгоритма окажет влияние выбор того или иного исполнителя для решения одной и той же задачи?

5. Можно ли считать исполнителем алгоритма: (а) человека, ведущего запись текста под диктовку, (b) компьютер; (с) компьютерную программу, (d) дрессированное животное. Ответы обоснуйте.

6. Доказать, что примитивно-рекурсивными являются функции: (а) х-у; (b) xy; (с) п!

7. Каким образом связаны свойства алгоритма и особенности устройства алгоритмической машины?

8. Какие действия алгоритмической машины следует считать элементарными?

9. Решите следующие задачи, используя алгоритмическую машину Поста; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:

a) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения суммы N+Q.

b) решите предыдущую задачу при условии, что исходные числа разделены произвольным числом пустых ячеек.

c) на ленте находятся два числа N и Q (N > Q), разделенные одной пустой ячейкой. Напишите программу нахождения разности N - Q.

d) на ленте N меток. Построить такое же количество меток справа от имеющихся через одну пустую.

e) на ленте находятся два числа N и Q, разделенные одной пустой ячейкой. Напишите программу нахождения произведения N - Q.

10. На каком-либо языке программирования высокого уровня разработайте программу эмуляции работы машины Поста.

11. Решите следующие задачи, используя алгоритмическую машину Тьюринга; во всех задачах в исходном состоянии обозревается крайняя левая ячейка:

a) Сложение двух чисел в унарной системе счисления (например, 1111+111).

b) Дано слово из знаков а и b произвольной длины (например, abb-bab), причем, заранее не известно, какой знак первый (а или b). Необходимо первый знак переместить в конец слова.

c) Добавление 1 к числу в произвольной заданной системе счисления.

d) Перевод целого числа из одной системы счисления в другую.

12. На каком-либо языке программирования высокого уровня разработайте программу эмуляции работы машины Тьюринга.

13. Найти значение функции S2(S1,S1) (т.е. результат подстановки функции непосредственного следования самой в себя).

14. Нормальный алгоритм имеет алфавит А = {а, b, с} и систему подстановок: асаа, aab→bc, bc→cab. Найти результат применения алгоритма к исходным словам: (1) cbcbba; (2) abccba; (3) accca.

15. На каком-либо языке программирования высокого уровня разработайте программу, обеспечивающую задание и выполнение нормальных алгоритмов Маркова.

16. Разработайте нормальные алгоритмы, обеспечивающие:

a) выполнение операции вычитания единицы из числа в троичной системе счисления;

b) выполнение операции добавления единицы к числу в двоичной системе счисления;

c) инверсию числа в двоичном алфавите;

d) преобразование док→тоска. Применить его к словам ток, дот.





 

Читайте также:

Формы представления информации

А.1. Понятие вероятности

Пример 2.8

Предисловие

Постановка задачи

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1868

 
 

54.158.21.176 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.