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