Домашнее задание для 11 тех (группа 1, группа 2) класса по информатике на среду 25.01.23:
1. Прочитайте §32, ответьте на вопросы 1, 2, 3, 4, 5, 6 к §32;
2. Решите задачу:
Составьте, используя машину Тьюринга или нормальные алгорифмы Маркова алгоритм вычисления функции F(x): "x*x", где x - произвольное натуральное число, записанное в унарной системе счисления (перефразируя: составьте алгоритм, который для произвольного натурального числа, записанного в унарной системе счисления формирует удвоенное число, половины которого в унарной записи разделены символом "*").
Пример: x = 4
Состояние ленты исполнителя на входе алгоритма: 1111
Состояние ленты исполнителя на выходе алгоритма: 1111*1111
Подсказку к решению задачи можно найти в методическом пособии, скачать которое можно по ссылке: документ в формате pdf
Работу алгоритма решения задачи можно проверить на эмуляторах машины Тьюринга или нормальных алгорифмов Маркова, скачать которые можно по ссылкам (внутри архивного файла, работает только под ОС Windows): файл архив в формате zip (эмулятор машины Тьюринга), файл архив в формате zip (эмулятор нормальных алгорифмов Маркова).
Составив алгоритм решения задачи в эмуляторе его можно сохранить в виде файла и отправить на проверку по электронной почте (или сдать на флэшке перед уроком)
Если нет возможности использовать программу эмулятор, то решение задачи нужно оформить письменно в тетради или на отдельном листе.
3. Прочитайте §33 по теме "Сложность алгоритмов" учебника. Ответьте на вопросы 1, 2, 3, 4, 5 к §33.
В дополнение к §33 учебника обязательно! посмотрите видео, посвящённое основам понятия "асимптотическая сложность алгоритмов". Видео можно найти на youtube по ссылке:
4. Решите задачу на оценку сложности алгоритма: Составьте алгоритм, который находит в одномерном массиве размера n (n вводится с клавиатуры и n ≥ 1) количество элементов, равных масксимальному элементу.
Определите, какие элементарные операции можно выделить в этом алгоритме, оцените количество этих операций во всём алгоритме и затем определите асимптотическую сложность алгоритма.
Пример оформления ответа:
К задаче необходимо привести код алгоритма написанный на языке Python.
Основы языка Python можно освежить в памяти воспользовавшись онлайн учебником за 10 класс доступный для скачивания по ссылке: https://kpolyakov.spb.ru/loadstat.php?f=/download/ch10-8_python.pdf
Скачать интерпретатор языка Python на домашний компьютер можно с официального сайта: https://www.python.org/downloads/
Программу можно скачать в вида файла на компьютер нажав кнопку "Download code":
Написав программу и оформив ответ к задаче, решение можно прислать по электронной почте (адрес указан в задании в электронном дневнике), либо сдать файл программы и ответ к задачу очно перед уроком.
