Типовые алгоритмы обработки данных

Фреймы

Марвин Минский, первый, кто предложил идею фреймов, описывает его следующим образом:

“Фрейм - это структура данных, представляющая стереотипную ситуацию, вроде нахождения внутри некоторого рода жилой комнаты, или сбора на вечеринку по поводу дня рождения ребенка. К каждому фрейму присоединяется несколько видов информации. Часть этой информации — о том как использовать фрейм. Часть о том, чего можно ожидать далее. Часть о том, что следует делать если эти ожидания не подтвердятся”.

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

С каждым слотом можно связать любое число процедур. Чаще всего со слотами связываются 3 типа процедур:

1, Процедура ЕСЛИ-ДОБАВЛЕНО Выполняется, когда новая информация помещается в слот.

2. Процедура ЕСЛИ_УДАЛЕНО Выполняется, когда информация удаляется из слота

3. Процедура ЕСЛИ-НУЖНО Выполняется, когда запрашивается информация из слота, а он пустой.

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

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

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

Существуют десятки видов алгоритмов сортировки. К сожалению нет универсального алгоритма сортировки. Эффективность алгоритма сортировки может зависеть от множества факторов:

- числа сортируемых элементов;

- возможности помещения всех элементов в доступную оперативную память;

- степени сортировки элементов к определённому моменту;

- диапазона и распределения значений сортируемых элементов;

- места расположения элементов (на диске, оперативной памяти) и т.д.

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

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

С точки зрения пользователя наибольший интерес представляют следующие виды: сортировка массива, сортировка строк, сортировка элементов файла.

Сортировка элементов массива. Сортировка массива заключается в ранжировании элементов массива по возрастанию или убыванию их значений.

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

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

Дата добавления: 2014-10-17