Алгоритм и свойства алгоритма¶

Что такое алгоритмы и какими они бывают

Ты можешь разрабатывать микросервисы и знать все уровни модели OSI, но какой ты программист, если не можешь объяснить ребёнку, что такое алгоритм?

Иллюстрация: Катя Павловская для Skillbox Media

Алгоритм и свойства алгоритма¶

Пишет об истории IT, разработке и советской кибернетике. Знает Python, JavaScript и немного C++, но предпочитает писать на русском.

Алгоритм и свойства алгоритма¶

Ведущий бэкенд-разработчик мобильного приложения «Альфа-Банка».

Иногда совсем простые вопросы о профессии вводят в ступор даже опытных специалистов. Примерно так происходит, когда у разработчика с 5–10-летним стажем спрашивают: «Что такое алгоритм?»

Но для того мы здесь и собрались, чтобы дать понятные ответы на «глупые» вопросы. В этой статье расскажем, что такое алгоритмы, для чего они нужны и какими бывают.

В широком смысле алгоритм — это последовательность действий, которые нужно выполнить, чтобы получить определённый результат.

Слово «алгоритм» произошло от имени персидского математика Абу Абдуллаха аль-Хорезми. В своём труде «Китаб аль-джебр валь-мукабала» учёный впервые дал описание десятичной системы счисления. А наука алгебра получила своё название в честь его книги.

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

1. Устанавливаем капсулу.

2. Проверяем уровень воды в специальном отсеке.

3. Если воды недостаточно — доливаем.

4. Ставим чашку под кран кофемашины.

5. Запускаем кофемашину.

6. Выключаем кофемашину, когда чашка наполнилась.

7. Достаём кружку.

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

С компьютерами намного сложнее. Им неизвестно, что значит «установить капсулу», «долить воду», «запустить кофемашину» и так далее. Чтобы запрограммировать робота-баристу под определённую модель бытовой техники, алгоритм придётся расписать более детально:

1. Возьми штепсельную вилку шнура питания кофемашины.

2. Вставь штепсельную вилку в розетку.

3. Проверь, есть ли вода в отсеке для воды.

4. Если воды недостаточно:

4.1. Подними крышку отсека.

4.2. Возьми кувшин с водой.

4.3. Лей воду из кувшина в отсек, пока он не заполнится.

4.4. Закрой крышку отсека.

4.5. Поставь кувшин с водой на стол.

5. Открой крышку кофемашины.

6. Возьми из коробки капсулу с кофе.

7. Вставь капсулу в отсек для капсулы.

8. Закрой крышку кофемашины.

9. Поверни рычаг кофемашины вправо.

10. Когда чашка наполнится, поверни рычаг кофемашины влево.

11. Возьми кружку.

12. Принеси кружку хозяину.

Конечно, если мы собираем робота с нуля, то даже такой детализации будет недостаточно. Каждую процедуру ещё нужно будет реализовать на языке программирования (например, на C++ или Python), что само по себе — нетривиальная задача. Тем не менее описание стало более точным и формальным.

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

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

У алгоритмов есть два замечательных качества: они позволяют эффективно решать задачи и не изобретать решения, которые кто-то уже придумал до нас. Это справедливо как для повседневной жизни, так и для IT.

Представьте, что оформляете загранпаспорт. Если будете всё делать сами и без инструкции, около 40 минут потратите только на выяснение необходимых справок и порядка оформления. Куда проще воспользоваться «Госуслугами», потому что алгоритм там уже составлен — делаете, что вам говорят, и ждёте результат. А ещё проще — обратиться к посреднику, который подготовит все справки и оформит паспорт за неделю.

Это очень бытовой пример, но программирование примерно так и работает. Разработчики изучают алгоритмы, чтобы писать быстрый и эффективный код, — распознают типовую задачу и подбирают для неё оптимальный алгоритм.

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

А если нужно упорядочить массив из 10 000 000 элементов? Тогда компьютеру придётся выполнить 1014 шагов, что потребует гораздо больше времени. Надо оптимизировать!

