0: Здравствуйте, ребята. Тема сегодняшнего урока. Основные сведения об алгоритмах.

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

2: Дела. Некоторые задачи настолько сложны, что требуют длительных размышлений для нахождения решения, которое иногда так и не удаётся найти в любом случае для решения задачи надо знать, что дано.

3: И что следует получить для получения результатов, необходимо знать способ решения задачи располагать алгоритмом из курса информатики основной школы вам должны быть хорошо известны понятия алгоритма.

4: И исполнителя, но на всякий случай освежим в памяти эту информацию. Исполнитель алгоритма это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.

5: Исполнители бывают 2 типов формальные и неформальные. Далее мы будем говорить преимущественно о формальных или не размышляющих исполнителях. Формальный исполнитель не размышляет над выполнениями команд, а строго.

6: Следует пошаговым инструкциям алгоритма 1 и ту же команду формальный исполнитель всегда выполняет одинаково за действия формального исполнителя отвечает управляющий им объект, алгоритм точная система предписаний.

7: Определяющая содержание и порядок действий исполнителя над некоторыми объектами, исходными и промежуточными данными для получения искомого результата за конечное число Шагов любой алгоритм существует не сам по себе он всегда.

8: Предназначен для определённого исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Значение слова. Алгоритм, очень похожее по значению на слова. Рецепт, метод, способ, но в отличие от

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

10: Заключается в том, что каждая команда алгоритма определяет однозначное действие исполнителя и недвусмысленно указывает, какая команда должна выполняться следующей суть свойства понятности в том, что запись алгоритма должна быть настолько чёткой.

11: Полный, что у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений. Результативность это свойство означает, что при точном исполнении команды алгоритма процесс должен прекратиться за конечное число Шагов, и при этом должен быть получен ответ на

12: Вопрос задачи свойство результативности содержит в себе свойство конечности, то есть завершение работы алгоритма за конечное число Шагов, свойство массовости, говорит о том, что алгоритм пригоден для решения любой задачи из некоторого класса задач.

13: С учётом рассмотренных свойств мы можем уточнить первоначальное понятие алгоритма. Итак, алгоритм это конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных.

14: К конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости из курса информатики основной школы нам известны разные способы записи 1 и того же.

15: Алгоритма словесная запись на естественном языке, записи алгоритма в виде блок схемы запись на алгоритмическом языке или на языке программирования. Выбор способа записи алгоритма зависит от ряда причин. Не

16: Большой алгоритм можно записать в словесной форме если для вас наиболее важна наглядность, то разумно использовать блок схему. Алгоритм, готовый к реализации, должен быть записан на языке, понятном исполнителю. Рассмотрим пример Зада.

17: В которой алгоритм преобразования числа задан в словесной форме, на вход алгоритма подаётся натуральное число n. Алгоритм строит по нему новое число r. Следующим образом 1 строится.

18: Двоичная запись числа n 2 складываются все цифры двоичной записи числа n. 3 находится остаток от деления полученной суммы на 2 и дописывается в конец числа справа 4 для полученной записи повторяются шаги 2 и 3.

19: Полученная таким образом запись в ней на 2 разряда больше, чем в записи исходного числа n, является двоичной записью искомого числа re надо указать такое наименьшее число n, для которого результат работы данного алгоритма больше.

20: Числа 77 в ответе это число надо записать в десятичной системе счисления. Чтобы лучше понять условия этой задачи. Возьмём произвольное число, например, 61 и преобразуем его в соответствии с

21: Условием задачи. Я думаю, вам понятен способ перевода числа 61 в двоичную систему счисления и понятны все преобразования, которые мы провели в соответствии с имеющимся алгоритмом. Можно заметить следующее. Каждый двоичный разряд припи.

22: К двоичному числу справа увеличивает число как минимум в 2 раза 2 двоичных разряда, приписанных к двоичному числу справа увеличивают исходное число как минимум в 4 раза, если сумма единиц в двоичной записи исходного числа.

23: Чётная, то за 2 шага к нему будет приписано 00. Если сумма единиц в исходном числе нечётная, то мы за 2 шага приписываем к нему единицу и 0 используем эту информацию для решения задачи, если результат работы

24: Рассматриваемого нами алгоритма больше числа 77, то это может быть число 78. Поработаем с этим числом, переводим число 78 в двоичную систему счисления. Получаем 1.

25: 0 0 1 1 1 0 2 последние цифры. 1 0. Это значит, что в двоичной записи исходного числа должно быть нечётное количество единиц. Отбросив 1 0. Посмотрим на оставшуюся часть. Это

26: 1, 0, 0, 1, 1, 111. Все подходит. Это число 19. Переводим 19 в двоичную систему, суммируем двойки. Их 3. Остаток отделения 3 на 2 равен единице при

27: Писываем единицу справа к исходному числу, снова подсчитываем двойки и теперь уже 0 приписываем к исходному числу. Справа двоичное число, переводим в десятичную систему и получаем 78. Итак, наша гипотеза оказалась верной при

