Что такое алгоритм в программировании

Содержание

Что такое алгоритм в программировании

Что такое алгоритм в программировании

Различают следующие виды алгоритмов :

линейный – список команд (указаний), выполняемых последовательно друг за другом;

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

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

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

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

1. определить температуру воздуха

2. если температура ниже 0, то надеть шубу, иначе надеть куртку

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

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

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

Какие алгоритмы должен знать уважающий себя программист?

    Ответы экспертов, 30 апреля 2015 в 1:38

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

Павел Емельянов , главный архитектор Virtuozzo

Сейчас в … “ненаучном” программировании алгоритмы не так важны. Хорошая алгоритмическая подготовка и смекалка пригодится в специфических областях, например в Big Data или компьютерном моделировании физических, социологических и других процессов реального мира. Даже игровая индустрия уже пережила тот период, когда как воздух требовались новые классные алгоритмы, на “стандартных” в большинстве случаев вполне можно жить.

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

Сергей Зефиров , программист с широким опытом работы, энтузиаст и евангелист языка Haskell

Он должен уметь выводить алгоритмы, а не знать их. Ровно как и математик должен уметь выводить доказательства.

На каких алгоритмах стоит потренироваться в выводе:

  • сортировки – от пузырька, до параллельной кеш-независимой сортировки;
  • динамическое программирование;
  • алгоритмы сжатия данных – кодирование Хаффмана, арифметическое кодирование, сжатие подпоследовательностей;
  • символические вычисления – как организовать;
  • как сделать статическую структуру динамической – как сделать быструю (O(logN)) вставку в упорядоченный массив.

Материалы по перечисленным темам:

  • Наша статья, посвященная пяти основным алгоритмам сортировки.
  • Введение в динамическое программирование для начинающих.
  • Книга, посвященная методам сжатия данных. Несколько тем, рассмотренных в книге: кодирование источников данных без памяти (канонический алгоритм Хаффмана, арифметическое сжатие, векторное квантование), словарные методы сжатия данных, методы контекстного моделирования и другие.
  • Введение в структуры данных для новичков: динамический массив.

Роман Юферев , руководитель направления ИТ-менеджмента и мониторинга в компании VIAcode

Сортировка «пузырьком». Шутка. Алгоритмы – это то, что нам нужно для обработки данных, а сейчас весь мир сталкивается с совершенно новыми задачами при обработке данных и новыми возможностями, поэтому собрание сочинений Кнута на полке уже не является показателем вашей крутости. В то же время, это не значит, что преподаватели в вузе учат вас какой-то “фигне”. Повторюсь – изучением алгоритмов и работой над учебными задачами вы тренируете, «разминаете» свои мозги, готовите их к реальной работе, поэтому не брезгуйте материалом, который вам дают в вузе, но и не рассчитывайте особо на его практическое применение в реальной профессиональной жизни.

Где можно «потренировать» мозги:

Еще больше сайтов с задачками вы можете найти в нашей статье «28 сайтов, на которых можно порешать задачи по программированию».

Василий Кобзарь , преподаватель GeekBrains, специализируется на администрировании Linux

Уважающий себя программист должен понимать абсурдность данного вопроса.

Антон Пискунов , основатель и генеральный директор BeastGaming

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

Читать еще:  Что такое семантика в программировании

Джозеф Браун , профессор Университета Иннополис

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

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

Андрей Ситник , веб-разработчик в Evil Martians

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

Александр Чистяков , главный инженер в Git in Sky

Алгоритмы сортировки и поиска, очевидно. Наша жизнь – это сортировка и поиск.

Александр Рожнов , Team Lead в компании Undev

  • Сортировка пузырьком;
  • разворачивание однонаправленного списка;
  • алгоритмы работы с бинарными деревьями;
  • алгоритмы работы с хеш-таблицами;
  • поиск описания работы интересующего алгоритма за o(n) в Интернете.

Материалы для изучения упомянутых Александром тем:

Всеволод Шмыров , разработчик в команде API Яндекс.Карт

Павел Егоров , заместитель руководителя управления разработки СКБ Контур

Что такое хорошая алгоритмическая подготовка?

Да, хорошая алгоритмическая подготовка важна для программиста. И нет, хорошая — это вовсе не заучивание алгоритмов из списка “Самых Важных Алгоритмов, Которые Должен Знать Каждый”. На мой взгляд хорошая алгоритмическая подготовка должна стремиться дать программисту следующие три умения.

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

Очевидно, для этого недостаточно просто знать алгоритмы. Нужно уметь “видеть их”, распознавать возможности их применения.

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

В-третьих, алгоритмическая подготовка должна помогать умело пользоваться готовыми инструментами. Базы данных — это сплошные структуры данных и алгоритмы. Причем на концептуальном уровне довольно простые и понятные — деревья поиска, хэштаблицы, SS-Table, …

Например, зная, что индекс в БД — это просто дерево поиска, несложно понять, какие запросы могут быть выполнены быстро, а какие обречены на full-scan.
Зная, как на каких алгоритмах работает полнотекстовый поиск в Lucene, можно предсказать, какие запросы к Elastic будут давать релевантные ответы, а какие — нет, и даже как это можно доработать.

Если подводить итог:

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

Для чего нужны алгоритмы? Основные алгоритмы программирования

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

Алгоритм — что это?

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

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

