Как называется сортировка происходящая в оперативной памяти

Обновлено: 07.07.2024

Цель лекции: изучить основные алгоритмы внутренних сортировок и научиться решать задачи сортировок массивов различными методами (бинарная пирамидальная сортировка , метод Шелла, быстрая сортировка Хоара, сортировка слиянием ).

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

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.

Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию.

В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг за другом в любом порядке. Однако иногда бывает полезно сохранять первоначальный порядок элементов с одинаковыми значениями.

В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки . Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.

Практически каждый алгоритм сортировки можно разбить на 3 части:

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

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

Оценка алгоритмов сортировки

Ни одна другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Универсального, наилучшего алгоритма сортировки на данный момент не существует. Однако, имея приблизительные характеристики входных данных , можно подобрать метод, работающий оптимальным образом. Для этого необходимо знать параметры, по которым будет производиться оценка алгоритмов.

Время сортировки – основной параметр, характеризующий быстродействие алгоритма.
Память – один из параметров, который характеризуется тем, что ряд алгоритмов сортировки требуют выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив данных и независящие от входной последовательности затраты, например, на хранение кода программы .
Устойчивость – это параметр, который отвечает за то, что сортировка не меняет взаимного расположения равных элементов.
Естественность поведения – параметр, которой указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Классификация алгоритмов сортировок

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

Наиболее подробно рассмотрим классификацию алгоритмов сортировки по сфере применения. В данном случае основные типы упорядочивания делятся следующим образом.

Внутренняя сортировка – это алгоритм сортировки, который в процессе упорядочивания данных использует только оперативную память ( ОЗУ ) компьютера. То есть оперативной памяти достаточно для помещения в нее сортируемого массива данных с произвольным доступом к любой ячейке и собственно для выполнения алгоритма. Внутренняя сортировка применяется во всех случаях, за исключением однопроходного считывания данных и однопроходной записи отсортированных данных. В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память .
Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных использует внешнюю память , как правило, жесткие диски. Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память . Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ .

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

Следует отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к носителям.

Рассмотрим основные алгоритмы внутренних сортировок, которые называются усовершенствованными (логарифмическими).

Бинарная пирамидальная сортировка

Данный метод сортировки был предложен Дж. У. Дж. Уильямсом и Р.У. Флойдом в 1964 году. Пирамидальная сортировка в некотором роде является модификацией такого подхода, как сортировка выбором , с тем лишь отличием, что минимальный (или максимальный) элемент из неотсортированной последовательности выбирается за меньшее количество операций. Для такого быстрого выбора из этой неотсортированной последовательности строится некоторая структура. Именно суть данного метода и состоит в построении такой структуры, которая называется пирамидой.

Пирамида (сортирующее дерево, двоичная куча) – двоичное дерево с упорядоченными листьями ( корень дерева – наименьший или наибольший элемент). Пирамиду можно представить в виде массива. Первый элемент пирамиды является наименьшим или наибольшим, что зависит от ключа сортировки .

Просеивание – это построение новой пирамиды по следующему алгоритму: новый элемент помещается в вершину дерева, далее он перемещается ("просеивается") по пути вниз на основе сравнения с дочерними элементами. Спуск завершается, если результат сравнения с дочерними элементами соответствует ключу сортировки.

Последовательность чисел x_i,x_i+1. x_n формирует пирамиду , если для всех k=i, i+1. n/2 выполняются неравенства x_k > x_2k, x_k > x_i (или x_k < x_2k, x_k < x_2k+1 ). Элементы x_2i и x_2i+1 называются потомками элемента x_i .

Массив чисел 12 10 7 5 8 7 3 является пирамидой. Такой массив удобно изображать в виде дерева. Первый элемент массива, элементы которого образуют собой пирамиду , является наибольшим (или наименьшим). Если массив представлен в виде пирамиды , то массив легко отсортировать.

Алгоритм пирамидальной сортировки.