28: Н. Равным 19. В результате преобразований по заданному алгоритму получим число 78. Задача решена. Если кто-то сомневается, что 19 наименьшее число, удовлетворяющее условию задачи, то мож,

29: Взять в качестве исходного числа 18, провести преобразование по заданному алгоритму и убедиться в том, что ничего не получается. Советую вам поставить видео на паузу и самостоятельно решить

30: Аналогичную задачу. Кстати, такие задачи входят в егэ по информатике. Если вы все сделаете правильно, то получите число 25. Вспомним основные условные графические обозначения блок схем с помощью блок.

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

32: Операций, в результате которых изменяется значение форма представления или расположения данных с помощью блока ромб, обозначается выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий блоком шестиуго.

33: Угольник обозначается выполнение операций, меняющих команды или группу команд, изменяющих программу блок прямоугольник с 2 вертикальными прямыми внутри, обозначает использование ранее созданных и отдельно описанных алгоритмов или программ.

34: Следующем слайде будет представлена блок. Схема 1 очень известного алгоритма. Интересно, узнаете ли вы его?

35: Надеюсь, все узнали метод половинного деления поставьте видео на паузу и подсчитайте, какое наибольшее число Шагов может понадобиться для угадывания по этому алгоритму числа x, принадлежащего отрезку 0 100 в теории алгоритм.

36: Установлено, что для задачи, имеющей алгоритмическое решение, можно придумать множество различных способов её решения, то есть алгоритмов. Какой же алгоритм лучше подходит для

37: Решение конкретной задачи давайте разбираться вычислительным процессом называется последовательность Шагов алгоритма, пройдённых при его исполнении. Сложность алгоритма это количество элементарных Шагов в вычислительном процессе.

38: Этого алгоритма. Обратите внимание в определении сложности алгоритма. Речь идёт именно о вычислительном процессе, а не о самом алгоритме. Алгоритм состоит из команд. Команда это отдельная инструкция в описании алгоритма шаг алгоритма.

39: Это отдельное действие, которое исполнитель выполняет по команде в циклических алгоритмах за счёт повторного выполнения одних и тех же команд. Число Шагов при выполнении алгоритма может быть значительно больше числа команд в алгоритме. Эффективность алгоритма оценивается

40: Количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма. Давайте потренируемся оценивать сложность алгоритмов в старинной библиотеке в 1 из

41: 1000 томов, посвящённых кладам и тайникам. Спрятана книга сейф. Надо её найти в задаче. Мы принимаем за 1 действие открытие книги, а действиями по снятию книг с полки можно пренебречь. Таким образом, для

42: Для того чтобы найти книгу сейф, нам придётся последовательно проверять все книги подряд, значит, сложность задачи будет равна количеству книг, то есть о большое от n будет равно 1000 по условию другой задачи под названием поиск в телефонной книге.

43: Книги сейф оказался Клочок страницы с фамилией и 1 цифрой номера телефона. Надо найти страницу с нужной фамилией в телефонном справочнике, в котором 1000 страниц, благодаря тому, что фамилии в телефонном справочнике отсортированы по alpha.

44: Мы можем существенно сократить поиск, применив метод половинного деления, как это будет выглядеть, открыв книгу примерно в середине, мы уменьшаем неопределённость вдвое сложность алгоритма будет равна у большое от лога.

45: Рифма 1000 по основанию 2 таким образом, в книге объёмом 1000 страниц страница с нужной фамилией находится не более чем за 10 раз, так как 2 в степени 10 равно 1024. Рассмотрим ещё.

46: 1 задачу известно, что во многих языках программирования нет операций возведения в степень, поэтому такой алгоритм программисту приходится писать самостоятельно операция возведения в степень реализуется через операции.

47: Умножения с Ростом показателя степени растёт количество операций умножения, которые выполняются достаточно долго, следовательно, актуален вопрос о создании эффективного алгоритма возведения.

48: Степень. Рассмотрим. Метод быстрого вычисления натуральной степени n вещественного числа, описанный ещё в древней Индии. Последовательность Шагов по реализации этого метода перед вами на экране. Воспользуемся ей.

49: Для построения эффективного алгоритма возведения числа в степень 40 преобразуем 40 из десятичной системы счисления в двоичную получаем число 1 0 1:00 0, заменим каждую единицу парой букв к x.

50: А каждый 0 буквой к. Теперь построим последовательность к x k k x к к к. Вычеркнем крайнюю левую пару к x k k x к к к. Вычислим искомое значение.

51: X. Во 2 степени икс, в 4 икс в 5 икс, в 10 икс, в 20 икс в 40 мы вычислили 40 степень числа x за 6 операций умножения. Такой метод значительно эффективнее прямолинейного алгоритма.

52: Возведения в степень, требующего в рассматриваемом случае 39 операций умножения.