Министерство образования Российской Федерации
Воронежский государственный педагогический университет
РАБОЧАЯ ПРОГРАММА
дисциплины "Теоретические основы информатики"
для подготовки специалиста по специальности 030100 «Информатика»
с дополнительной специальностью 030200 «Математика»
(6 семестр)
Всего: 108 час.
Всего: 54
Из них: 36 лекционных
18 лабораторных
54 – СРС
Форма отчетности: 6 семестр экзамен
по учебному плану уч. г.
Составитель: доц.
Программа утверждена на заседании
кафедры информатики и МПМ
10 мая 2001 г., протокол №9
Заведующий кафедрой, профессор
_______________________
Воронеж – 2001
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Курс является одной из завершающих образование специалиста компьютерных дисциплин. Он содержит систематизированное изложение основных понятий информатики: информация, алгоритма, модели задачи. Большое внимание уделено понятию информации и различным формам ее представления, ориентированных на машинную обработку. Изучаются также понятия алгоритма, свойства и классификация алгоритмов, способы их формального отношения и исполнения. Целью курса является обобщение информации, содержащейся отдельными частями в разных компьютерных дисциплинах и приобретение навыков решения задач, связанных с проверкой эффективности и сложности разрабатываемых алгоритмов. По курсу рекомендуются провести две контрольных работы.
2. ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ
№ | Тема | Всего в трудоемкости | В том числе аудиторных | СРС | ||
Всего | Лекции | Лаборат. | ||||
1. | Информация. Измерение информации. | 16 | 8 | 6 | 2 | 8 |
2. | Алгоритмы. Сложность алгоритмов. Реально выполнимые алгоритмы. | 12 | 6 | 4 | 2 | 6 |
3. | Полиномиальные алгоритмы. | 12 | 6 | 4 | 2 | 6 |
4. | Основные методы разработки алгоритмов. | 24 | 12 | 8 | 4 | 12 |
5. | Исчерпывающий поиск. Сложность задачи. Оценки. Понятие трудной задачи. | 12 | 6 | 4 | 2 | 6 |
6. | Алгоритмы оптимизации. | 20 | 10 | 8 | 2 | 10 |
7. | Комбинаторные алгоритмы. | 12 | 6 | 2 | 4 | 6 |
Итого: | 108 | 54 | 36 | 18 | 54 | |
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Информация. Информационные процессы. Непрерывная и дискретная форма представления информации качество и единицы измерения информации. Кодирование информации. Классификация и виды кодов.
Алгоритмы. Основные понятия теории алгоритмов. Свойства алгоритмов. Формы и способы представления алгоритмов. Рекурсия и итерация. Сложность и асимптотическая сложность алгоритмов. Реальный выполнимые алгоритмы.
Основные методы разработки алгоритмов. Понятие эффективности алгоритма. Понятие о динамическом программировании. Цель и методы динамического программирования. Метод балансировки. Изменения представления данных.
Понятие исчерпывающего поиска. Оценки сложности задачи. Верхние и нижние оценки. Понятие трудной задачи. Критерии трудности.
Алгоритмы оптимизации. Сетевые и графические алгоритмы. Понятие жадного алгоритма. Матрицы. Теорема Радо-Эдмондса.
Комбинаторные алгоритмы. Приближенные комбинаторные алгоритмы. Оценки их точности. Использование комбинаторных формул при оценки размера пространства поиска в переборных задачах программирования.
4. РЕКОМЕНДАЦИИ К СРС
Занятия по теоретическим основам информатики проводятся по подгруппам в компьютерных классах. Задания для работы выдаются и обсуждаются преподавателем на лекционных занятиях. В качестве отчетности используются контрольные работы.
Индивидуальные задания для самостоятельной работы выдаются преподавателем на лабораторных занятиях и выполняются в специально отведенное для этого время в присутствии лаборанта.
5. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
Основная литература:
1. , Информатика. - М.: Высш. шк., 19с.
2. Информатика. 4.1, 2, 3. - М.: Диалог-МИОП, 1996.
3. Бауэр . 4.1, 2. - М.; Мир, 1990.
6. ВОПРОСЫ К ЭКЗАМЕНУ
1. Понятия информации и информационных процессов. Свойства информации. Формы представления.
2. Количество и объем информации. Единицы измерения информации. Формула Шеннона.
3. Коды и кодирование информации. Классификация и виды кодов. Понятие о криптограмме.
4. Основные понятия теории алгоритмов. Свойства. Формы и способы представления.
5. Рекурсия. Формы рекурсий.
6. Итерация. Примеры итерационных алгоритмов.
7. Понятие сложности алгоритмов. Асимптотическая сложность. Реально выполняемые алгоритмы.
8. Поиск эффективности алгоритма. Классификация методов разработки алгоритмов.
9. Понятие о динамическом программировании, его целях и методах.
10. Метод балансировки разработки эффективных алгоритмов.
11. Изменение представления данных как метод повышения эффективности алгоритма.
12. Понятие об исчерпывающем поиске. Оценки сложности задачи. Верхние и нижние оценки.
13. Сетевые алгоритмы. Определения и примеры.
14. Алгоритмы на графах. Определения и примеры.
15. Понятие жадного алгоритма. Матрицы.
16. Приближенные комбинаторные алгоритмы. Классификация.
17. Оценка точности комбинаторных алгоритмов.
18. Использование комбинаторных алгоритмов в задачах перебора.
