Понятие алгоритма. Программирование. Алгоритмы программирования и структуры данных Понятие базовых алгоритмов
Любое управление процессом требует определенных правил и четких действий. Компьютер – это устройство, предназначенное для автоматизации создания, хранения, обработки и передачи данных, а значит здесь должны выполняться четкие предписания для выполнения той или иной задачи.
Для создания программ, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.
Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.
Иными словами, алгоритм – это точная инструкция, а инструкции встречаются практически во всех областях человеческой деятельности. Возможны алгоритмы проведения физического эксперимента, сборки шкафа или телевизора, обработки детали. Однако не всякая инструкция есть алгоритм.
Инструкция становится алгоритмом только тогда, когда она удовлетворяет определенным требованиям. Одно из требований алгоритма однозначность, т.е. если при применении к одним и тем же данным он даст один и тот же результат.
Применительно к ЭВМ алгоритм позволяет формализовать вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин вычислительный процесс распространяется и на обработку других видов информации, например, символьной, графической или звуковой.
Если вычислительный процесс заканчивается получением результатов, то говорят, что данный алгоритм применим к рассматриваемой совокупности исходных данных. В противном случае говорят, что алгоритм неприменим к совокупности исходных данных. Любой применимый алгоритм обладает следующими основными свойствами:
· дискретностью;
· определенностью;
· результативностью;
· массовостью.
Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов. Преобразование исходных данных в результат осуществляется дискретно во времени.
Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств (однозначность толкования инструкций).
Результативность означает возможность получения результата после выполнения конечного количества операций.
Массовость заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных (разработка в общем виде).
Для задания алгоритма необходимо описать следующие его элементы:
· набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
· правило начала;
· правило непосредственной переработки информации (описание последовательности действий);
· правило окончания;
· правило извлечения результатов.
Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.
Понятия алгоритма и программы разграничены не очень чётко. Обычно программой называют окончательный вариант алгоритма решения задачи, ориентированный на конкретного пользователя.
Таким образом, можно дать следующее определение программы для ЭВМ:
К основным способам описания алгоритмов можно отнести следующие:
· словесно-формульный (на естественном языке);
· структурный или блок-схемный;
· с использованием специальных алгоритмических языков;
· с помощью граф-схем (граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, линии – рёбрами).
Перед составлением программ чаще всего составляют алгоритм решения поставленной задачи одним из вышеописанных способов.
При словесно -формульном способе алгоритм записывается в виде текста с формулами по пунктам, составляющих последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
у = 4а – (х + 3).
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
1. Ввести значения а и х.
2. Сложить х и 3.
3. Умножить а на 4.
4. Вычесть из 4а сумму (х+3).
5. Вывести у как результат вычисления выражения.
При блок -схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий.
Такой вид записи алгоритма обладает наибольшими достоинствами. Он наиболее нагляден: каждая операция вычислительного процесса изображается отдельной геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Оформление программ должно соответствовать определенным требованиям (рис. 2.). В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).
Одним из свойств алгоритма является дискретность, т.е. представление процесса вычислений на отдельные шаги и выделения отдельных участков программы на определенные структуры.
Любой вычислительный процесс может быть представлен как комбинация элементарных алгоритмических структур:
· Следование. Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
· Ветвление. Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
· Цикл. Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
· Функция (подпрограмма). Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.
При этом выделят три основных вида алгоритмов:
Современные системы программирования обычно предоставляют пользователям мощные и удобные средства разработки программ. В них входят:
· компилятор или интерпретатор;
· интегрированная среда разработки;
· средства создания и редактирования текстов программ;
· обширные библиотеки стандартных программ и функций;
· отладочные программы, т.е. программы, помогающие находить и устранять ошибки в программе;
· "дружественная" к пользователю диалоговая среда;
· многооконный режим работы;
· мощные графические библиотеки; утилиты для работы с библиотеками;
· встроенный ассемблер;
· встроенная справочная служба;
· другие специфические особенности.
Любой алгоритм можно представить комбинацией трех базовых структур:
Линейный (следование);
Разветвляющийся (разветвление);
Циклический (повторение).
Следование – все этапы решения задачи выполняются строго последовательно один раз за время выполнения данной программы.
Разветвление – структура обеспечивает в зависимости от результата проверки условия (истина или ложь) выбора одного из альтернативных путей работы алгоритма, каждый путь ведет к общему выходу (рис. 5).
Рисунок 5. Структуры алгоритмов: «если-то» (обход) и «если-то-иначе»
Алгоритм с базовой структурой «разветвление» - разветвляющийся. Цикл – повторное выполнение или циклическая работа операторов. Различают две разновидности структуры (рис. 6):
Рисунок 6. Алгоритмы со структурой «цикл»: 1 структура - с предусловием (цикл - пока) и
2 структура - с постусловием (цикл - до)
Тело цикла – группа операторов, повторяющихся в цикле.
Оператор – формальная запись предписания для выполнения некоторой последовательности действий.
В 1 структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, во 2 структуре – хотя бы один раз.
Циклы могут содержать внутри себя другие циклы – вложенные циклы.
Алгоритмы с базовой структурой «цикл» - циклические.
Контрольные вопросы:
1. Что такое алгоритм?
2. Какими свойствами обладает алгоритм?
3. Какие виды алгоритмов существуют?
4. Назовите примеры словесно-формульного описания алгоритма.
5. Назовите примеры графического описания алгоритма.
6. Перечислите формы (способы) представления алгоритмов.
7. Что понимают под телом цикла?
8. Назовите базовые структуры программирования.
Тема: КЛАССИФИКАЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ.
ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ.
Языки программирования - это формальные языки общения человека с ЭВМ, предназначенные для описания совокупности инструкций, выполнение которых обеспечивает правильное решение требуемой задачи. Их основная роль заключается в планировании действий по обработке информации. Любой язык программирования основан на системе понятий, и уже с ее помощью человек может выражать свои соображения.
Связь между языком, на котором мы думаем/программируем, и задачами и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть по крайней мере двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т. п. Хорошее проектирование и отсутствие ошибок не может гарантироваться за счет чисто языковых средств.
Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идеи - простые операции производятся со скоростью молнии на двоичных числах.
Машиннозависимые языки программирования - это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т. д.). Эти языки называются языками программирования низкого уровня. Они ориентированы на конкретный тип процес-сора и учитывают его особенности. Операторы такого языка близки к машинному коду и ориентированы на конкретные команды процессора, то есть данный язык является машинно-зависимым. Языком низкого уровня является язык Ассемблер. С его помощью создаются очень эффективные и компактные программы, так как разработчик получает доступ ко всем возможностям процесора. Подобные языки применяются для написания небольших системных приложений, драйверов устройств, библиотек. В тех случаях, когда объем ОЗУ и ПЗУ мал (в районе нескольких килобайт), альтернативы ассемблеру нет. Именно эти языки программирования позволяют получать самый короткий и самый быстродействующий код программы.
Машиннонезависимые языки программирования - это средство описания алгоритмов решения задач и информации, подлежащей обработке. Они удобны в использовании для широкого круга пользователей и не требуют от них знания особенностей организации функционирования ЭВМ и вычислительной системы.
Подобные языки получили название высокоуровневых языков программирования. Программы, составляемые на таких языках, представляют собой последовательности операторов, структурированные согласно правилам рассматривания языка (задачи, сегменты, блоки и т. д.). Операторы языка описывают действия, которые должна выполнять система после трансляции программы на машинный язык.
Командные последовательности (процедуры, подпрограммы), часто используемые в машинных программах, представлены в высокоуровневых языках отдельными операторами. Программист получил возможность не расписывать в деталях вычислительный процесс на уровне машинных команд, а сосредоточиться на основных особенностях алгоритма.
Языки программирования высокого уровня значительно ближе и понятнее человеку. В них не учитываются особенности конкретных компьютерных архитектур, то есть данные языки являются машиннонезависимыми. Это позволяет использовать однажды записанную на таком языке программу на различных ЭВМ.
Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации (в начале 1950-х гт.) машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования были созданы языки высокого уровня (т. е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина) и в конечном итоге заставляют компьютер выполнять соответствующие команды, которые даются на машинном языке.
К языкам программирования высокого уровня можно отнести следующие: Фортран, Пролог, СоВо1, А1gо1, Раsсаl, Васik, С, С ++ , ]аvа, НТМL, Реrl и другие.
С помощью языка программирования создается не готовая программа, а только ее текст, описывающий ранее разработанный алгоритм. Чтобы получить работающую программу, надо либо автоматически перевести этот текст в машинный код и затем использовать отдельно от исходного текста, либо сразу выполнять команды языка, указанные в тексте программы. Для этого используются программы-трансляторы.
Существует два основных вида трансляторов: интерпретаторы, которые сканируют и проверяют исходный код в один шаг, и компиляторы, сканирующие исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.
Интерпретатор берет очередной оператор языка из текста программы, анализирует его структуру и затем сразу исполняет. Только после того как текущий оператор успешно выполнен, интерпретатор перейдет к следующему. При этом если один и тот же оператор будет выполняться в программе многократно, интерпретатор будет выполнять его так, как будто встретил впервые.
Компиляторы полностью обрабатывают весь текст программы (он называется исходный код). Процесс компиляции состоит из двух частей: анализа и синтеза. Анализирующая часть компилятора разбивает исходную программу на составляющие ее элементы (конструкции языка) просматривает их в поиске синтаксических ошибок (иногда несколько раз), производит определенный смысловой анализ и создает промежуточное представление исходной программы. Синтезирующая часть из промежуточного представления создает новую программу, которую компьютер в состоянии понять. Такая программа называется объектной программой , или объектным кодом .
Откомпилированные программы работают быстрее, но интерпретируемые проще исправлять и изменять.
Каждый конкретный язык ориентирован либо на компиляцию, либо на интерпретацию – в зависимости от того, для каких целей он создавался. Например, Паскаль обычно используется для решения довольно сложных задач, в которых важна скорость работы программ. Поэтому данный язык обычно реализуется с помощью компилятора . С другой стороны, Бейсик создавался как язык для начинающих программистов, для которых построчное выполнение программы имеет неоспоримые преимущества. Иногда для одного языка имеется и компилятор , и интерпретатор . В этом случае для разработки и тестирования программы можно воспользоваться интерпретатором, а затем откомпилировать отлаженную программу, чтобы повысить скорость ее выполнения.
При использовании компиляторов весь исходный текст программы преобразуется в машинные коды, и именно эти коды записываются в память микропроцессора. При использовании интерпретатора в память микропроцессора записывается исходный текст программы, а трансляция производится при считывании очередного оператора. Естественно, что быстродействие интерпретаторов намного ниже по сравнению с компиляторами, т. к. при использовании оператора в цикле он транслируется многократно. Однако при программировании на языке высокого уровня объем кода, который нужно хранить во внутренней памяти, может быть значительно меньше по сравнению с исполняемым кодом. Еще одним преимуществом применения интерпретаторов является легкая переносимость программ с одного процессора на другой.
Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает «непосредственный режим». Непосредственный режим позволяет вам задавать компьютеру задачу и возвращает вам ответ, как только вы нажмете клавишу ЕNТЕR. Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение. Однако интерпретаторные языки имеют недостатки. Необходимо, например, иметь копию интерпретатора в памяти все время, тогда как многие возможности интерпретатора, а следовательно, и его возможности могут не быть необходимыми для исполнения конкретной программы. При исполнении программных операторов интерпретатор должен сначала сканировать каждый оператор с целью прочтения его содержимого (что этот человек просит меня сделать?), а затем выполнить запрошенную операцию. Операторы в циклах сканируются излишне много.
Компилятор - это транслятор текста на машинный язык, который считывает исходный текст. Он оценивает его в соответствии с синтаксической конструкцией языка и переводит на машинный язык. Другими словами, компилятор не исполняет программы, он их строит. Интерпретаторы невозможно отделить от программ, которые ими прогоняются, компиляторы делают свое дело и уходят со сцены. При работе с компилирующим языком, таким, как Турбо-Бейсик, вы придете к необходимости мыслить о ваших программах в признаках двух главных фаз их жизни: периода компилирования и периода прогона. Большинство программ будут прогоняться в четыре - десять раз быстрее их интерпретаторных эквивалентов. Если вы поработаете над улучшением, то сможете достичь 100-кратного повышения быстродействия. Оборотная сторона монеты состоит в том, что программы, расходующие большую часть времени более точно отражающих конкретную структуру алгоритма. С этой целью в программирование введено понятие подпрограммы - набора операторов, выполняющих нужное действие и не зависящих от других частей исходного кода. Программа разбивается на множество мелких подпрограмм (занимающих до 50 операторов - критический порог для быстрого понимания цели подпрограммы), каждая из которых выполняет одно из действий, предусмотренных исходным заданием. Комбинируя эти подпрограммы, удается формировать итоговый алгоритм уже не из простых операторов, а из законченных блоков кода, имеющих определенную смысловую нагрузку, причем обращаться к таким блокам можно по названиям. Получается, что подпрограммы - это новые операторы или операции языка, определяемые программистом.
Возможность применения подпрограмм относит язык программирования к классу процедурных языков.
Наличие подпрограмм позволяет вести проектирование и разработку приложения сверху вниз - такой подход называется нисходящим проектированием. Сначала выделяется несколько подпрограмм, решающих самые глобальные задачи (например, инициализация данных, главная часть и завершение), потом каждый из этих модулей детализируется на более низком уровне, разбиваясь, в свою очередь, на небольшое число других подпрограмм, и так происходит до тех пор, пока вся задача не окажется реализованной.
Такой подход удобен тем, что позволяет человеку постоянно мыслить на предметном уровне, не опускаясь до конкретных операторов и переменных. Кроме того, появляется возможность не реализовывать сразу некоторые подпрограммы, а временно откладывать, пока не будут закончены другие части. Например, если имеется необходимость вычисления сложной математической функции, то выделяется отдельная подпрограмма такого вычисления, но реализуется она временно одним оператором, который просто присваивает заранее выбранное значение. Когда все приложение будет написано и отлажено, тогда можно приступить к реализации этой функции.
Немаловажно, что небольшие подпрограммы значительно проще отлаживать, что существенно повышает общую надежность всей программы.
Очень важная характеристика подпрограмм - это возможность их повторном использовании. С интегрированными системами программирования поставляются большие библиотеки на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости.
Процесс создания программы называется программированием.
Выделяют несколько разновидностей программирования.
Алгоритмическое или модулъное программирование. Основная идея алгоритмического программирования - разбиение программы на последовательность модулей, каждый из которых выполняет одно или несколько действий. Единственное требование к модулю - чтобы его выполнение всегда начиналось с первой команды и всегда заканчивалось на самой последней (то есть чтобы нельзя было попасть на команды модуля извне и передать управление из модуля на другие команды в обход заключительной).
Алгоритм на выбранном языке программирования записывается с помощью команд описания данных, вычисления значений и управления последовательностью выполнения программы.
Текст программы представляет собой линейную последовательность операторов присваивания, цикла и условных операторов. Таким способом можно решать не очень сложные задачи и составлять программы, содержащие несколько сот строк кода. После этого понятность исходного текста резко падает из-за того, что общая структура алгоритма теряется за конкретными операторами языка, выполняющими слишком детальные, элементарные действия. Возникают многочисленные вложенные условные операторы и операторы циклов, логика становится совсем запутанной, при попытке исправить один ошибочный оператор вносится несколько новых ошибок, связанных с особенностями работы этого оператора, результаты выполнения которого нередко учитываются в самых разных местах программы.
Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.
Сама постановка такого вопроса в корне не верна. Количество специальностей в индустрии растёт постоянно, и человек, который пишет сайты на.net будет заниматься совсем другими вещами, нежели человек, пишущий драйвера для сенсоров на ARM архитектуре под экзотической ОС. Давайте прежде всего определим, что же такое алгоритм. Неформально Кормен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Формально алгоритм определяется в разных моделях вычислений: операции, которые можно выполнить на машине Тьюринга или с помощью лямбда-исчислений. Таким образом фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». Правильно такой вопрос должен звучать что-то вроде: «нужно ли программисту в отрасли Х знать продвинутые алгоритмы и детали теории вычислений».
Если посмотреть на все эти статьи, то можно заметить, что люди, которые их пишут, фактически обижены на университеты за то, что их заставили учить много сложного материала - в виде алгоритмического анализа, сложных алгоритмов и структур данных - который им вроде бы не пригодился. По сути, авторы статей обижены на университеты из-за того, что там не смогли предсказать будущую область работы авторов и дать им только минимально нужный набор навыков. Ведь действительно, чтобы писать простенькие сайты и скрипты, не нужно особого знания алгоритмов и структур данных. Или всё-таки нужно?
Давайте подумаем, что же нужно учить программисту в университете, для того чтобы приобрести необходимые навыки для успешной карьеры. Библиотеки? Фреймворки? Они устаревают, интерфейсы к ним меняются, все они написаны чаще всего под один язык, который студенты могут и не использовать никогда в индустрии. Всех учить писать сайты? Или всех учить писать ОС? Образование должно охватывать как можно большую аудиторию и давать максимально возможный набор навыков. Программист в первую очередь должен уметь анализировать и решать проблемы – это основной навык, которым должны обзавестись выпускники факультетов информатики. Написание кода – это просто необходимый инструмент, который используется для решения задач. Кто может знать какие навыки вам понадобятся в будущем? Таким образом учить теорию – это наиболее оптимально с точки зрения образования. Полученные навыки можно применить в любой области, а выучить библиотеку или фреймворк имея хорошую базу знаний не составит большого труда. Парадоксально то, что люди задающие вопросы про нужность алгоритмов, как правило имеют какие-то знания в этой области. Я не помню ни одного человека, который не имел знаний в области теории вычислений, и с гордостью кричал об этом, утверждая, что ему они не нужны.
Итак, вы абстрактный программист в вакууме, работаете десять с лишним лет клепая сайты и решая простые однотипные задачи клиентов/компании. Вам хорошо и уютно в вашей нише, и только мучительно больно за бесцельно потраченное время в классе по теории вычислений и алгоритмическому анализу, который вам ничего не дал. По утрам закуривая сигарету за чашкой кофе, в глубине философских размышлений о бренности бытия вы задумываетесь: зачем же программистам, не решающим сложных задач, знать алгоритмы и основы анализа. Короткий ответ: чтобы быть квалифицированным специалистом и эффективно использовать доступные инструменты, включая язык, на котором вы пишите. Теория алгоритмов и анализа учит не только экзотические алгоритмы и структуры данных в виде АВЛ и красно-чёрных деревьев. Она также даёт представления о том, как эффективно организовать данные, как писать код с максимальной производительностью, где в системе возможно бутылочное горлышко и как с ним бороться. Вас ознакамливают с готовыми решениями, чтобы вы не писали велосипедов, и не бежали в гугл каждый раз, когда нужно сделать что-то нетривиальное.
Знания теории анализа и алгоритмов применяются всеми программистами на самом деле каждый день, просто мы привыкли к этим вещам настолько, что даже не задумываемся над этим. Какую бы задачу вы не решали – будь то простой сайт с выборкой данных из БД, или баш скрипт на сервере, вы будете использовать какие-то структуры данных. Как минимум примитивный массив, а скорее всего и что-то посложнее. Языки дают нам множество различных структур, многие из которых взаимозаменяемы. Часто мы имеем несколько вариаций одного абстрактного типа с разными реализациями. Например, в С++ есть структуры данных vector и list. Чем они отличаются, и какие будут преимущества и недостатки использования одного или другого? Как в С++ реализована map, и чем она отличается от multimap? Как реализован list в Python – через массив или связным списком и как лучше всего с ним работать? Почему в C# нежелательно использовать ArrayList, а вместо него использовать List? Как реализован SortedDictionary и как он повлияет на исполнение программы если будет использован вместо Dictionary? Как работает continuation, когда её нужно использовать, и будут ли какие-то побочные эффекты при её использовании? Когда вы в последний раз использовали каррированные функции, которые есть почти в каждом языке? Если вы думаете, что map в С++ реализована как хэш-таблица, вы ошибаетесь. Она реализована на красно-чёрных деревьях, а хэш-таблицей реализована unordered_map. Отдельно стоит упомянуть динамическое программирование. Понимание что это такое, как можно оптимально переписать рекурсивные функции и что такое мемоизация, часто поможет избежать выстрела себе в ногу. Таким образом просто чтобы полноценно и эффективно использовать язык, на котором вы пишите, уже нужно иметь хотя бы поверхностные знания о структурах данных, что они из себя представляют, и как могут повлиять на исполнение вашей программы.
А как же библиотеки? Ведь они решают столько задач! Чтобы рационально использовать библиотеки, их тоже нужно понимать. Во-первых, функции в библиотеки могут иметь побочные эффекты или поведение, которые вы не будете знать без понимания алгоритмов. Получив баг в таком случае можно долго и упорно пытаться его поймать и решить, когда можно было избежать. Во-вторых, различные инструменты и библиотеки часто нужно «настраивать» - говорить им какие алгоритмы, структуры данных и технологии использовать внутри. Без элементарных знаний вам придётся либо идти читать маны, либо выбирать наугад. В-третьих – есть множество задач, которые нельзя решить простым вызовом API библиотеки или фреймворка. Что вы будете делать в таком случае? Тратить часы на поиски возможных решений и просить помощи у друга? В-четвёртых – множество задач решается очень просто несколькими строчками кода или встроенными средствами языка. Если для решения каждого чиха вы будете тянуть библиотеку, то ваши программы будут гигантскими монстрами, занимая по сотни мегабайт и больше на диске, отжирая всю память на сервере, и при том имея довольно скудный функционал. Кроме того, наличие кучи подключенных библиотек влечёт за собой проблемы совместимости, и программа может падать случайным образом из-за странного поведения нескольких библиотек в одном проекте. Бездумное использование библиотек может привести к довольно плачевным последствиям, и разработчики, которые умеют только использовать библиотеки, но не способны решить даже простую проблему самостоятельно, никогда не будут ценится, потому что их решения будут неконкурентоспособны.
Со мной работал один программист со стажем больше десяти лет. Однажды нам понадобилась функция, которую использованная нами библиотека на тот момент не поддерживала: примитивный text-wrap в одном из визуальных компонентов. Этот «программист» посмотрел, что стандартными средствами это сделать нельзя, и сразу заявил, что реализация такой функции невозможна. Задачу решил интерн-третьекурсник с аналитическим мозгом, который за два часа написал простой алгоритм и внедрил его в нужный компонент. Другой проект в виде сайта на.net мне достался по наследству. Главная страничка представляла собой несколько маленьких графиков, и загружалась почти 10 секунд. Оказалось, что человек, который изначально делал этот проект, нагородил кучу ужасных конструкций из тройных вложенных циклов, которые долго и печально забирали данные из БД, и потом привязывали их к графикам. После небольшого рефакторинга страница стала грузится почти мгновенно.
Может ли программист обойтись без знаний алгоритмов и теории анализа? Может, и таких «программистов» очень много. Только назвать их программистами можно разве что с большой натяжкой. Ко мне на собеседование приходит очень много программистов, со стажем десять-пятнадцать лет, и толком не понимающих что же они делают и почему. У них своя ниша, они ходят от компании к компании, не задерживаясь в них больше года. Как правило, у них есть небольшой набор задач, которые они могут решать, и если сделать шаг в сторону, то человек теряется и ему нужно обучить себя новым навыкам. Таких людей приглашают на проект, и от них избавляются как можно быстрее, потому что они теряют кучу времени, изобретая велосипеды и читая маны чтобы узнать то, что уже должны были знать из университета. У них как правило нет особо никакой карьеры и нестабильный заработок.
В итоге, для чего нужно знать алгоритмы и теорию анализа, если можно выполнять работу и без этих знаний? Чтобы быть квалифицированным специалистом в своей профессии, иметь карьерный рост и уважение коллег. Чтобы эффективно решать поставленные задачи и не изобретать велосипедов. Чтобы не писать монстров с огромным количеством сторонних библиотек, которые занимают сотни мегабайт на диске от отжирают кучу памяти на сервере и регулярно падают по случайной причине в зависимости от фазы луны. Чтобы эффективно и с максимальными возможностями использовать язык, на которым вы пишете. Чтобы принимать информированные и осмысленные решения по выбору библиотеки и технологии для решения проблемы. Если же ваша работа заключается в написание SQL запроса и вбивание команды в консоль, то хочу вас огорчить: вы не программист, вы – пользователь, вам действительно не нужны алгоритмы и иже с ним, и вы зря потратили время в университете потому что для такой работы достаточно закончить курсы или прочитать пару вводных книжек самостоятельно.
Алгоритм Кнута-Морриса-Пратта
Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=xx... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l... l[n], где l[i]=длина слова l(x...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x...x[i], одновременно являющегося его концом.
Какое отношение все это имеет к поиску подслова?
Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A.
Описать алгоритм заполнения таблицы l...l[n].
Решение. Предположим, что первые i значений l...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x) и должны вычислить l.
Другими словами, нас интересуют начала Z слова x...x . Слово Z" является началом и концом слова x...x[i]. Однако не любое слово, являющееся началом и концом слова x...x[i], годится - надо, чтобы за ним следовала буква x.
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x...x[i], являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква x. Из подходящих выберем самое длинное. Приписав в его конец х, получим искомое слово Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела.
Вот что получается:
{таблица l..l[i] заполнена правильно}
while i <> n do begin
{len - длина начала слова x..x[i], которое является
его концом; все более длинные начала оказались
неподходящими}
while (x<>х) and (len>0) do begin
if x=x do begin
{х..x - самое длинное подходящее начало}
{подходящих нет}
Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l (число итераций на i-м шаге)<= l[i]-l+1 Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и используемая память тоже. Придумать, как обойтись памятью не более Cn (что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное). Решение. Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l,...,l [n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение l[i] для текущего i - кроме него и кроме таблицы l...l[n], нам для вычислений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем. Написать соответствующий алгоритм (проверяющий, является ли слово X=x...x[n] подсловом слова Y=y...y[m] Решение. Сначала вычисляем таблицу l...l[n]как раньше. Затем пишем такую программу: {len - длина максимального качала слова X, одновременно являющегося концом слова y..j[j]} while (len<>n) and (j<>m) do begin while (x<>у) and (len>0) do begin {начало не подходит, применяем к нему функцию l} {нашли подходящее или убедились в отсутствии} if x=y do begin {x..x - самое длинное подходящее начало} {подходящих нет} {если len=n, слово X встретилось; иначе мы дошли до конца слова Y, так и не встретив X} Алгоритм Бойера - Мура
Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.) Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s]=0 (мы увидим дальше, почему). Как заполнить массив pos? положить все pos[s] равными 0 for i:=1 to n do begin В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается. {все предыдущие положения образца уже проверены} while last<= m do begin {слово не кончилось} if x[m]<>y then begin {последние буквы разные} last:=last+(n-pos]); {n - pos] - это минимальный сдвиг образца, при котором напротив y встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца} если нынешнее положение подходит, т.е. если x[i]..х[n]=y..y, то сообщить о совпадении; Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку заменить на last:=last+(n-u), где u - координата второго справа вхождения буквы x[n] в образец. Как проще всего учесть это в программе Решение. При построении таблицы pos написать написать last:=last+n-pos]; Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта. Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить. Решение. Пусть образец имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. Настоящий (не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. Привести пример удобной для вычисления функции. Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться.) Привести пример семейства удобных функций. Решение. Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (хn-1 следует вычислить заранее), умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку. Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура. курсовая работа , добавлен 13.06.2007 Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением.txt). курсовая работа , добавлен 29.05.2013 Поиск в массивах и списках, ключ и произвольные данные. Линейный (последовательный) поиск. Бинарный поиск в упорядоченном массиве. Алгоритм Рабина-Карпа, простая и улучшенная хэш-функция. Алгоритм Бойера-Мура со сдвигом по стоп-символам и по суффиксам. презентация , добавлен 19.10.2014 Исследование понятия алгоритма, особенностей линейных и разветвляющихся алгоритмов. Свойства алгоритма: понятность, точность, дискретность, массовость и результативность. Составление программы для вычисления значения функции и построение её графика. контрольная работа , добавлен 25.03.2013 Изучение определения, описания и вызова функций, указателей и ссылок на них. Написание функции умножения произвольного столбца двумерного массива на const. Умножение 2 столбцов массива на константы. Составление блок-схемы алгоритма и текста программы. лабораторная работа , добавлен 09.01.2012 Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером. презентация , добавлен 04.04.2014 Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание. курсовая работа , добавлен 11.12.2009 Характеристика особливостей реалізації пошуку по масиву методами лінійним, бінарним, по "дереву Фібоначе" та екстраполярним на мові програмування Turbo Pascal. Використання алгоритма Рабіна-Карпа та Кнута-Морріса-Пратта для знаходження підрядка в рядку. курсовая работа , добавлен 16.09.2010 Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов. лабораторная работа , добавлен 03.12.2014 Разработка на языке ассемблера алгоритма контроля, на циклический CRC-код, массива данных хранящегося в некоторой области памяти. Сохранение кода для последующей периодической проверки массива данных. Сообщение об искажении данных. Описание алгоритма. Понятие алгоритма так же фундаментально для информатики, как и
понятие информации. Существует много различных
определений алгоритма, так как это понятие достаточно широкое и
используется в различных областях науки, техники и повседневной
жизни.
Алгоритм – понятная и точная последовательность действий,
описывающая процесс преобразования объекта из начального
состояния в конечное.
Исполнителем
алгоритма может быть как человек (кулинарные
рецепты, различные инструкции, алгоритмы математических
вычислений), так и техническое устройство. Различные
машины
(компьютеры, промышленные роботы,
современная бытовая техника) являются формальными
исполнителями
алгоритмов. От формального исполнителя не
требуется понимание сущности решаемой задачи, но требуется
точное выполнение последовательности команд.
Алгоритм можно записывать различными способами (словесное
описание, графическое описание – блок схема, программа на одном
из языков программирования и т.д.). Программа – это алгоритм,
записанный на .
Для создания алгоритма (программы) необходимо знать: полный набор исходных данных задачи (начальное
состояние объекта);
цель создания алгоритма (конечное состояние
объекта);
систему команд исполнителя (то есть набор
команд, которые исполнитель понимает и может выполнить).
Полученный алгоритм (программа) должен обладать следующим
набором свойств: дискретность
(алгоритм разбит
на отдельные шаги - команды); однозначность
(каждая команда
определяет единственно возможное действие исполнителя); понятность
(все команды
алгоритма входят в систему команд исполнителя); результативность
(исполнитель
должен решить задачу за конечное число шагов). Большая часть алгоритмов
обладает также свойством массовости
(с помощью
одного и того же алгоритма можно решать множество однотипных
задач). Выше отмечалось, что один и тот же алгоритм может быть записан
по-разному. Можно записывать алгоритм естественным языком.
В таком виде мы используем рецепты, инструкции и т.п. Для записи
алгоритмов,
предназначенных формальным
исполнителям,
разработаны специальные
языки программирования
. Любой алгоритм можно описать
графически в виде блок-схемы
. Для этого разработана
специальная система обозначений: Приведем
пример описания алгоритма суммирования двух величин в виде
блок-схемы:
Такой способ описания алгоритм наиболее нагляден и понятен
человеку. Поэтому, алгоритмы формальных исполнителей обычно
разрабатывают сначала в виде блок-схемы, и только затем создают
программу на одном из
.
Программист имеет возможность конструировать и использовать
нетипичные алгоритмические структуры, однако, в этом нет
необходимости. Любой сколь угодно сложный алгоритм может быть
разработан на основе трёх типовых структур: следования,
ветвления и повторения. При этом структуры могут располагаться
последовательно друг за другом или вкладываться друг в друга.
Наиболее простой алгоритмической структурой является линейная
.
В ней все операции выполняются один раз в том порядке, в
котором они записаны.
Ветвление.
В
полном ветвлении
предусмотрено два варианта действий
исполнителя в зависимости от значения логического выражения
(условия). Если условие истинно, то выполняться будет только
первая ветвь, иначе только вторая ветвь.
Вторая ветвь может быть пустой. Такая структура называется
неполным ветвлением или обходом
. Из нескольких ветвлений можно сконструировать структуру «выбор
»
(множественное ветвление), которая будет выбирать не из двух, а
из большего количества
вариантов действий исполнителя,
зависящих от нескольких условий
.
Существенно, что выполняется только одна ветвь - в такой
структуре важное значение приобретает порядок следования
условий: если выполняются несколько условий, то сработает только
одно из них - первое сверху.
Цикл
(повторение).
Цикл
позволяет организовать многократное повторение
одной и той же последовательности команд
- она называется
телом цикла. В различных видах циклических алгоритмов количество
повторений может зависеть от значения логического выражения
(условия) или может быть жестко задано в самой структуре.
Различают циклы:
«д
о
»,
«п
ока
»,
циклы со счётчиком.
В
циклах «д
о» и «п
ока»
логическое выражение (условие) может предшествовать телу цикла (цикл
с предусловием
) или завершать цикл (цикл с послеусловием
). Ц
иклы
«д
о
» - повторение тела
цикла до выполнения условия:
Ц
иклы
«п
ока
» - повторение тела
цикла пока условие
выполняется
(истинно):
Ц
иклы со счётчиком
(с параметром)
– повторение тела цикла заданное число раз:
Вспомогательный алгоритм
представляет собой модуль, к
которому можно многократно обращаться из основного алгоритма.
Использование вспомогательных алгоритмов может существенно
уменьшить размер алгоритма и упростить его разработку. Существует два метода разработки сложных алгоритмов: Метод последовательной детализации задачи
(«сверху-вниз»)
состоит в том, что исходная сложная задача разбивается на
подзадачи. Каждая из подзадач рассматривается и решается
отдельно. Если какие-либо из подзадач сложны, они также
разбиваются на подзадачи. Процесс продолжается до тех пор, пока
подзадачи не сведутся к элементарным. Решения отдельных
подзадач затем собираются в единый алгоритм решения исходной
задачи. Метод широко используется, так как позволяет вести
разработку общего алгоритма одновременно нескольким
программистам, решающим локальные подзадачи. Это необходимое
условие быстрой разработки программных продуктов. Сборочный метод
(«снизу-вверх») заключается в создании
множества программных модулей, реализующих решение типичных
задач. При решении сложной задачи программист может использовать
разработанные модули в качестве вспомогательных алгоритмов
(процедур). Во многих уже
существуют подобные наборы модулей, что существенно упрощает и
ускоряет создание сложного алгоритма. Управление
- целенаправленное
взаимодействие объектов, одни из которых являются управляющими,
другие - управляемыми.
В простейшем случае таких объектов два:
С точки зрения информатики управляющие
воздействия можно рассматривать как управляющую информацию.
Информация может передаваться в форме команд.
Последовательность команд по управлению объектом, приводящая к
заранее поставленной цели, называется алгоритмом управления
.
Следовательно, объект управления можно назвать исполнителем
управляющего алгоритма. В рассмотренном примере, управляющий
объект работает "не глядя" на то, что происходит с управляющим
объектом (управление без обратной связи
). Такая схема
управления называется незамкнутой
. Другая схема
управления может учитывать информацию о процессах, происходящих
в объекте управления:
В этом случае, алгоритм управления должен быть
достаточно гибким, чтобы анализировать эту информацию и
принимать решение о своих дальнейших действиях в зависимости от
состояния объекта управления (управление с обратной связью
).
Такая схема управления называется замкнутой
.
Более
подробно процессы управления изучаются рассматриваются
кибернетикой
. Эта наука утверждает, что самые разнообразные
процессы управления в обществе, природе и технике происходят
сходным образом, подчиняются одним и тем же принципам.
Подобные документы
Обозначение
Описание
Примечания
Начало и конец алгоритма
Ввод и вывод данных.
Вывод данных иногда
обозначают иначе:
Действие
В вычислительных
алгоритмах так обозначают присваивание
Развилка
Развилка - компонент,
необходимый для реализации ветвлений и циклов
Начало цикла с параметром
Типовой процесс
В программировании -
процедуры или подпрограммы
Переходы между блоками
Линейная структура (следование).
Вспомогательный алгоритм (подпрограмма, процедура).
Методы
разработки сложных алгоритмов.
