ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК

КАФЕДРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Д О П О Л Н Е Н И Е

К РАБОЧЕЙ УЧЕБНОЙ ПРОГРАММЕ

по дисциплине «Структуры и Алгоритмы Компьютерной Обработки Данных»

(наименование дисциплины)

для специальности

010503.65 – Математическое обеспечение и администрирование
информационных систем

(шифр и наименование)

с применением рейтинговой системы оценивания успеваемости студентов

г. Тюмень, 2010

1. Тематический план изучения дисциплины

1.2. Распределение часов курса дисциплины по темам и видам работ

№

Тема

недели семестра

Виды учебной работы и самостоятельная работа, в час.

Итого часов по теме

Итого количество баллов

Лекции*

Лабораторные занятия*

Самостоятельная работа*

1

2

3

4

5

6

7

8

Модуль 1.

Алгоритмы: построение и анализ.

1.

Т1. Введение. Цель и задачи курса. Временная сложность алгоритмов. Вычисление рекуррентных отношений.

1-2

2

2

4

8

0-4

2.

Т2. Методы построения алгоритмов.

3-4

2

2

4

8

0-6

3.

Т3. Структуры данных. Концепция АТД. Линейные структуры данных. Нелинейные структуры данных.

5-6

6

6

8

20

0-10

Всего

10

10

16

36

0-20

Модуль 2.

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

1.

Т1. Поиск в линейных таблицах.

6-7

4

4

6

14

0-10

2.

Т2. Поиск в нелинейных таблицах.

8-9

4

4

6

14

0-10

3.

Т3. Поиск в таблицах с вычисляемыми входами.

10-11

4

4

8

16

0-10

Всего

12

12

20

44

0-30

Модуль 3.

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

1.

Т1. Простые алгоритмы внутренней сортировки. Улучшенные алгоритмы внутренней сортировки. Алгоритмы сортировки за линейное время.

12-13

6

6

8

20

0-15

2.

Т2. Сортировка частично упорядоченного множества.

14-15

4

4

8

16

0-15

3.

Т3. Алгоритмы внешней сортировки.

16-18

4

4

7

15

0-20

Всего

14

14

23

51

0-50

Итого (часов, баллов) за семестр:

36

36

59

131

0 – 100

1.2. ОЦЕНКА РАБОТЫ СТУДЕНТОВ В РЕЙТИНГОВЫХ БАЛЛАХ

НЕ нашли? Не то? Что вы ищете?

Распределение рейтинговых баллов по видам работ и нормам контроля

Виды работ и контроля

Максимальное количество баллов

 

Модуль 1

Модуль 2

Модуль 3

Итого

Тема 1

Тема 2

Тема 3

Тема 4

Тема 5

Тема 6

Тема 7

Тема 8

Тема 9

Лекции

-

-

-

-

-

-

-

-

5

5

Лабораторные работы

5

5

5

5

5

5

5

5

5

45

Самостоятельная работа

5

5

5

15

Контрольная работа

10

10

20

Итоговое тестирование

15

15

Итого по дисциплине

5

5

10

10

15

10

15

10

20

100 

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

№ п/п

Вид контроля

Максимальное количество баллов

1.

Посещение лекционных занятий

В случае пропуска лекции без уважительной причины текущий рейтинг снижается на 1 балл

2.

Посещение лабораторных занятий

В случае пропуска занятия без уважительной причины текущий рейтинг снижается на 1 балл

3.

Выполнение лабораторных работ

За защиту лабораторной работы позже установленного срока количество баллов снижается на 1.

4.

Выполнение индивидуальных заданий в процессе самостоятельной работы

0-5 баллов

5.

Выполнение факультативных творческих заданий

За выполнение по инициативе студента факультативных творческих заданий текущий рейтинг может быть повышен на величину баллов за задание

6.

Участие в олимпиадах по программированию

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

7.

Контрольная работа

баллов

8.

Экзамен по дисциплине

0 - 5 баллов за ответ на вопрос экзаменационного билета

2. Примерная тематика курсовых работ

1. Прошитые деревья.

2. Деревья Хаффмана.

3. Деревья оптимального поиска.

4. Деревья цифрового поиска.

5. B+-деревья

6. Trie-деревья.

7. Patricia-деревья.

8. Суффиксные деревья.

9. Биномиальные кучи.

10. Фибоначчиевы кучи.

11. Поиск образца в строке: алгоритм Рабина-Карпа.

12. Поиск образца в строке: алгоритм Кнута-Морриса-Пратта.

13. Поиск образца в строке: алгоритм Бойера-Мура.

14. Задача о наибольшей общей последовательности.

15. Задача об оптимальной триангуляции многоугольника.

16. Каскадное слияние.

17. Сортирующие сети.

18. Алгоритм фрактального сжатия изображений

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

20. Вероятностные алгоритмы

21. Жадные алгоритмы

22. Динамическое программирование

23. Структуры данных и алгоритмы для внешней памяти.

24. Алгоритм умножения Тоома-Кука

25. Слоёные списки (скип-списки)

26. FFT и умножение больших чисел

3. Учебно-методическое и информационное обеспечение дисциплины

Основная литература:

1.  Алгоритмы и структуры данных: с примерами на Паскале. - Санкт-Петербург: Невский Диалект, 2008. -  352 с.

2. Новиков математика для программистов: учеб. пособие для студ. по направлению "Информатика и вычисл. техника"/ . - 3-е изд. - Санкт-Петербург: ПИТЕР, 20с.

3.  Введение в распределенные алгоритмы/ Ж. Тель. - Москва: Изд-во МЦНМО, 20с.

Дополнительная литература:

1. Деревнина данных и алгоритмы компьютерной обработки данных: Учебное пособие. - Тюмень: Издательство ТюмГУ, 20с.

2. Искусство программирования. Т1. Основные алгоритмы. – Москва: Изд. дом Вильямс, 2005. – 720 с.

Рабочая программа пересмотрена и одобрена на заседании кафедры программного обеспечения

протокол №___от «___» ________ 20___ г.

Заведующий кафедрой ПО / /