Разработчик, не сведущий в computer science, начнёт ломать голову над более эффективным решением. А опытный специалист применит алгоритм быстрой сортировки, который в среднем случае даст «время» 16 × 107 шагов.

Знатоки скажут, что ещё проще было бы воспользоваться библиотечной функцией сортировки (например, sorted() в Python). Тем не менее даже встроенные алгоритмы бывают недостаточно эффективными и разработчикам приходится писать собственные функции для сортировки. Но это уже совсем другая история 🙂

Теперь представьте: вы живёте в XX веке где-нибудь в США и зарабатываете тем, что ездите по городам и продаёте мультимиксеры. Чтобы сэкономить время и деньги, вам нужно придумать кратчайший маршрут, который позволит заехать в каждый город хотя бы один раз и вернуться обратно.

Алгоритм и свойства алгоритма¶

Это знаменитая задача , для которой практически невозможно подобрать лучшее решение. Простой перебор здесь не поможет. Уже при 10 городах количество возможных маршрутов будет равно 3,6 млн, а при 26 — даже самым мощным компьютерам понадобится несколько миллиардов лет, чтобы перебрать все варианты.

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

Информатик и автор классических учебников по программированию Дональд Кнут выделял следующие свойства алгоритмов:

  • конечность,
  • определённость,
  • наличие ввода,
  • наличие вывода, или результативность,
  • универсальность,
  • эффективность.

Рассмотрим каждое подробно.

Конечность. Алгоритм должен решать задачу за конечное число шагов. Необходимость этого критерия очевидна: программа, которая решает задачу бесконечно долго, никогда не приведёт к результату.

Определённость. Исполнитель (компьютер, операционная система) должен однозначно и верно интерпретировать каждый шаг алгоритма.

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

Универсальность. Алгоритм должен решать задачи с разными входными данными. Например, хорошая функция для сортировки массивов должна одинаково хорошо справляться с массивами из 10, 100 и 1 000 000 элементов.

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

Представьте, что вы изучили какой-нибудь язык программирования, например Go, и устроились бэкенд-разработчиком в IT-компанию. В вашей команде, помимо бэкендеров, есть фронтенд-разработчики, которые пишут код на JavaScript.

Вы придумали крутой алгоритм, который ускорит работу приложения, и хотите рассказать о нём коллегам. Но как это сделать, если они программируют на другом языке?

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

У псевдокода нет общепринятых стандартов, и авторы используют собственные оригинальные нотации. Хотя часто они заимствуют названия операций из Python, Pascal и Java. Например, код ниже напоминает программу на Python:

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

ЕСЛИ массив ПУСТОЙ:

ДЛЯ i В ДИАПАЗОНЕ ОТ 0 ДО ДЛИНА(массив):

Главное — чтобы тот, кто читает ваш алгоритм, понял его и воспроизвёл на своём языке программирования.

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

Блок-схемы — это геометрические фигуры, соединённые между собой стрелками. Овалы, прямоугольники, ромбы и другие фигуры обозначают отдельные шаги алгоритма, а стрелки указывают направление потока данных. При этом в каждый блок записывается команда в виде логического или математического выражения.

В таблице ниже представлены основные элементы блок-схем:

Элемент кода в Python

Алгоритм и свойства алгоритма¶

Никак не обозначаетсяили обозначается как начало функции:

Конец функции обозначается словом return

Алгоритм и свойства алгоритма¶

Операторы ввода и вывода:

print()
word = input()

Алгоритм и свойства алгоритма¶


+
*

Алгоритм и свойства алгоритма¶

n < :
sum +=

Алгоритм и свойства алгоритма¶

k,v enumerate(arr):
print(k, v)

Алгоритм и свойства алгоритма¶

Функции для работы с файлами:

f = open(, )
f.close()

С помощью этого нехитрого набора фигур можно нарисовать схему практически любого алгоритма. Другие фигуры блок-схем вы найдёте в документации к ГОСТ 19.701-90.

А теперь разберёмся, какими бывают алгоритмы, напишем примеры на Python и нарисуем для них блок-схемы.

По конструкции алгоритмы можно разделить на несколько групп.

