31

Структуры и алгоритмы обработки данных Введение

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

Данные – представление фактов и идей в формализованном виде для передачи или обработки их при помощи некоторого процесса (алгоритма).

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

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

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

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

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