Теория алгоритмов — это дисциплина, которая находится на грани между информатикой и математикой и изучает общие законы формирования алгоритмов.
Введение
Основным базовым компонентом при формировании программ является алгоритм, представляющий собой набор очерёдности выполнения операций, которые должны привести от начальных данных к искомому результирующему итогу.
Необходимость алгоритмов появилась из-за ограниченных объёмов доступной памяти, временных интервалов функционирования компьютеров и других моментов, возникающих при решении сформулированных проблем.
На текущий момент имеется немалое число спроектированных алгоритмов, отличающихся по сложности и предназначенных для различных областей деятельности людей. Это позволяет решать практически любые, стоящие перед составителями программ задачи, при условии правильного использования этих алгоритмических структур в различных сочетаниях.
Структура информации — это комплект элементов информационных данных и все их взаимные связи. Разнообразных структур информации, так же существует очень много, и каждая из структур используется в конкретной области. При создании очень многих прикладных программ, главным параметром, который определяет выбор, является именно структура представления информации. Когда этот выбор сделан, процедура создания алгоритма превращается в рутинную задачу, не вызывающую затруднений при её решении. Но, следует отметить, что одна и та же информация при разных её структурных формах, может требовать разные объёмы памяти. И аналогичные операции, но различной структурной организации тех же самых данных, могут сформировать алгоритмы разного уровня эффективности. Это означает, что выбор конкретного алгоритмического решения сильно зависит от оптимального выбора исходной структуры информационных данных.
Классификация структуры данных
Основные параметры, на основании которых может быть классифицирована структура данных, следующие:
- Методы отображения данных.
- Параметры памяти, используемой для сохранения информации.
- Уровень сложности выражения данных.
- Способы распределения компонентов внутри структуры.
- Степень изменяемости данных.
По методам отображения данные могут быть поделены на формы логической и физической структуры. Физическая структура — это метод сохранения данных в памяти компьютерного оборудования. Логической структурой считается такая информационная структура, которая не затрагивает методику её сохранения в компьютерной памяти. Почти всегда, присутствуют отличия между структурой, выраженной физически, и её описанием в логических формах, которое зависит от внешних характеристик и самой структуры. Существуют специальные операции, отображающие физическую структуру в форме логической, и есть, так же, обратная процедура.
По виду используемой памяти для хранения информации, согласно размещению и предоставлению её доступности, существует внутренняя и внешняя структура данных. Внутренняя структура предполагает хранение данных в области статической или динамической памяти компьютера. Внешняя структура предполагает размещение данных на внешних запоминающих устройствах и считаются файловыми структурами.
По сложности отображения, структуры данных делятся на элементарные и составные. Элементарными можно считать структуры данных, которые не разделяются на отдельные компоненты. Относительно физической структуры необходимо заметить, что в фактической структурной организации компьютера и используемой в нём операционной системе практически всегда возможно заранее определить элементарные единицы данных и их местоположение в памяти. С логической точки зрения, данные, в формате элементарных единиц, просто неделимы. Под составными структурами данных понимаются структурные образования, которые можно поделить на отдельные компоненты, выступающие, со своей стороны, как иные структуры данных.
Главным параметром составных информационных структур считается порядок расположения их компонентов. Согласно этому параметру, структуры могут быть линейными и нелинейными. Линейные структуры делятся на последовательные и произвольные, что определяется расположением их компонентов в памяти. Нелинейными считаются структуры данных, обладающие многосвязными списками, графами и тому подобное.
Изменчивость возможно охарактеризовать как колебания числа компонентов или их взаимных связей. Однако, изменчивость структуры не означает, что надо учитывать колебания величин информационных компонентов, поскольку в таком случае все структуры данных могли бы обладать изменчивостью.
Проектирование и анализ алгоритмов
Алгоритм обработки информационных данных — это способ решения задачи, который возможно реализовать в конкретной среде программирования.
Тщательная доработка алгоритма является важнейшим элементом операции по решению задачи в любой области применения. Разработку алгоритма разрешения какой-либо реальной задачи принято начинать с примерной оценки степени её трудности, вычленения пограничных величин начальных данных, разбиение общей задачи на ряд других подзадач, обладающих меньшей сложностью. Обычно, не выполняется привязка алгоритма к его конкретной будущей реализации, так как есть достаточно много языков программирования. Они в некоторой степени зависят от своей платформы и аппаратного обеспечения. Аналогичные по структуре, но сформированные на разных языках алгоритмы, могут выдать разные по эффективности результаты. Необходимо учитывать, что некоторые языки программирования оснащены специальными библиотеками, реализующими базовые процедуры обработки информационных данных. Для обеспечения возможности переноса решения без потери их актуальности, не допустимо ориентировать их только на конкретные операции выбранного языка программирования. Это условие является основной причиной, которая позволяет считать главным выбор метода решения задачи, ориентированного на её специфику. Выполнить адаптацию алгоритма к конкретному программному языку можно позже.