Шаг 1. Преобразовать массив в пирамиду (рис. 42.1. А).

Шаг 2. Использовать алгоритм сортировки пирамиды (рис. 42.1. В – H).

Алгоритм преобразования массива в пирамиду (построение пирамиды). Пусть дан массив x[1],x[2]. x[n] .

Шаг 1. Устанавливаем k=n/2 .

Шаг 2. Перебираем элементы массива в цикле справа налево для i=k,k-1. 1 . Если неравенства x_i > x_2i, x_i > x_2i+1 не выполняются, то повторяем перестановки x_i с наибольшим из потомков. Перестановки завершаются при выполнении неравенств x_i > x_2i, x_i > x_2i+1 .

Алгоритм сортировки пирамиды.

Рассмотрим массив размерности n , который представляет пирамиду x[1],x[2]. x[n] .

Шаг 1. Переставляем элементы x[1] и x[n] .

Шаг 2. Определяем n=n-1 . Это эквивалентно тому, что в массиве из дальнейшего рассмотрения исключается элемент x[n] .

Шаг 3. Рассматриваем массив x[1],x[2]. x[n-1] , который получается из исходного за счет исключения последнего элемента. Данный массив из-за перестановки элементов уже не является пирамидой. Но такой массив легко преобразовать в пирамиду . Это достигается повторением перестановки значения элемента из x[1] с наибольшим из потомков. Такая перестановка продолжается до тех пор, пока элемент из x[1] не окажется на месте элемента x[i] и при этом будут выполняться неравенства x[i] > x[2i], x[i] > x[2i+1] . Тем самым определяется новое место для значения первого элемента из x[1] (рис. 42.1. С).

Шаг 4. Повторяем шаги 2, 3, 4 до тех пор, пока не получим n=1 . Произвольный массив можно преобразовать в пирамиду (рис. 42.1. D – H).

увеличить изображение
Рис. 42.1. Демонстрация бинарной пирамидальной сортировки по неубыванию

Построение пирамиды , ее сортировка и "просеивание" элементов реализуются с помощью рекурсии. Базой рекурсии при этом выступает пирамида из одного элемента, а сортировка и просеивание элементов сводятся посредством декомпозиции к аналогичным действиям с пирамидой из n-1 элемента.

Теоретическое время работы этого алгоритма можно оценить, учитывая, что пирамидальная сортировка аналогична построению пирамиды методом просеивания (при этом не учитывается начальное построение пирамиды ). Поэтому время работы алгоритма пирамидальной сортировки без учета времени построения пирамиды будет определяться по формуле T₁(n)=O(nxlog n) .

Построение пирамиды занимает T₂(n)=O(n) операций за счет того, что реальное время выполнения функции построения зависит от высоты уже созданной части пирамиды .

Тогда общее время сортировки (с учетом построения пирамиды ) будет равно: T(n)=T₁(n)+T₂(n)=O(n)+O(nxlog n)=O(nxlog n) .

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

Здравствуйте! Есть тест, который мне нужно решить, по разным дисциплинам. Многие вопросы мне не удалось загуглить, а в некоторых ответы отличаются совсем чуть-чуть. В тесте отмечены мои варианты ответа, возможно они не правильны. Может у кого будет время сможет их проверить или подсказать.

Модуль «Информатика и программирование»

Вопрос № 1. Сколько раз будет выведено на экран значение переменной i в соответствии с приведенным фрагментом программы?
for (int i=0; i<=10; i++)
cout << ++i << endl;

Вопрос № 3. Укажите, что выполняется в приведенном фрагменте кода:
int *p1 = new int(5); //1
int *p2 = new int[5]; //2
int *p3 = new int; //3

Вопрос № 5. Классический пример рекурсивного вызова функции - вычисление факториала
char factorial(int n)
if (n==0)
return 1;
return n*factorial(n-1);
>
.
int k=factorial(6);
Какое значение будет возвращено при вызове функции factorial(6) и сколько раз будет выполнена функция factorial в этом случае?