1. Работать за конечный объём времени. Если алгоритм не способен разобраться с проблемой за конечное количество времени, можно сказать, что этот алгоритм бесполезен.

2. Иметь чётко определённые инструкции. Любой шаг алгоритма должен точно определяться . При этом его инструкции должны быть однозначны для любого случая.

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

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

Алгоритмы сортировки (пирамидальная, быстрая, слиянием)

Какой алгоритм сортировки считают лучшим? Здесь нет однозначного ответа, ведь всё зависит от ваших предпочтений и поставленных перед вами задач. Рассмотрим каждый из алгоритмов:

1. Сортировка слиянием . Важнейший на сегодня алгоритм. Базируется на принципе сравнения элементов и задействует подход «разделяй и властвуй», позволяя более эффективно решать проблемы, которые когда-то решались за время O (n^2). Сортировка слиянием была изобретена математиком Джоном фон Нейманом в далёком 1945 году.

2. Быстрая сортировка . Это уже другой подход к сортировке. Тут алгоритм базируется, как на in-place разделении, так и на принципе «разделяй и властвуй». Однако эта сортировка нестабильна, что и является её проблемой. Зато алгоритм эффективен при сортировке массивов в оперативной памяти.

3. Пирамидальная сортировка . Алгоритм in-place который использует приоритетную очередь (за счёт этой очереди сокращается время поиска данных).

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

Преобразование Фурье. Быстрое преобразование Фурье

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

Алгоритм Дейкстры

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

Алгоритм RSA

Это алгоритм пришёл к нам из криптографии . Он сделал криптографию доступной всем, предопределив её будущее. Вообще, RSA-алгоритм сделан для решения простой задачи с неочевидным решением . Он позволяет делиться открытыми ключами между конечными пользователями и независимыми платформами таким образом, чтобы можно было применять шифрование.

Читать еще:  Ноутбук dexp безопасный режим

Алгоритм безопасного хэширования

Ну, это не совсем алгоритм. Скорее, его можно назвать семейством криптографических хэш-функций (SHA-1, SHA-2 и т.д.), которые разработаны в США и имеют важнейшее значение для всего мира. Антивирусы, электронная почта, магазины приложений, браузеры и т. п. — во всём этом используются алгоритмы безопасного хэширования (на деле хэш является результатом их работы). Алгоритм нужен для определения, удалось ли вам загрузить то, что хотели, а также не подверглись ли вы фишингу или атаке «человек посередине».

Анализ связей

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

Алгоритм был создан в далёком 1976 году и используется сегодня при ранжировании страниц в процессе поиска в Google, при генерации ленты новостей, при составлении списка возможных друзей на Facebook, при работе с контактами в LinkedIn и во многих других случаях. Любой из перечисленных сервисов работает с различными объектами и параметрами и объектами, однако сама математика по сути не меняется.

Пропорционально-интегрально-дифференцирующий алгоритм

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

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

Алгоритмы сжатия данных

Сложно сказать, какой алгоритм для сжатия наиболее важен, ведь в зависимости от поставленных задач он может меняться от zip до mp3 либо от JPEG до MPEG-2. Но эти алгоритмы важны почти для всех сфер деятельности.

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

Алгоритм генерации случайных чисел

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

Алгоритмы и программы

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

  • подготовить необходимую теоретическую базу для последующего овладения различными методами обработки информации, навыками программирования в малом и построения правильных эффективных программ;
  • дать минимально необходимые для практического программирования знания о языке Java и предоставить образцы небольших типовых программ.

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

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

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

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

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

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

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

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

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

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

Читать еще:  Как активировать xp в безопасном режиме

Пример и свойства алгоритма

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

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

Алгоритм решения задачи.

П1: Положить целое число равным двум и перейти на шаг П2.

П2: Если делится нацело на , то завершить работу алгоритма, выдав в качестве результата ; иначе перейти на шаг П3.

П3: Увеличить значение на единицу и перейти на шаг П2.

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

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

Основные свойства любого алгоритма — это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.

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

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

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

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

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

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

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

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

Понятие эффективности алгоритма имеет и свои количественные характеристики. Различают временную и емкостную эффективности. Первая из них характеризует время выполнения алгоритма, а вторая — требуемый для этого объем памяти. Важнейшие для практики вопросы оценки временной эффективности или сложности (complexity) алгоритмов рассматриваются ниже, в «лекции 5» .

Алгоритмы в программировании: основные понятия

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

Каждый алгоритм обладает следующими свойствами:

Пошаговость (Дискретность)

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

Определенность (Однозначность)

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

Понятность

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

Результативность

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

Массовость

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

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

Начало и конец алгоритма

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

Ввод и вывод данных

Ввод и вывод данных обозначается в виде параллелограмма

Действие

Выполняемое действие алгоритма обозначается в виде квадрата.

Развилка

Развилка используется для обозначения условий и циклов в виде ромба.

Начало цикла с параметром

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

Процесс

Процессом является процедуры и подпрограммы.

Стрелки

Стрелками обозначаются переходы между блоками алгоритма

Заключение

Есть много различных задач, которые решаются на основе различных алгоритмов. Во многом, большинство задач схожи и для их решения применяются общие алгоритмы. Понимание разных алгоритмов поможет выбрать наиболее правильный для решения той или иной задачи. А какие алгоритмы вам доводится часто применять на практике?

IT Новости из мира ПК
Добавить комментарий