В линейных алгоритмах действия идут последовательно, одно за другим. Такие программы — самые простые, но на практике они встречаются редко.

Пример. Напишите программу, которая умножает число, введённое пользователем, на 100 и выводит результат на экран.

Алгоритм и свойства алгоритма¶

Изображение: Skillbox Media

Ниже приведена реализация алгоритма на языке Python:

x = int(input())
x = x *
print(x)

В ветвящихся алгоритмах ход программы зависит от значения логического выражения в блоке «Условие». По большому счёту, любое логическое выражение сводится к выбору между истиной (True, «1») или ложью (False, «0»).

Пример. Напишите программу, которая запрашивает у пользователя возраст. Если он равен или больше 18, программа выводит приветствие, увеличивает значения счётчика посетителей на 1 и прощается, а если меньше — сразу прощается и завершает работу.

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

Алгоритм и свойства алгоритма¶

То же самое на Python:

Когда пользователь вводит 18 или больше, программа выполняет часть кода, которая записана под оператором if. Если же возраст меньше 18, то на экран выводится сообщение «Доступ запрещён» и программа завершает работу.

Такие алгоритмы содержат циклы — наборы действий, которые выполняются несколько раз. Количество повторений может задаваться целым числом или условием. В некоторых случаях, например, в операционных системах и прошивках микроконтроллеров, используются бесконечные циклы.

Пример. Напишите программу, которая циклично увеличивает значения счётчика на 1 и на каждом шаге выводит его значение. Когда значение счётчика достигнет 10, программа должна завершиться.

В основе нашего решения будет лежать следующее условие: если значение счётчика меньше 10 — прибавить 1, иначе — завершить работу. Вот как это выглядит в виде блок-схемы:

Алгоритм и свойства алгоритма¶

Переведём это в код на Python. Обратите внимание, что мы не прописываем отдельную ветвь для случая «Нет»:

count =
#прибавлять 1 к count, пока count меньше 10
count < :
count +=
print(count)
print(“Переменная count равна 10!”)

Результат работы программы:

Рекурсия — это явление, при котором система вызывает саму себя, но с другими входными данными. Такие алгоритмы используют для обхода словарей в глубину, вычисления факториала, расчёта степеней и других практических задач. В целом всё это можно сделать с помощью циклов, но код рекурсивных функций более лаконичен и удобочитаем.

Пример. Пользователь вводит число n. Посчитайте его и выведите результат на экран.

#функция, которая вызывает саму себя

n == :

#когда функция возвращает значение,
#она вызывает себя, но с аргументом n – 1
n * factorial(n – )

Вот как выглядит блок-схема рекурсивного алгоритма:

Алгоритм и свойства алгоритма¶

Алгоритм и свойства алгоритма¶

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

Есть и другие классификации алгоритмов. Например, по множеству решаемых задач их можно разделить на численные, поисковые, сортировочные, строковые, сетевые и криптографические. А по точности получаемых результатов — на нормальные и стохастические (вероятностные).

Если хотите изучить алгоритмы более подробно, начните с простых и увлекательных книг по computer science:

  • «Грокаем алгоритмы», Адитья Бхаргава;
  • «Теоретический минимум по Computer Science», Владстон Фило;
  • «Гид по Computer Science», Вильям Спрингер.

Когда познакомитесь с основными алгоритмами и научитесь решать с их помощью стандартные задачи, переходите к более серьёзной литературе. Например, прочитайте Computer Science Роберта Седжвика и «Алгоритмы» Рода Стивенса.

У «Яндекса» есть бесплатные тренировки с разбором алгоритмических задач и распространённых ошибок. А попрактиковаться, закрепить теорию и подготовиться к техническому интервью можно на LeetCode — там есть сотни задач разной сложности и для разных языков программирования.

Алгоритм и свойства алгоритма¶

Научитесь: Профессия Python-разработчик

Алгоритм и свойства алгоритма¶

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

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

Типы алгоритмических моделей¶

Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе или С++), то говорят об исходной программе. Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.

