1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
Основные свойства алгоритмов:
Дискретность: алгоритм состоит из конечного числа шагов. Определенность: каждый шаг алгоритма должен быть четко определен и понятен. Ввод и вывод: алгоритм имеет входные данные и производит выходные данные. Конечность: алгоритм должен завершаться после выполнения конечного числа шагов. Эффективность: каждый шаг алгоритма должен быть выполним за ограниченное время.
2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
Кулинарный рецепт приготовления торта нельзя считать алгоритмом, так как он может содержать нечеткие инструкции (например, "добавьте немного сахара"), которые не могут быть выполнены строго и однозначно. Также рецепт может зависеть от индивидуальных предпочтений и опыта повара.
3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
Шаги алгоритма для проведения перпендикуляра к прямой в заданной точке:
Возьмите линейку и положите её на прямую так, чтобы она проходила через заданную точку. Определите перпендикулярное направление на линейке. Отметьте точку на прямой, которая находится на перпендикуляре и на том же расстоянии от заданной точки, что и начальная точка. Протяните прямую через заданную точку и отмеченную точку - это будет перпендикуляр к исходной прямой.
4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2. Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?
6. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
Допустим, у исполнителя есть команда "Увеличить число на 1". Если любое действие считается допустимым, то можно бесконечно увеличивать число на 1, что приводит к бесконечному выполнению команд и не завершается.
7. Перечислите известные вам способы записи алгоритмов.
Известные способы записи алгоритмов: естественный язык, блок-схемы, псевдокод, программирование на различных языках программирования.
8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму: 1) вычисляется сумма первой и второй цифр числа; 2) вычисляется сумма второй и третьей цифр числа; 3) вычисляется сумма третьей и четвёртой цифр числа; 4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел; 5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.
Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.
Опишите систему команд этого исполнителя.
Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?
Укажите минимальное и максимальное значения результата работы этого исполнителя.
При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.
10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.
Что собой представляет машина Тьюринга?
Машина Тьюринга — это абстрактная вычислительная модель, разработанная Аланом Тьюрингом в 1936 году. Она представляет собой устройство, способное выполнять вычисления в соответствии с определенными правилами. Машина Тьюринга состоит из бесконечной ленты, на которой записаны символы, и головки, которая может перемещаться влево и вправо, считывать и записывать символы на ленту и принимать решения на основе правил.
11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
Отличие шага алгоритма от команды алгоритма:
Шаг алгоритма: Это элементарное действие алгоритма, например, операция сложения двух чисел. Команда алгоритма: Это совокупность шагов, объединенных для выполнения определенной задачи, например, алгоритм умножения двух чисел. Пример: В алгоритме сортировки пузырьком каждое перемещение элемента во время прохода по массиву — это шаг алгоритма, а весь процесс прохода по массиву и сравнения/перемещения элементов — это команда алгоритма.
12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
Сложность алгоритма — это мера ресурсов (времени и/или памяти), которые требуются для его выполнения. Она зависит от различных факторов, включая количество входных данных, структуру алгоритма, тип операций и др. Эффективным алгоритмом считается такой, который выполняет задачу за минимальное количество ресурсов (например, за минимальное время).
13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
Сложность алгоритма перемножения двух натуральных чисел "столбиком" составляет O(n * m), где n - количество цифр в первом числе, а m - количество цифр во втором числе. Это происходит потому, что для каждой цифры первого числа нужно выполнить умножение на каждую цифру второго числа.
14. Какой алгоритм считается эффективным?
Эффективный алгоритм обычно характеризуется небольшой сложностью по времени и/или памяти. Один из примеров эффективных алгоритмов - алгоритм быстрого возведения в степень. Вместо того чтобы выполнять n-1 умножение для возведения числа x в степень n, алгоритм быстрого возведения позволяет выполнить логарифмическое количество операций умножения (порядка O(log n)), используя метод разделяй и властвуй.
15. Постройте эффективный алгоритм возведения числа х в степень n = 152.