Вопрос № 6. Чему будет равняться значение переменной k после выполнения операторов
int a=4;
int b=5;
if (a=b)
k=1;
else
k=0;

Вопрос № 7. Необходимо найти ошибки в следующем фрагменте программы (синтаксические, логические, . ). :
int A[10], B[10], *C;
for(i=1;i<=10;i++)
cin>>A[i];
cin>>B[i];
>
for (i=1;i<=10;i++)
C[i]=A[i]+B[i];
Каждое возможное исправление/добавление в строчке кода считается за ошибку.
Определить количество ошибок, которое будет выдано на этапе компиляции.

Вопрос № 8. В теле функции может быть указан оператор <. return 1;>, если она возвращает значение типа:

Вопрос № 9. Перегрузка функций - использование одного и того же имени для разных функций. При этом действуют следующие ограничения:

1). перегруженные функции должны находиться в одной области видимости;
2). перегруженные функции должны находиться в разной области видимости;
3). не могут перегружаться функции, имеющие совпадающие тип и число аргументов, но разные типы возвращаемых значений;
4). не могут перегружаться функции, имеющие разное число аргументов и одинаковые типы возвращаемых значений;
5). не могут перегружаться функции, если их списки формальных параметров различаются только применением модификаторов const и volatile или использованием ссылки &, а типы возвращаемых значений одинаковые;
6). не могут перегружаться функции, если их списки формальных параметров различаются только применением модификаторов const и volatile или использованием ссылки &.

(в ответах 5 и 6 я не уверена)

Вопрос № 10. В С/С++ к целочисленным типам данных относят:

Модуль «Базы данных»

Вопрос № 1. Что означает наличие NOT NULL при описании атрибута в таблице?

Вопрос № 2. Какие из утверждений справедливы для понятия «внешний ключ»?

1). Значения внешнего ключа для каждой строки таблицы должны отличаться?
2). В таблице может быть несколько строк, имеющих одинаковое значение ключа.
3).В таблице может не быть ни одного внешнего ключа.
4). В каждой таблице может быть только один внешний ключ.
5). В таблице может быть несколько внешних ключей.

Вопрос № 3. В каких из перечисленных ниже случаях необходимо задавать ограничение на уровне таблицы?

Вопрос № 4. Какое из определений соответствует понятию «Возможный ключ»?

Вопрос № 5. В операторе выбора «SELECT» могут использоваться следующие агрегатные функции:

Вопрос № 6. Внешнее соединение – это:

Вопрос № 7. Какие из перечисленных ниже операторов относятся к языку манипулирования данными?

Вопрос № 8. Какие высказывания справедливы по отношению к оператору INSERT?

Вопрос № 9. Какие из приведенных определений являются корректными?

Вопрос № 10. Выберите все корректные высказывания по отношению к термину «Х-блокировка».

Вопрос № 11.Выберите все корректные высказывания по отношению к термину «S-блокировка».

Будем рассматривать задачу упорядочения совокупности данных , имеющих единообразную структуру вида [поле значений]+[ключ], в предположении, что на множестве значений ключей имеется отношение порядка “<”, удовлетворяющее двум условиям:

- закон трихотомии: для любых значений ивыполняется ровно одно из соотношений;

- закон транзитивности: (и).

Будем писать , если или.

Сортировкой называется упорядочение данных в порядке возрастания или убывания значений ключевого поля (для краткости будем говорить о возрастании или убывании самого ключа). Таким образом, при решении задачи сортировки ищется такая перестановка исходного множества номеров, при которой

Сортировка называется устойчивой, если она сохраняет относительный порядок для одинаковых значений ключа:

Устойчиво сортирующая перестановка единственна. Требование устойчивости существенно, если данные уже упорядочены по одному или нескольким другим (вторичным) ключам, не влияющим на основной ключ, и нежелательно разрушать эту упорядоченность.