Основные способы записи алгоритмов¶

  • вербальный — алгоритм описывается на человеческом языке;
  • символьный — алгоритм описывается с помощью набора символов;
  • графический — алгоритм описывается с помощью набора графических изображений.

При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура. Блоки соединяются линиями переходов, определяющими очередность выполнения действий.
Основные блоки

Базовые алгоритмические структуры¶

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

Следование – действия выполняются строго в том порядке, в котором записаны. Образуется последовательностью действий, следующих одно за другим.

Ветвление¶

Форма организации действий, при которой в зависимости от справедливости проверяемого условия алгоритм может пойти по одной из двух возможных ветвей. Происходит выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран

Цикл¶

Форма организации действий, при которой одна и та же последовательность шагов алгоритма выполняется несколько раз или ни разу в зависимости от проверяемого условия

Возможны случаи, когда внутри тела цикла необходимо повторять некоторую последовательность операторов, т. е. организовать внутренний цикл. Глубина вложения циклов (то есть количество вложенных друг в друга циклов) может быть различной.

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

Данные и величины¶

В программировании изучаются методы программного управления работой компьютера, который выступает в качестве исполнителя. Компьютер работает с величинами — различными информационными объектами: числами, символами, кодами и др., поэтому алгоритмы, предназначенные для управления компьютером, называются алгоритмами работы с величинами.

Совокупность величин, с которыми работает компьютер.

По отношению к программе различают исходные, окончательные (результаты) и промежуточные данные, которые получают в процессе вычислений.
Величина имеет три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные
Костанта — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, true и т.д.
Переменная может изменять свои значения в ходе выполнения программы и представляется символическим именем — идентификатором, например: X, S2, cod 15.

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

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

Примеры алгоритмов¶

Создать алгоритм деления обыкновенных дробей.

  • Числитель первой дроби умножить на знаменатель второй дроби.
  • Знаменатель первой дроби умножить на числитель второй дроби.
  • Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2.

Блок – схема и текст на алгоритмическом языке (псевдокоде) выглядят следующим образом:

Данный алгоритм имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода. При описании алгоритмов в блок-схемах типы, как правило,не указываются (но подразумеваются).
В алгоритмах на АЯ для всех переменных типы указываются явно. Описание типов переменных производится сразу после заголовка алгоритма. В них используются следующие обозначения типов: цел — целый тип, вещ — вещественный тип, лит — символьный (литерный) тип, лог — логический тип. В алгоритме для деления дробей для всех переменных указан целый тип.

Составить алгоритм решения квадратного уравнения ax2+ bx + c = 0

Решением в общем случае будут два корня x1, и x2 , которые вычисляются по формуле:

Блок-схема алгоритма представлена на рисунке

Циклы¶

Дано целое положительное число п. Требуется вычислить n! (n-факториал).

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

Блок-схема
В алгоритме используются три переменные целого типа: n — аргумент; i—промежуточнаяпеременная; F — результат. Для проверки правильности алгоритма построена трассировочная таблица.

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

Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение. Служебные слова нц и кц обозначают начало цикла и конец цикла соответственно.

Вспомогательные алгоритмы¶

Алгоритм, целиком используемый в составе другого алгоритма.

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

Дважды используется команда обращения к вспомогательному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами.
Вспомогательные алгоритмы оформляются в виде процедур. Процедура СТЕПЕНЬ будет выглядеть так:

а и k — формальные параметры-аргументы, z — параметр-результат.
Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия:
* по количеству (сколько формальных, столько и фактических параметров);
* по последовательности (первому формальному соответствует первый фактический параметр, второму — второй и т.д.);
* по типам (типы соответствующих формальных и фактических параметров должны совпадать)

Обращение к процедуре инициирует следующие действия:

  • Значения параметров-аргументов присваиваются соответствующим формальным параметрам.
  • Выполняется тело процедуры (команды внутри процедуры).
  • Значение результата передается соответствующему фактическому параметру, и происходит переход к выполнению следующей команды основного алгоритма.

Использование процедур позволяет строить сложные алгоритмы методом последовательной детализации

asd (a^2 + b^2 = c^2)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *