Задачи для лабораторных работ

 

1. Составить программу, решающую системы линейных уравнений методом Гаусса. Исходная матрица уравнения является треугольной. Для хранения структуры данных использовать одномерные массивы.

 

Примечание: Программа не должна оперировать с двумерными массивами

 

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

 

Примечание: Обычная запись числа: (10+2)*5. Польская бесскобочная запись для данного выражения имеет вид: 10 ­ 2 ­ + 5 ­ *, где символом ­ обозначается помещение элемента в стек. Программа должная выглядеть следующим образом. На экране в любой момент времени можно ввести либо какое-либо число, либо арифметическую операцию (+,-,*,/). Если вводится число, то оно автоматически помещается в стек. Если вводится какая-либо арифметическая операция, то должны извлечься два последних числа из стека, произвестись над ними арифметические действия и затем результат помещается в стек и выводится на экран. Необходимо предусмотреть возможность предупреждения пользователя, когда он собирается выполнить какое-либо арифметическое действие над двумя числами, а в стеке только одно число, например: 10 ­ 2 ­ + 5 ­ * - +

 

3. Написать программу, которая умеет вставлять, удалять элементы из бинарного упорядоченного дерева, а также отображать текущую структуру дерева.

 

Примечание: Отображать структуру дерева можно в любом виде, однако самым простым способом представляется отображение дерева в режиме каталога

 

4. На основе программы 3 реализовать один из алгоритмов балансировки деревьев.

 

Примечание: Балансировка дерева должна осуществляться на момент вставки. Удаление элементов из сбалансированного дерева можно опустить. Также в программе должна быть предусмотрена возможность отображения текущей конфигурации дерева

 

5. Реализовать сравнительный анализ не менее 5 способов сортировки, которые принадлежат не менее четырем семействам методов (сортировка путем вставок, обменная сортировка, сортировка посредством выбора, сортировка методом слияния, сортировка методом распределения).

 

Примечание: Для сравнения методов должен использоваться один и тот же массив случайных чисел. Количество элементов в массиве должно задаваться с клавиатуры. Результатом работы программы должна быть таблица, в которой приводятся реализованные методы сортировок и затраченное ими машинное время на выполнение алгоритма.

 

6. Написать программу, реализующую сравнительный анализ трех способов последовательного поиска

 

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

 

8. Написать программу, находящую минимальное остовное дерево для графа

 

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

 

10. Написать программу, определяющую максимальный поток в графе.

 

Заключение

 

Разработка высокопроизводительных алгоритмов по обработке информации не прекращается ни на минуту. Каждый год в научных журналах появляются новые способы поиска информации, анализ того или иного алгоритма и т.д. И поэтому внимательный читатель данного пособия может подвергнуть сомнению целесообразность практического использования ряда алгоритмов приведенных в нем. Однако целью данной части курса было не только знакомство с оптимальными алгоритмами, но и выработка у студентов творческого мышления и способности к критическому анализу сделанного ранее. После того, как произошло знакомство с основными алгоритмами по обработке информации, необходимо переходить к рассмотрению современных способов разработки программного обеспечения – объектно-ориентированному проектированию и технологии RUP. Рассмотрению этих и других вопросов будут посвящены следующие части данного учебно-методического пособия.

 

 

Библиографический список

 

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

2. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.

3. Далека В. Д., Деревянко А.С., Кравец О.Г., Тимановская Л.Е. Модели и структуры данных. – Харьков: ХГПУ, 2000. – 241с.

4. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Издательский дом “Вильямс”, 2000. – 720 с.

5. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ.: Уч. пос. – М.: Издательский дом “Вильямс”, 2000. – 832 с.

6. Стивенс Р. Delphi. Готовые алгоритмы. – М.:ДМК Пресс, 2001. – 384с.

 

[1] Вводная часть данной темы составлена на основе материалов монографии [3]

[2] Составлено на основе материалов монографии [6]

[3] Составлено на основе материалов монографий [3,6]

[4] Правильнее будет сказать, что функция SetLength выполняет копирование растущего списка в заново выделенную память только в том случае, если его не удается расширить текущий сегмент памяти, отведенный под хранение массива. Это является одним из достоинств динамических массивов в Delphi.

[5] Во всяком случае, данная структура данных не требует наличия такой связи

[6] Составлено на основе материалов монографии [6]

[7] Составлено на основе материалов монографий [4,6]

[8] Составлено на основе материалов монографий [4,6]

[9] Под “достижением конца дерева” понимается попытка перехода с текущего узла по ссылке на дочерний, однако соответствующее значение ссылки является пустым

[10] Самым худшим случаем с точки зрения разбалансировки дерева является последовательное добавление в дерево возрастающей последовательности элементов

[11] Имеется в виду ситуация, когда нарушается условие AVL-дерева

[12] Составлено с использованием материалов сайта http://algolist.manual.ru

[13] Составлено с использованием материалов сайта http://algolist.manual.ru

[14] Составлено на основе материалов монографии [6]

[15] Свое название Б-деревья получили по фамилии их разработчика Байера (Bayer)

[16] Составлено на основе материалов монографий [5,6]

[17] Составлено с использованием материалов сайта http://algolist.manual.ru

[18] Составлено на основе материалов монографии [5]

[19] Составлено с использованием материалов сайта http://www.citforum.ru

[20] Составлено на основе материалов монографии [5]

[21] Составлено на основе материалов монографии [5]

[22] Составлено на основе материалов монографии [6]