Самостоятельная работа с экзаменом- 78 часов Контактные часы 7 часов Экзамен 2 семестр Зачет нет Составитель рабочей программы профессор, Соколов Андрей Владимирович Цели освоения дисциплины Цели освоения учебной дисциплины «Информатика»

Общие сведения о дисциплине

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

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

3. 
   Телефонный справочник. Массив структур. Реализовать функции: добавить, удалить, найти, вывести список. Использовать передачу параметров (массив и количество элементов, например).
   

4. 
   Телефонный справочник. Связные списки. Реализовать функции: добавить элемент, добавить в указанное место, удалить заданный, найти, вывести список, обратить список. Использовать передачу параметров.
   

5. 
   Класс «Матрица». Разработать класс, реализовать основные операции, например «+, -, *, -, T», с помощью перегрузки операций.
   

6. 
   Стек и Очередь. Шаблоны, параметризованная реализация. Доработать main(): выбор операций.
   

7. 
   Бинарные деревья. 3 рекурсивных и 3 нерекурсивных реализации обходов бинарного дерева (прямой, обратный, концевой).
   

8. 
   Стековый калькулятор. Добавить свои функции.
   

9. 
   Сортировки. Реализовать 3 сортировки (кроме «Пузырек»), одна из которых «Быстрая». Сравнить время работы.
   

10. 
    Поиск в упорядоченном массиве (бинарный). Поиск со вставкой по бинарному дереву.
    

11. 
    Хеширование. «Метод цепочек» или «Поиск в открытой рассеянной таблице».
    

1. 
   Пирамидальная сортировка. Кнут. 3 том. Кормен.
   
2. 
   Красно-черные деревья. Кормен, Седжвик
   
3. 
   Биномиальные кучи. Кормен.
   
4. 
   Фибоначчиевые кучи. Кормен.
   
5. 
   Поиск в ширину в графе. Кормен.
   
6. 
   Поиск в глубину в графе. Кормен.
   
7. 
   Очереди с приоритетами (реализации на массивах и списках, сортирующее дерево, биномиальная очередь) Кормен, Седжвик.
   
8. 
   Списки пропусков Седжвик
   
9. 
   B-деревья Кормен, Седжвик, Кнут 3 том.
   
10. 
    Библиотека стандартных шаблонов. Шилдт, Страуструп. Классы контейнеры. Векторы. Списки. Строки.
    
11. 
    Представление линейного списка в виде сбалансированных деревьев. Д. Кнут 6.2.3.
    
12. 
    Threading Building Blocks интел. Containers
    
13. 
    Threading Building Blocks интел. Memory Allocation
    
14. 
    Threading Building Blocks интел. Parallelizing Simple Loops.
    
15. 
    Threading Building Blocks интел. Parallelizing Complex Loops
    
16. 
    GNU C Реализация функций динамического распределения памяти, malloc и др., и системы оbstack. Изучить методы реализации.
    
17. 
    Параллельные распределители памяти такие, например, как Hoard и Miser. Изучить методы реализации.
    
18. 
    Trie-дерево Седжвик
    
19. 
    Patricia-дерево Седжвик
    
20. 
    NVIDIA CUDA 4.0 Thrust C++. Сравнение с STL и TBB.
    
21. 
    Кратчайшие пути и умножение матриц. Кормен
    

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

1. 
   Способы передачи параметров в С и С++.
   
2. 
   Передача имён функций и указателей на функцию в качестве параметров функции.
   
3. 
   Работа с указателями. Массивы и указатели.
   
4. 
   Передача массивов и указателей в качестве параметров.
   
5. 
   Структуры. Массивы структур.
   
6. 
   Функции и структуры.
   
7. 
   Последовательное и связанное представление линейных списков.
   
8. 
   Реализация основных операций со связанными списками.
   
9. 
   Стеки, очереди, деки и способы их представления.
   
10. 
    Циклические списки, списки с двумя связями. Нестандартные методы представления линейных списков.
    
11. 
    Классы. Управление доступом к членам класса.
    
12. 
    Наследование. Виртуальные функции.
    
13. 
    Перегрузка бинарной операции с помощью функции-члена класса с одним параметром.
    
14. 
    Перегрузка бинарной операции с помощью функции не члена класса с двумя параметрами.
    
15. 
    Реализация последовательного стека с помощью параметризованного класса. Использование шаблонов.
    
16. 
    Бинарные деревья. Прямой, обратный и концевой обходы БД.
    
17. 
    Реализация некоторых алгоритмов работы с бинарными деревьями. Ввод дерева, рекурсивные и нерекурсивные обходы бинарных деревьев в глубину и в ширину .
    
18. 
    Представление лесов деревьев в виде бинарных деревьев. Обходы лесов деревьев.
    
19. 
    Последовательное представление дерева в обратном порядке, скобочные способы записи деревьев, прямая и обратная польские записи выражений.
    
20. 
    Реализация стекового калькулятора для вычисления выражений в обратной польской записи.
    
21. 
    Сортировка. Постановка задачи. Сортировка вставками. Метод Шелла.
    
22. 
    Обменная сортировка. Сортировка методом пузырька. Быстрая сортировка Хоара.
    
23. 
    Рекурсивная реализация быстрой сортировки.
    
24. 
    Стековая реализация быстрой сортировки.
    
25. 
    Сортировка типов, определённых пользователем с помощью перегрузки операции отношения порядка.
    
26. 
    Сортировка выбором. Сортировка слиянием. Внешняя сортировка.
    
27. 
    Последовательный поиск. Поиск в упорядоченной таблице.
    
28. 
    Поиск со вставкой по бинарному дереву.
    
29. 
    Оптимальные и сбалансированные деревья.
    
30. 
    Хеширование. Поиск со вставкой по таблице с цепочками.
    
31. 
    Поиск со вставкой по открытой рассеянной таблице.
    
32. 
    Введение во внешний поиск. В-деревья.
    
33. 
    Динамическое распределение памяти блоками фиксированного и переменного размеров.
    
34. 
    Виртуальная память.
    

1. 
   Аксенова Е.А., Соколов А.В. Алгоритмы и структуры данных на С++. Петрозаводск, изд-во ПетрГУ, 2008 г.
   
2. 
   Страуструп Б. Дизайн и эволюция C++. – М.: ДМК Пресс, СПБ.: Питер, 2007.
   
3. 
   Фридман А.Л. Язык программирования Си++: учебное пособие.- М., 2004.
   
4. 
   Франка П. С++: 26 уроков для освоения языка: Уч. курс. – СПб., 2001.
   
5. 
   Подбельский В.В. Язык Си++: Уч пос. – М., 2002.
   
6. 
   Громкович Ю. Теоретическая информатика: введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: [учебник] / Юрай Громкович. – 3-е изд. – СПб.: БХВ- Петербург, 2010.
   
7. 
   Кнут Д. Искусство программирования для ЭВМ.-М.:Мир. Т1, Т3. 2001.
   
8. 
   М. Эллис, Б. Строуструп. Справочное руководство по языку программирования С++ с комментариями. М.: Мир, 1992.
   

8. 
   Г. Шилдт. Теория и практика С++. BHV-Санкт-Петербург,1996.
   
9. 
   Р. Седжвик. Фундаментальные алгоритмы на С++. СПб: Изд.-во ДиаСофт. 2001.
   
10. 
    Вирт Н. Алгоритмы + структуры данных = программы. -М.:Мир, 1977.
    

11. 
    Г. Шилдт. Полный справочник по C. 4-е издание. М.: Изд-во Вильямс, 2002.
    
12. 
    Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: Изд-во ПетрГУ. 2002
    
13. 
    Кормен Е., Лейзерсон Ч., Ривест Р. Алгоритмы:построение и анализ. М.: МЦНМО, 2000.
    

1. 
   Электронный конспект лекций и наборы презентаций для лекционных занятий. Электронное пособие в открытом доступе.
   

2. 
   Программное обеспечение (свободно распространяемое): Транслятор C++.
   

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