Основные алгоритмы обработки информации

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

Различные пути решения задачи могут быть сделаны либо за счет простого алгоритма и сложной структуры данных, либо наоборот. Будем рассматривать некоторые характерные или базовые виды алгоритмов. Самыми общими алгоритмическими задачами являются: а) задача поиска,(в некоторой ОС хранится некотороый объем анных, необходимо вычленить ту часть которая соответсвует предварительно поставленным условием(по сути является решением задачи)) т е задача поиска ориентирована на получения какого то конечного результата б)задача сортировки . представляет собой перестройку или перераспределение имеющихся данных под некоторое правило. Т е преобразование информации внутри информационной системы, сортировка не является конечной задачей Б не рассчитана на какой то окончательный результат, она обслуживает другие алгоритмические задачи, в частности задачу поиска Задача поиска. В целом задача поиска заключается в следующем: дан некоторый объем информации и некоторый образец для этих исходных данных формируется 2 вопроса есть а и образец х. .1содержит ли нужное 2 где содержится.

Поиск в массиве основной разновидностью задачей поиска является поиск в массиве.

Исходные данные а – последовательность однотипных элементов а0 а а2 … а-ное ответ – один из этих элементов, который каким то образом соответствует заданному образцу х. при этом соответсвие элемента массива образцу в общем случае может быть задано по разному. В самом простом случае это может быть тождественность т е х – это просто значение одного из элементов, который может содержаться в массиве а.

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

Т е поиск в массиве осуществляеся только по значению ключевых полей. Остальные поля играют роль доп нагрузки или коненчой цели реализации . прим. Массив содержит персональную информацию студентов ключем может быть ФИО или номер , а доп информация (адрес оценки и др) ответом является информация оценки и т д. 2)может бытьзадано более сложное отношение, прим значение больше или меньше какого то критического или удовлетворяет какой то сложной функции . задан массив точек. Стоит задача поиска точер за пределом круга некоторого радиуса р x^2+y^2<9

3) в некотором смысле частный случай предыдущего примера. Может быть задана специального вида функция

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