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

Вид материала

Реферат

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

Подобный материал:

• Среда Turbo Pascal 5 Разделы описаний 6 решение, 661.4kb.
• Описание курса Цель курса, 44.75kb.
• С. М. Гусакова 1, А. С. Комаров 2, В. В. Устинов 3, В. Ю. Федорович 4 Вдоклад, 117.89kb.
• Назначение курса, 71.74kb.
• Курсовая работа является важным этапом по проверке готовности студентов к самостоятельному, 186.41kb.
• Пример рабочей программы дисциплины ооп основы построения современных систем, 65.27kb.
• А. М. Горького математико-механический факультет кафедра алгебры и геометрии Библиотека, 334.84kb.
• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• Структуры данных, 484.34kb.
• Курс «Физика электронных и ионных процессов» Направления: «Электроника и наноэлектроника»,, 24.62kb.

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


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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Файлы
   

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


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


Выполнить по шагам сортировку массива целых чисел методом простой сортировки. Вариант задания представлен в таблице. М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 с.