Министерство образования Российской Федерации

Московский государственный университет
приборостроения и информатики

 

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

(Анализ эффективности алгоритмов)

 

 

Учебное пособие

 

Москва 2009

УДК 681.3

 

Филатов В.В.

Структуры и алгоритмы обработки данных (Анализ эффективности алгоритмов) – М.:МГУПИ, 2009. – 1 с.

 

 

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

Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Методы программирования» студентами различных форм обучения, проходящих подготовку по специальностям 230105 и 090105.

 

 

Рецензенты:

 

 

Утверждено:

Содержание

Структуры и алгоритмы обработки данных.................................................... 1

Введение......................................................................................................... 4

1 Основные сведения............................................................................... 5

1.1 Понятия алгоритма и структуры данных............................................... 5

1.2 Понятия сложности и эффективности алгоритмов и структур данных. 9

1.3 Асимптотические обозначения.............................................................. 12

1.3.1 Асимптотически точная оценка функции роста........................... 12

1.3.2 - и - обозначения.................................................................... 14

1.3.3 и обозначения................................................................... 15

1.3.4 Свойства асимптотических функций............................................. 17

1.3.5 Сложение и умножение в O-символике........................................ 21

1.3.6 Ограниченность показателя функции роста................................. 22

1.3.7 Основные классы эффективности.................................................. 23

1.3.8 Принципы анализа эффективности нерекурсивных алгоритмов 25

1.3.9 Примеры анализа алогритмов...................................................... 28

1.3.10 Формулы, использующиеся анализе алгоритмов...................... 32

Литература.................................................................................................. 35

Русскоязычные ресурсы InterNet.................................................. 36

 

Введение

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

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

Во втором разделе приводятся описания различных структур данных и основных операций над ними. Рассмотрены простые и сложные (составные) типы данных, линейные и нелинейные структуры, а также файлы.

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

Материал учебного пособия базируется на следующих дисциплинах: «Информатика», «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика»

.