Методы программирования. Кулаков Ю.В - 7 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

27. Что из себя представляют связанные ортогональные списки, и как такие списки использует алгоритм S,
реализующий операцию осевого шага в разреженной матрице?
28. Каковы определения понятий дерева, корня дерева, поддерева, степени узла дерева, концевого узла, уз-
ла разветвления, уровня узла, упорядоченного и ориентированного дерева, леса?
29. Почему в разговоре о деревьях удобно использовать терминологию генеалогических деревьев?
30. Какие способы представления деревьев Вы знаете?
31. Какое дерево называется бинарным?
32. Что вкладывается в понятие прохождения бинарного дерева, и какие порядки прохождения бинарных
деревьев Вам известны?
33. Каким образом организуется представление бинарных деревьев посредством прошитых деревьев?
34. В чем заключается преимущество прошитого бинарного дерева перед непрошитым с точки зрения его
прохождения?
35. Каким способом деревья можно представить в виде бинарных деревьев?
36. Каковы прямой, обратный и концевой порядки прохождения лесов, и как эти порядки связаны с пред-
ставлением лесов с помощью вложенных скобок?
37. Каким образом могут быть представлены деревья при последовательном распределении памяти?
38. Почему для полной спецификации всякого ориентированного дерева или леса достаточно знания толь-
ко всех восходящих связей, и каким образом это обстоятельство используется в алгоритме Е обработки соот-
ношений эквивалентности?
39. Как понятие дерева используется в систематическом методе обнаружения независимых неизвестных в
задаче определения количества реализаций каждого шага некоторого алгоритма?
Литература: [1, с. 289–460], [6, с. 234–255].
Т е м а 2. АЛГОРИТМЫ СОРТИРОВКИ
Программа
2.1. Сложность алгоритмов
Понятия модели вычислений и оценки сложности алгоритмов.
2.2. Внутренняя сортировка
Основные понятия и стратегии сортировки. Алгоритмы сортировки вставками, выбором, слиянием, обменная
сортировка, распределяющая сортировка. Оценка сложности работы алгоритмов внутренней сортировки.
2.3. Внешняя сортировка.
Основные понятия внешней сортировки. Алгоритмы многофазного и каскадного слияния.
Методические указания
2.1. Сложность алгоритмов
Познакомьтесь с определением понятия модели вычислений и рассмотрите различные способы представле-
ния такой модели. Усвойте, что анализ сложности алгоритмов чрезвычайно важен в программировании для
ЭВМ и включает в себя оценку используемого объема памяти, а также время, необходимое для выполнения
алгоритма. На примере алгоритма М поиска максимального элемента одномерного массива детально изучите
только анализ времени выполнения алгоритма, поскольку для этого алгоритма достаточно запоминающего уст-
ройства фиксированного объема.
2.2. Внутренняя сортировка
Внимательно изучите понятие сортировки и некоторые из наиболее важных ее применений. Определитесь
с понятиями записи, файла, ключа, устойчивой сортировки и внутренней сортировки. Познакомьтесь с глав-
ными стратегиями сортировки: сортировкой вставками, обменной сортировкой, сортировкой посредством
выбора и сортировкой подсчетом.
Начните знакомство с методами внутренней сортировки с сортировки подсчетом и алгоритма C ее реали-
зации. Выполните этот алгоритм вручную для некоторых входных данных и проанализируйте полученные ре-
зультаты. Обратите внимание на то, что записи в этом алгоритме не перемещаются. Оцените время работы это-
го алгоритма и уясните, что он интересен для нас не эффективностью, а главным образом, своей простотой.
Рассмотрите затем другую разновидность сортировки подсчетом, называемую распределяющим подсчетом,
которая действительно весьма важна с точки зрения эффективности в условиях, когда имеется много равных
ключей и все они попадают в небольшой диапазон. Изучите алгоритм D сортировки распределяющим подсче-
том.
Далее изучите семейство методов сортировки, называемое сортировкой вставками и основанное на том,
что перед рассмотрением очередной записи предыдущие записи уже упорядочены. Изучите алгоритм S сорти-
ровки простыми вставками, выполните его вручную для некоторых входных данных и проанализируйте полу-
ченные результаты. Оцените время работы этого алгоритма. Познакомьтесь с методом сортировки, называемым
бинарными вставками, который существенно снижает общее число сравнений для вставляемых элементов.
Изучите алгоритм D метода сортировки Шелла с убывающим шагом, реализующий механизм, который позво-

Страницы