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


Скачать 105.21 Kb.
НазваниеСтруктуры и алгоритмы обработки данных
Дата22.04.2013
Размер105.21 Kb.
ТипРеферат
Структуры и алгоритмы обработки данных.


Целью изучения курса «Структуры и алгоритмы обработки данных» является освоение студентами методов представления данных в памяти ЭВМ и основных алгоритмов, оперирующих с ними.

Студент должен иметь представление:

  • об основных структурах представления данных в ЭВМ;

  • об алгоритмах, оперирующих со структурами;

  • об использовании структур представления данных для решения возникающих задач;

знать и уметь использовать:

  • основные понятия алгоритмических структур для построения алгоритмов и задач по их математическим моделям;

должен приобрести навыки:

  • грамотной постановки задач, возникающих в практической деятельности для их решения с помощью ЭВМ;

  • разработки оптимальных алгоритмов для решения поставленных задач;

  • формализованного описания поставленных задач.



СОДЕРЖАНИЕ ТЕОРЕТИЧЕСКОГО РАЗДЕЛА ДИСЦИПЛИНЫ

Введение

Разработка алгоритмов и проверка их правильности. Тестирование, аналитическое доказательство правильности алгоритмов, эффективность.

  1. Структуры представления данных в ЭВМ

Классификация. Линейные структуры данных: их последовательное и связанное представление, операции с ними. Нелинейные структуры данных: графы, деревья. Основные понятия и определения.

  1. Деревья. Основные понятия и определения

Ориентированные. Упорядоченные. Бинарные. Сбалансированные. Сильноветвящиеся. Представление деревьев в памяти ЭВМ. Последовательное и связанное размещение элементов. Конструирование оптимальных деревьев.

Операции над деревьями. Обход дерева, упорядочивание, поиск, включение/ удаление вершины.

  1. Графы и их представление в ЭВМ

Представление с помощью матрицы смежности, матрицы инцидентности, списков смежности, списков дуг.

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

  1. Задачи поиска

Исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование, поиск в глубину.

Быстрый поиск: бинарный и последовательный поиски в массивах, М-блочный поиск, хеширование. Выбор в линейных списках.

Использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска.

Алгоритмы поиска на графах: Алгоритм Форда-Фанкерсона, алгоритм поиска кратчайшего пути, жадный алгоритм.

  1. Задачи сортировки

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

Анализ сложности и эффективности алгоритмов поиска и сортировки.

  1. Файлы

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


Контрольное задание по курсу Структуры и алгоритмы обработки данных.


Выполнить по шагам сортировку массива целых чисел методом простой сортировки. Вариант задания представлен в таблице. М1 – сортировка простыми включениями, М2 – сортировка простым выбором, М3 – сортировка простым обменом. Привести блок-схему метода.


Таблица вариантов.

п/п

Сортируемый массив

М1

М2

М3

1

87 76 3 53 87 79 54 74 72 67 79 57 89 9 93










2

48 70 10 50 71 39 7 50 90 42 41 22 49 23 92










3

87 11 35 74 74 4 13 92 82 16 10 53 55 42 2










4

27 84 17 85 67 86 53 53 60 75 3 90 34 85 69










5

60 99 49 82 32 30 99 79 19 76 96 79 74 4 44










6

14 16 74 6 97 30 33 70 88 23 30 85 43 66 56










7

24 4 10 89 76 14 17 61 36 21 68 27 100 48 18










8

41 15 90 43 36 9 34 46 6 51 40 86 71 48 90










9

72 61 43 41 11 56 30 96 31 48 25 16 73 57 27










10

96 96 49 11 27 47 18 69 61 76 50 57 16 32 54










11

60 12 17 66 28 9 55 12 3 6 19 38 80 89 2










12

94 36 89 66 80 56 24 47 37 91 5 66 95 93 59










13

5 62 46 71 9 57 41 76 86 84 13 17 30 45 98










14

6 75 80 18 82 89 49 52 19 14 28 7 79 67 38










15

17 71 36 24 93 60 78 25 63 84 18 31 48 67 46










16

84 63 12 75 60 56 42 22 81 54 74 51 61 92 27










