Информатика 23-24 г Тема. Формализация понятия алгоритма

 

Какими бывают алгоритмы

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

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

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

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

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

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

Вероятностные. Такие алгоритмы упоминаются реже, но это довольно интересный тип: работа алгоритма зависит не только от входных данных, но и от случайных величин. К ним, например, относятся известные алгоритмы Лас-Вегас и Монте-Карло.

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

Графическое изображение алгоритмов

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

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

Сложность алгоритма

Понятие «сложность» — одно из ключевых в изучении алгоритмов. Оно означает не то, насколько трудно понять тот или иной метод, а ресурсы, затраченные на вычисление. Если сложность высокая, алгоритм будет выполняться медленнее и, возможно, тратить больше аппаратных ресурсов; такого желательно избегать.

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

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

 O(1) означает, что алгоритм выполняется за фиксированное константное время. Это самые эффективные алгоритмы.

 O(n) — это сложность линейных алгоритмов. n здесь и дальше обозначает размер входных данных: чем больше n, тем дольше выполняется алгоритм.

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

 O(log n) — более эффективный алгоритм. Скорость его выполнения рассчитывается логарифмически, то есть зависит от логарифма n.

 O(√n) — алгоритм, скорость которого зависит от квадратного корня из n. Он менее эффективен, чем логарифмический, но эффективнее линейного.

Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими степенями. Их сложность растет очень быстро, и их лучше не использовать.

Графическое описание сложности. Лучше разобраться в сложности в O-нотации поможет график. Он показывает, как изменяется время выполнения алгоритма в зависимости от размера входных данных. Чем более пологую линию дает график, тем эффективнее алгоритм.

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

Использование алгоритмов в IT

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

Разработка ПО и сайтов. Алгоритмы используются для парсинга, то есть «разбора» структур с данными, таких как JSON. Парсинг — одна из базовых задач, например в вебе. Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений, настройке поведения приложения и многом другом.

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

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

Поисковые задачи. Алгоритмы поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые системы вроде Google или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

Машинное обучение. В машинном обучении и искусственном интеллекте подход к алгоритмам немного другой. Если обычная программа действует по заданному порядку действий, то «умная машина» — нейросеть или обученная модель — формирует алгоритм для себя сама в ходе обучения. Разработчик же описывает модель и обучает ее: задает ей начальные данные и показывает примеры того, как должен выглядеть конечный результат. В ходе обучения модель сама продумывает для себя алгоритм достижения этого результата.

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

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

Информатика 23-24 г Понятие о парадигмах программирования

 

Понятие о парадигмах программирования

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

Популярные подходы

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

1.     Объектно-ориентированный подход

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

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

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

Инкапсуляция. Каждый объект независим, все данные и методы содержатся внутри него.

Наследование. ООП позволяет создавать массу новых объектов, похожих на уже готовый.

Полиморфизм. Взаимодействие между участками кода строится на базе единых правил.

Абстракция. Программа всегда может обратиться к методам и свойствам объекта извне.

Объектно-ориентированное программирование поддерживается большим числом языков, в числе которых известные С++, Java, JavaScript, Python, Swift.

2.     Декларативный подход

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

Главное достоинство декларативной методики в том, что написанный в соответствии с ней код компактен и прост для понимания. Но есть и серьезные недостатки:

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

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

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

3.     Императивный подход

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

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

1.     сложи два числа и выведи результат;

2.     отправь запрос на файловый сервер;

3.     открой программу и сверни ее в окно;

4.     выведи на экран сообщение и так далее.

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

4.     Функциональный подход

Используя функциональный стиль, разработчик описывает не четкую инструкцию в формате последовательности действий, а взаимодействие между командами и подпрограммами. В этом плане есть сходство с ООП, однако здесь такой подход реализуется на уровне всего приложения. Функциональная разработка поддерживается языками Haskell, Lisp, Erlang, Clojure и F#.

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

·        последовательность правил не имеет значения, они работают в любом месте кода;

·        все переменные работают как константы, иные данные хранятся в самих функциях;

·        функции возвращают предсказуемый результат, который не зависит от переменных;

·        последовательность исполнения подпрограмм определяет не программист, а код.

Функциональная парадигма существует более 60 лет, но до сих пор применяется точечно, имеет узкую сферу применения и проигрывает по популярности объектно-ориентированному подходу.

Объекты

Природа объектов

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

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

То, что объект «помнит», хранится в его полях.
То, что объект «умеет делать», реализуется в виде его внутренних процедур и функций, называемых методами.
Свойства объектов аналогичны свойствам, которые мы наблюдаем у обычных предметов. Значения свойств можно устанавливать и читать. Программно свойства реализуются через поля и методы.

Пример:

Объект «кнопка» имеет свойство «цвет». Значение цвета кнопка запоминает в одном из своих полей. При изменении значения свойства «цвет» вызывается метод, который перерисовывает кнопку.

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