Страница 76 - гдз по информатике 11 класс учебник Босова, Босова

10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.

Андрей Андреевич Марков

Андрей Андреевич Марков (22 сентября 1903 — 11 октября 1979) — советский математик, сын известного русского математика А. А. Маркова. Окончил Восьмую Петроградскую Гимназию в 1919 году; Ленинградский университет в 1924 году; аспирантуру в Астрономическом Институте (Ленинград) в 1928 году. Ученая степень доктора физико-математических наук присвоена без защиты диссертации в 1935 году. Член-корреспондент. Академии наук СССР с 1953 года.

Награждён орденом Ленина (1954). Премия имени П. Л. Чебышёва АН СССР (1969).

После войны, на базе вычислительного центра при АНССР, Марков создал настоящую лабораторию логики и структуры машин, которой лично руководил более двух десятилетий, внеся большой вклад в советскую информатику.

Андрею Андреевичу Маркову удалось доказать неразрешимость проблемы равенства в ассоциативных системах. Он вывел ключевые проблемы гомеоморфии и топологии, а также стал основателем и создателем школы конструктивной логики и математики в Советском Союзе. Именно его авторству принадлежит термин нормального алгоритма.

Основные труды по топологии (доказал неразрешимость проблемы гомеоморфизма), топологической алгебре, теории динамических систем, теории алгоритмов. Наиболее важные работы Маркова относятся к конструктивной математике, где он создал научную школу. Занимался практическими вопросами математической логики, в частности её применениями в теории ЭВМ.

11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.

Шаг алгоритма - это элементарное действие алгоритма, например, операция сложения двух чисел.

Команда алгоритма - это совокупность шагов, объединенных для выполнения определенной задачи, например, алгоритм умножения двух чисел.

12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?

Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.

13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.

Умножение двух чисел столбиком в случае, если одно из них состоит из n, а второе — из m десятичных цифр требует не более max(n,m) умножений и не более max(n,m) запоминаний. Т.е. данный алгоритм имеет сложность порядка О(n·m).

14. Какой алгоритм считается эффективным?

Алгоритм считается эффективным, если его потребление ресурсов, также известное как вычислительные затраты, находится на некотором приемлемом уровне или ниже него.

15. Постройте эффективный алгоритм возведения числа х в степень n = 152.

Алгоритм быстрого возведения в степень основан на рекурсивном разложении степени пополам. Для начала определим базовый случай: если степень равна 0, то результатом будет 1. Если степень равна 1, то результатом будет само число. В остальных случаях применяется следующий алгоритм:

1. Если степень n четная, то выполняем рекурсивное возведение числа x в степень n/2, и результат умножаем самого на себя.

2. Если степень n нечетная, то выполняем рекурсивное возведение числа x в степень (n-1)/2, и результат умножаем самого на себя, затем умножаем результат на исходное число.

Таким образом, алгоритм рекурсивно разбивает возведение в степень на более простые операции и постепенно сокращает степень до базового случая.

Пример использования: Для эффективного возведения числа x = 5 в степень n = 152 применяем алгоритм быстрого возведения в степень:

1. Поскольку 152 — четная степень, рекурсивно возведем число 5 в степень 76, затем умножим результат на само себя: 5⁷⁶ · 5⁷⁶ = (5⁷⁶)².

2. Далее, рекурсивно возведем число 5 в степень 38, затем умножим результат на само себя: (5⁷⁶)² = (5³⁸)² · (5³⁸)².

3. Продолжим этот процесс дальше, пока не достигнем базового случая.

4. В конце получим результат возведения числа 5 в степень 152.