Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Министерство образования Российской Федерации
Московский государственный университет
приборостроения и информатики
Структуры и алгоритмы обработки данных
(Анализ эффективности алгоритмов)
Учебное пособие
Москва 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
Введение
В этом учебном пособии описаны структуры данных и алгоритмы, знания которых является основой современного процесса программирования. Также приводятся основные приемы оценки эффективности и методы разработки алгоритмов, которые позволяют осуществлять сравнение и выбор наиболее оптимальных способов решения задач, возникающих при создании программного обеспечения различного назначения.
Учебное пособие состоит из трех разделов. В первом разделе рассматриваются основные понятия алгоритмов и структур данных, а также основные подходы к анализу их сложности.
Во втором разделе приводятся описания различных структур данных и основных операций над ними. Рассмотрены простые и сложные (составные) типы данных, линейные и нелинейные структуры, а также файлы.
Третий раздел посвящен основным алгоритмам обработки рассмотренных ранее структур данных и анализу сложности этих алгоритмов. Приводятся различные алгоритмы поиска, сортировки, сжатия данных и алгоритмы на графах, а также обсуждаются методы разработки алгоритмов.
Материал учебного пособия базируется на следующих дисциплинах: «Информатика», «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика»
.
Дата публикования: 2014-11-18; Прочитано: 758 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!