Домашнее задание для 11 тех класса по информатике на вторник 23.01.24:
1. Прочитайте §32, ответьте на вопросы 1, 2, 3, 4, 5, 6 к §32;
2. Решите задачу:
Составьте, используя машину Тьюринга или нормальные алгорифмы Маркова алгоритм записи выражения функции F(x): "x*x", где x - произвольное число, записанное в унарной системе счисления (перефразируя: составьте алгоритм, который для произвольного натурального числа, записанного в унарной системе счисления формирует удвоенное число, половины которого в унарной записи разделены символом "*").
Пример: x = 4
Состояние ленты исполнителя на входе алгоритма: | | | |
Состояние ленты исполнителя на выходе алгоритма: | | | | * | | | |
Подсказку к решению задачи можно найти в методическом пособии, скачать которое можно по ссылке: документ в формате pdf
Работу алгоритма решения задачи можно проверить на эмуляторах машины Тьюринга или нормальных алгорифмов Маркова, скачать которые можно по ссылкам (внутри архивного файла, работает только под ОС Windows): файл архив в формате zip (эмулятор машины Тьюринга), файл архив в формате zip (эмулятор нормальных алгорифмов Маркова).
Составив алгоритм решения задачи в эмуляторе его можно сохранить в виде файла и отправить на проверку по электронной почте (или сдать на флэшке перед уроком)
Если нет возможности использовать программу эмулятор, то решение задачи нужно оформить письменно в тетради или на отдельном листе.
3. Прочитайте §34 к теме "Доказательство правильности программ" учебника. Ответьте на вопросы 3, 4, 5, 6 к §34.
4. Решите писмьменно на отдельном листе задачи на определение инварианта алгоритма и доказательство корректности/некорректности алгоритма.
- докажите в общем виде, что операторы c = (L + R) // 2 и c = L + (R - L) // 2 (где c, L, R - целые числа, // - оператор выделения целой части деления одного целого числа на другое) дают одинаковый результат при любых значениях L и R (рассмотрите в качестве примера чётные и нечётные значения обеих переменных);
- докажите или опровергните правильность программы для выбора максимального из трёх значений, записанных в переменных a, b, c:
- если a > b то M := a
- иначе если b > c то M := b
- иначе если c > a то M := c
- все; все; все;
- Если программа некорректная (в решение опишите почему), приведите контрпример. Может ли быть, что при каких-то входных данных значение переменной M будет неопределённым? Если да, то при каких?
- В игре "ним" двое игроков по очереди берут камни из двух кучек. За один ход можно взять любое ненулевое количество камней, но только из одной кучки. Тот, кому камней не осталось, проигрывает. Опишите как определить, кто выиграет при правильной игре? Определите какой инвариант нужно соблюдать, чтобы обеспечить выигрыш?
Решение можно прислать в виде фотографий по электронной почте, либо сдать перед уроком.