Алгоритмы сортировки находят большое практическое применение. Они всегда сопровождают процессы обработки и хранения больших объемов информации. Выбор конкретного метода сортировки зависит как от структуры обрабатываемых данных (массивы, списки, деревья и т. д.), так и от архитектуры используемого компьютера.

Алгоритмы сортировки делят на два класса:

- внутренняя сортировка, при которой все данные хранятся и перемещаются в оперативной (быстрой) памяти с произвольным доступом ― в этом случае упорядочиваемые данные будем называть массивом;

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

В случае внутренней сортировки важно по возможности минимизировать количество наиболее часто повторяемых действий ― сравнений и обменов. Для внешней сортировки важно минимизировать число обращений к устройствам с медленным доступом (магнитным лентам, барабанам, дискам).

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

где .

Разные алгоритмы сортировки различным образом воздействуют на расположение сортируемых данных в памяти. Некоторые из них фактически переставляют элементы в памяти, то есть меняют их физические адреса. Другие сохраняют исходные физические адреса, но составляют дополнительную таблицу, содержащую сортирующую перестановку. В случае громоздкой структуры данных возможно также составление дополнительной таблицы, содержащей адресные ссылки на элементы и соответствующие значения ключа сортировки; после этого сортировка происходит только внутри этой таблицы. Последнее особенно предпочтительно, когда данные располагают несколькими ключами, и может потребоваться сортировка по различным комбинациям ключей.

Ключи сортировки часто не содержатся в исходной структуре данных в качестве отдельных полей, а имеют вид функций от поля (или полей) значений. Например, можно задать сортировку по количеству букв в поле “фамилия”, по лексикографической (алфавитной) упорядоченности “имён” и/или “отчеств” и т. п.

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

Методы сортировки разбиваются на несколько классов в зависимости от принципов, положенных в основу сортирующего алгоритма (рис. 22).

Внутри каждого класса содержатся методы, основанные на различных идеях (рис. 23).

Left : Указатель
Key : Ключ
Rec : Запись;

- Element=Запись
Left, Right : Указатели
Кеу : Ключ
Rec : Запись.

3. В памяти ЭВМ бинарное дерево удобно представлять в виде:
- связанных линейных списков;
- массивов;
- связанных нелинейных списков .
4. Элемент t, на котрый нет ссылок:
- корнем ;
- промежуточным;
- терминальным (лист).
5. Дерево называется полным бинарным, если степень исходов вершин равна:
- 2 или 0 ;
- 2;
- М или 0;
- M.

Лабораторная работа 6. Сортировка методом прямого включения.

1. Даны три условия окончания просеивания при сортировке прямым включением. Найдите среди них лишнее.
- найден элемент a(i) с ключом, меньшим чем ключ у x;
- найден элемент a(i) с ключом, большим чем ключ у x ;
- достигнут левый конец готовой последовательности.
2. Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?
- число сравнений ;
- время, затраченное на написание программы;
- количество перемещений;
- время, затраченное на сортировку.
3. Как называется сортировка, происходящая в оперативной памяти ?
- сортировка таблицы адресов;
- полная сортировка;
- сортировка прямым включением;
- внутренняя сортировка ;
- внешняя сортировка.
4. Как можно сократить затраты машинного времени при сортировке большого объёма данных ?
- производить сортировку в таблице адресов ключей ;
- производить сортировку на более мощном компьютере;
- разбить данные на более мелкие порции и сортировать их.
5. Существуют следующие методы сортировки. Найдите ошибку.
- строгие;
- улудшенные;
- динамические .

Лабораторная работа 7. Сортировка методом прямого выбора.

1. Метод сортировки называется устойчивым, если в процессе сортировки…
- относительное расположенние элементов безразлично;
- относительное расположение элементов с равными ключами не меняется ;
- относительное расположение элементов с равными ключами изменяется;
- относительное расположение элементов не определено.
2. Улучшенные методы имеют значительное преимущество:
- при большом количестве сортируемых элементов ;
- когда массив обратно упорядочен;
- при малых количествах сортируемых элементов;
- во всех случаях.
3. Что из перечисленных ниже понятий является одним из типов сортировки ?
- внутренняя сортировка ;
- сортировка по убыванию;
- сортировка данных;
- сортировка по возрастанию.
4. Сколько сравнений требует улучшенный алгоритм сортировки ?
- n*log(n) ;
- en;
- n*n/4.
5. К какому методу относится сортировка, требующая n*n сравнений ключей ?
- прямому ;
- бинарному;
- простейшему;
- обратному.

Лабораторная работа 8. Сортировка с помощью прямого обмена.

1. Сколько сравнений и пeрестановок элементов требуется в пузырьковой сортировке ?
- n*lon(n);
- (n*n)/4 ;
- (n*n-n)/2.
2. Сколько дополнительных переменных нужно в пузырьковой сортировке помимо массива, содержащего элементы ?
- 0 (не нужно);
- всего 1 элемент ;
- n переменных (ровно столько, сколько элементов в массиве).
3. Как рассортировать массив быстрее, пользуясь пузырьковым методом ?
- одинаково ;
- по возрачстанию элементов;
- по убыванию элементов.
4. В чём заключается идея метода QuickSort ?
- выбор 1,2,…n – го элемента для сравнения с остальными;
- разделение ключей по отношению к выбранному ;
- обмен местами между соседними элементами.
5. Массив сортируется “пузырьковым” методом. За сколько проходов по массиву самый “лёгкий” элемент в массиве окажется вверху ?
- за 1 проход ;
- за n-1 проходов;
- за n проходов, где n – число элементов массива.

Лабораторная работа 9. Сортировка с помощью дерева.

1. При обходе дерева

слева направо получаем последовательность…
- отсортированную по убыванию;
- неотсортированную ;
- отсортированную по возрастанию.
2. Какое из трёх деревьев не является строго сбалансированным ?

- A;
- B;
- C.
3. При обходе дерева слева направо его элемент заносится в массив…
- при втором заходе в элемент ;
- при первом заходе в элемент;
- при третьем заходе в элемент.
4. Элемент массива с ключом k=20 необходимо вставить в изображённое дерево так, чтобы дерево осталось отсортированным. Куда его нужно вставить ?

- левым сыном элемента 30 ;
- левым сыном элемента 41;
- левым сыном элемента 8.
-
5. При обходе какого дерева слева направо получается отсортированный по возрастанию массив ?

Лабораторная работа 10. Исследование методов линейного и бинарного поиска.
1. Где эффективен линейный поиск ?
- в списке;
- в массиве;
- в массиве и в списке .
2. Какой поиск эффективнее ?
- линейный;
- бинарный ;
- без разницы.
3. В чём суть бинарного поиска ?
- нахожденние элемента массива x путём деления массива пополам каждый раз, пока элемент не найден ;
- нахождение элемента x путём обхода массива;
- нахождение элемента массива х путём деления массива.
4. Как расположены элементы в массиве бинарного поиска ?
- по возрастанию ;
- хаотично;
- по убыванию.
5. В чём суть линейного поиска ?
- производится последовательный просмотр от начала до конца и обратно через 2 элемента;
- производится последовательный просмотр элементов от середины таблицы;
- производится последовательный просмотр каждого элемента .

Лабораторная работа 11. Исследование методов поиска с перемещением в начало и транспозицией.
1. Где наиболее эффективен метод транспозиций ?
- в массивах и в списках ;
- только в массивах;
- только в списках.
2. В чём суть метода перестановки ?
- найденный элемент помещается в голову списка ;
- найденный элемент помещается в конец списка;
- найденный элемент меняется местами с последующим.
3. В чём суть метода транспозиции ?
- перестановка местами соседних элементов;
- нахождение одинаковых элементов;
- перестановка найденного элемента на одну позицию в сторону начала списка .
4. Что такое уникальный ключ ?
- если разность значений двух данных равна ключу;
- если сумма значений двух данных равна ключу;
- если в таблице есть только одно данное с таким ключом .
5. В чём состоит назначение поиска ?
- среди массива данных найти те данные, которые соответствуют заданному аргументу ;
- определить, что данных в массиве нет;
- с помощью данных найти аргумент.

Лабораторная работа 12. Поиск по дереву с включением.

1. В каком дереве при бинарном поике нужно перебрать в среднем N/2 элементов ?

- A;
- B;
- C.
2. Сколько нужно перебрать элементов в сбалансированном дереве ?
A) N/2;
B) Ln(N);
C) Log2(N);
D) eN.
- A;
- B;
- C ;
- D.
3. Выберете вариант дерева, полученного после вставки узла -1.

- A ;
- B;
- C.
-
4. К какому элементу присоединить элемент 40 для вставки его в данное дерево ?

- к 30-му ;
- к 15-му;
- к –15-му;
- к 5-му.
5. Какой вид примет дерево после встаки элемента с ключом 58 ?

Лабораторная работа 13. Поиск по дереву с исключением.

1. Выберете вариант дерева, полученного после удаления узла –3.

- A;
- B ;
- C.
2. Какой вариант дерева получится после удаления элемента –1, а затем –8?

- A;
- B ;
- C.
3. Выберете вариант дерева, полученного после удаления узла с индексом 0.

- A ;
- B;
- C.
4. Какие из следующих пар чисел могут стать корнями дерева после удаления элемента 10 в соответсвии с двумя способами удаления узла, имеющего двух сыновей ?

- 0 или 15;
- 0 или 20;
- 5 или 30;
- 5 или 15 .
5. Какой вид примет дерево после удаления элемента с ключом 58 ?

МЕТОДИЧЕСКОЕ РУКОВОДСТВО К КУРСОВОЙ
РАБОТЕ

Курсовая работа выполняется студентами специальности 22.04 в четвертом семестре.
Целью курсовой работы является закрепление основ и углубление знаний в области структур и алгоритмов обработки данных в ЭВМ.
Тематика заданий на курсовую работу, приведенных в данных методических указаниях, может быть дополнена, расширена, увязана с решением актуальных научно-исследовательских задач, выполняемых на кафедре.

1 Требования к курсовой работе

1.1 Тема курсовой работы выдается каждому студенту индивидуально. В коллективных работах, в которых принимают участие два и более студентов, четко определяются объем и характер работы каждого студента. В задании формулируется задача, метод её решения.

1.2 Курсовая работа состоит из пояснительной записки, к которой прилагается дискета с отлаженными программами (пояснительная записка может быть выполнена в виде текстового файла в формате Microsoft Word).

1.3 В пояснительную записку должны входить:
- титульный лист (приложение Б);
- задание на курсовое проектирование (приложение А);
- реферат (ПЗ, количество таблиц, рисунков, схем, программ приложений, краткая характеристика и результаты работы);
- содержание:
а) постановка задачи исследования;
б) краткая теория по теме курсовой работы;
в) программная реализация исследуемых алгоритмов;
г) программа, с помощью которой проводилось исследование;
д) результаты проведенного исследования:
е) выводы;
- список использованной литературы;
- подпись, дата.

1.4 Пояснительная записка должна быть оформлена на листах формата А4, имеющих поля. Все листы следует сброшюровать и пронумеровать.

1.5 Исследование алгоритмов операций над структурами данных и методов сортировок и поиска проводить при следующих фиксированных количествах элементов в структурах: 10, 100, 1000, 10000.

1.6 Дополнительные условия выполнения курсовой работы выдаются руководителем работы.

2. Примерный перечень курсовых работ

1) Исследование стеков.
2) Исследование очередей.
3) Исследование кольцевых структур.

Читайте также: