6.2. Средства обеспечения освоения дисциплины

Не предусмотрены.

7. Материально-техническое обеспечение дисциплины

(Специализированные лаборатории и классы, приборы, установки, стенды, типовое оборудование).

Класс ПЭВМ не ниже Intel Pentium133, 32М RAM, 1G HDD с установленным программным обеспечением: MS Windows 95, MS Office, Borland С++.

Из расчета одна ПЭВМ на одного человека.

8. Методические рекомендации по организации изучения дисциплины

Примерным учебным планом на изучение дисциплины отводится два семест­ра. В конце первого семестра предусмотрен зачет, а в конце второго - экзамен. В каждом семестре выполняется одно домашнее задание.

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

(по специальности 075500 - 4 и 5 семестры,

по специальности 075200 - 5 и 6 семестры)

Предлагается:

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

во втором разделе привести классификацию алгоритмов сортировки и боль­ше внимания уделить сравнительному анализу сложности их работы.

в третьем разделе показать возможные подходы к классификации алгорит­мов поиска, заострить внимание на необходимости комплексного подхода к выбору структуры данных при реализации конкретного алгоритма;

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

в пятом разделе подчеркнуть какую важную роль играют в вопросах заши­ты информации алгоритмы, порождающие псевдослучайные последователь­ности, перестановки на множестве элементов и коды Грея;

8.1. Рекомендуемый перечень тем практических занятий:

1. Понятие структуры данных. Стеки, деки, очереди, линейные списки и деревья.

2. Алгоритмы сортировки сравнениями. Вывод нижней оценки для трудо­емкости работы алгоритмов данного типа.

3. Алгоритм сортировки вставками и вывод оценки его трудоемкости.

4. Обменная сортировка. Алгоритм быстрой сортировки.

5. Сортировка выбором. Турнирная и пирамидальная сортировки.

6. Сортировки слиянием и распределяющие сортировки.

7. Алгоритмы исчерпывающего поиска.

8. Алгоритмы поиска в последовательно организованных файлах.

9. Алгоритмы поиска в деревьях.

10. Хеширование и способы разрешения коллизий.

11. Способы задания графа. Остовное дерево. Алгоритм поиска в глубину.

12. Алгоритм поиска сильно связных компонент.

13. Нахождение двусвязных компонент.

14. Алгоритм построения минимального остовного дерева.

15. Моделирование равномерно распределенных случайных величин.

16. Алгоритмы порождения перестановок в лексикографическом порядке и циклическим сдвигом.

8.2. Рекомендуемый перечень тем индивидуальных занятий

1. Алгоритм сортировки вставками Шелла..

2. Обменная сортировка со слиянием алгоритм Бэтчера.

3. Лексикографическая сортировка.

4. Внешняя сортировка.

5. Алгоритмы поиска с возвращениями.

6. Индексно-последовательный поиск.

7. Построение оптимальных бинарных деревьев поиска.

8. Алгоритм сортировки в дерево.

9. Балансировка деревьев по высоте. 10. Балансировка деревьев по весу.

11. Цифровой поиск.

12. Алгоритм поиска в ширину.

13. Алгоритм нахождения кратчайшего пути.

14. Алгоритм транзитивного замыкания.

15. Алгоритм нахождения кратчайших расстояний от источника до всех ос­тальных вершин.

16. Моделирование равномерно распределенных дискретных случайных величин.

17. Моделирование равномерно распределенных дискретных случайных величин.

18. Алгоритмы порождения перестановок в порядке минимального измене­ния.

19. Коды Грея