17

80 9 55 34 10 89 88 69 43 57 12 30 66 71 7










18

13 85 95 94 17 52 97 75 99 93 62 64 30 72 14










19

78 77 94 73 4 50 1 40 22 36 38 36 4 85 59










20

85 54 37 51 77 19 71 37 86 43 69 44 88 79 71










21

91 57 34 10 89 76 72 4 2 48 46 6 60 34 78










22

70 89 19 56 54 25 17 79 99 93 24 21 12 14 34










23

19 6 20 12 84 3 42 56 33 64 46 35 28 49 94










24

29 37 82 86 70 97 6 79 3 83 6 25 60 83 13










25

37 78 71 21 10 55 72 62 18 54 28 71 9 77 49










26

68 17 99 51 97 24 92 76 61 73 30 3 76 79 96










27

20 87 33 2 86 80 56 13 52 19 75 14 63 49 6










28

2 9 89 96 28 53 68 16 88 8 18 62 92 77 68










29

39 88 37 76 16 88 82 28 89 67100 39 62 84 10










30

97 93 94 21 69 90100 44 28 15 16 24 3 87 88










31

11 22 33 45 58 50 89 25 42 83 84 53 1 9 15










32

14 4 92 67 87 16 94 47 5 91 86 16 88 69 70










33

82 21 73 55 27 28 19 9 46 2 15 47 55 58 61










34

50 65 57 50 92 64 70 37 75 6 34 25 31 53 67










35

5 2 73 95100 61 30 52 73 80 71 13 15 96 58










36

23100 6 31 71 15 30 64 84 48 55 97 82 43 28










37

2 72 10 8 73 19 93 15 88 86 90 16 40 54 23










38

84 89 40 51 54 24 14 33 19 84 24 23 100 41 48










39

8 23 80 71 76 28 89 5 18 68 91 50 53 2 17










40

26 83 47 84 58 65 94 44 51 4 49 84 37 55 10










41

48 33 49 38 43 89 12 28 17 66 8 49 68 18 62










42

48 61 31 9 95 20 77 10 59 83 47 93 89 63 24










43

52 9 21 40 59 73 88 2 43 3 44 20 60 66 90










44

19 34 95 17 74 75 18 15 49 68 6 23 72 31 86










45

62 40 37 51 51 78 99 7 54 41 7 76 47 89 39










46

4 68 33 99 8 24 66 25 84 28 80 35 23 37 97










47

87 76 3 53 87 79 54 74 72 67 79 57 89 9 93










48

48 70 10 50 71 39 7 50 90 42 41 22 49 23 92










49

87 11 35 74 74 4 13 92 82 16 10 53 55 42 2










50

27 84 17 85 67 86 53 53 60 75 3 90 34 85 69










51

60 99 49 82 32 30 99 79 19 76 96 79 74 4 44










52

14 16 74 6 97 30 33 70 88 23 30 85 43 66 56










53

24 4 10 89 76 14 17 61 36 21 68 27 100 48 18










54

41 15 90 43 36 9 34 46 6 51 40 86 71 48 90










55

72 61 43 41 11 56 30 96 31 48 25 16 73 57 27










56

96 96 49 11 27 47 18 69 61 76 50 57 16 32 54












Перечень рекомендуемой литературы

  1. Вирт Н. Алгоритмы + структуры данных = программы: Пер.с англ. - М.: Мир, 1985. - 406 с.

  2. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. - М.:Мир, 1976.

  3. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. - М.:Мир, 1976.

  4. Трамбле Ж., Соренсон П. Введение в структуры данных: Пер.с англ. - М.: Машиностроение, 1982. - 784 с.

  5. Райли Д. Абстракция и структуры данных: Вводный курс: Пер.с англ. - М.: Мир, 1993. - 752 с.

  6. Брой М. Информатика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х частях. Ч.4/ Пер.с нем. - М.:Диалог-МИФИ, 1998. - 224 с.

  7. Евстигнеев В.А. Применение теории графов в программировании/ Под ред. А.П.Ершова. - М.: Наука. Гл. Ред. ФМЛ, 1985. - 352 с.







Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница