Теоретическая информатика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Саратовский государственный университет имени

Факультет компьютерных наук и информационных технологий

УТВЕРЖДАЮ

___________________________

"__" __________________20__ г.

Рабочая программа дисциплины

ТЕОРЕТИЧЕСКАЯ ИНФОРМАТИКА

Направление подготовки

231000 Программная инженерия

Профиль подготовки

Разработка программно-информационных систем

Квалификация (степень) выпускника

Бакалавр

Форма обучения

Очная

Саратов,

2011 год

1.  Цели освоения дисциплины

Целью освоения дисциплины «Теоретическая информатика» является изучение теоретических основ процессов хранения, передачи и обработки различных видов информации, теории кодирования, основ машинной арифметики. Студенты знакомятся с интуитивным и математическим понятием алгоритма, учатся проводить доказательство корректности программы.

2.Место дисциплины в структуре ООП бакалавриата

Данная учебная дисциплина входит в раздел «Математический и естественнонаучный цикл. Вариативная часть» ФГОС-3.

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

3 Компетенции обучающегося, формируемые в результате освоения дисциплины

Данная дисциплина способствует формированию следующих компетенций:

- понимание основных концепций, принципов, теорий и фактов, связанных с информатикой (ПК-1);

- способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);

- умение готовить презентации, оформлять научно-технические отчеты по результатам выполненной работы, публиковать результаты исследований в виде статей и докладов на научно-технических конференциях (ПК-5).

- навыки использования операционных систем, сетевых технологий, средств разработки программного интерфейса, применения языков и методов формальных спецификаций, систем управления базами данных (ПК-15);

В результате освоения дисциплины обучающийся должен:

Знать:

· значение информации в современном обществе;

· требования информационной безопасности;

· наиболее широко используемые классы информационных моделей;

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

Уметь:

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

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

· оформлять результаты своей профессиональной деятельности.

Владеть

· навыками использования современного математического аппарата при решении прикладных задач;

· базовыми математическими знаниями и информационными технологиями;

· навыками эффективного применения их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий.

4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 2 зачетные единицы, 72 часа (54 часа аудиторных).

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам)
1	Основные понятия	1	1	Л:4			Тест №1 на 1 неделе
2	Интуитивное и математическое понятие алгоритма	1	2-5	Л:10	СР:2		Тест №2 на 5 неделе
3	Основы машинной арифметики	1	5-7	Л:6	СР:4		Тест №3 на 7 неделе
4	Конечные автоматы	1	7-9	Л:8	СР:4		Тест №4 на 9 неделе
5	Детерминированные функции	1	10-12	Л:8	СР:2		Тест №5 на 12 неделе
6	Распознавание образов	1	13-15	Л:8	СР:2		Тест №6 на 15 неделе
7	Корректность программ	1	15-18	Л:10	СР:4		Тест №7 на 18 неделе
	Промежуточная аттестация		Зачет
	ИТОГО	54	18

Раздел «Основные понятия». Предмет теоретической информатики. Основные понятия. Информатика как наука и как вид практической деятельности. Место информатики в системе наук. Роль информации в современном обществе. Виды информационных процессов. Принципы получения, хранения, обработки и использования информации. Измерение информации.

Раздел «Интуитивное и математическое понятие алгоритма». Алгоритм. Свойства алгоритмов. Рекурсивные функции и сопутствующие алгоритмы. Алгоритм как система текстовых замен. Алгоритм как система термовых замен.

Раздел «Основы машинной арифметики». Системы счисления. Алгоритмы перевода. Представление чисел с фиксированной и с плавающей точкой. Представление отрицательных чисел в ЭВМ.

Раздел «Конечные автоматы». Автоматные функции. Состояния автомата. Эквивалентность состояний. Теорема об эквивалентности состояний конечного автомата.

Раздел «Детерминированные функции». Задание детерминированных функций при помощи деревьев, вес функций. Ограниченно-детерминированные функции. Задание ограниченно-детерминированных функций диаграммами переходов и каноническими уравнениями. Преобразование автоматными функциями периодических последовательностей. Операция суперпозиции. Отсутствие полных относительно операции суперпозиции конечных систем автоматных функций. Схемы из логических элементов и элементов задержки. Реализация автоматных функций.

Раздел «Распознавание образов». Проблема распознавания. Общая характеристика задач распознавания и их типы. Математическая теория распознавания образов. Постановка задачи распознавания. Алгебраический подход к задаче распознавания. Геометрические процедуры распознавания. Линейные разделяющие функции и поверхности решений. Процедуры коррекции ошибок. Выявление кластеров. Комбинаторно-логические процедуры распознавания. Тестовые алгоритмы. Алгоритмы распознавания, основанные на вычислении

Раздел «Корректность программ». Динамическая структура программы. Спецификация программ. Правила вывода для операторов С++.

5. Образовательные технологии

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

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

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

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

1.  Информатика: Учеб. для студентов вузов по естеств.-науч. спец. / Виталий Адольфович Каймин. - 2-е изд., перераб. и доп. - М. : Инфра-М, 20c.
 Информатика: учебник / . - 5-е изд. - М. : Инфра-М, 2008. – 283 с
 Информатика: учеб. для студентов высш. учеб. заведений, обучающихся по естеств.-науч. направлениям и специальностям / Виталий Адольфович Каймин. - 4-е изд. - М. : ИНФРА-М, 20с.

2.  Я. Математика и информатика : учеб. пособие : учебник / ; Урал. гос. ун-т. - 3-е изд., доп. и перераб. - М. : ИНФРА-М, 20с.
Я. Математика и информатика: учеб. пособие для студентов вузов/ Владимир Яковлевич Турецкий. - 3-е изд., перераб. и доп. - М. : ИНФРА-М, 20с.
Я. Математика и информатика: учеб. пособ. для студентов вузов/ Владимир Яковлевич Турецкий. - М. : Инфра-М, 20с.

б) дополнительная литература:

1.  Информатика. Базовый курс: учеб. пособие / под ред. . - 2-е изд. - М. ; СПб. [и др.] : Питер, 20с.

2.  Дж. Информатика: учеб.-метод. пособие / Д. Дж. Луенбергер ; пер. с англ. под ред. . - М. :Техносфера, 20с.

3.  В. Теоретическая информатика: учеб. пособие / , ; Рос. гос. ун-т им. Иммануила Канта. - Калининград : Изд-во РГУ им. И. Канта, 2007. - XXVI, 501 с.

4.  В. Математические основы информатики: метод. пособие / , , . - М. : БИНОМ. Лаб. знаний, 20с.

5.  Теоретическая информатика и её основания: в 2 т. / . - М. : ФИЗМАТЛИТ, 20с.

в) программное обеспечение и Интернет-ресурсы:

Не требуется

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

Мультимедийная лекционная аудитория (наличие проектора и проекционного экрана).

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки «Разработка программно-информационных систем»

Автор: .

Программа одобрена на заседании кафедры Математической кибернетики и компьютерных наук от «22» февраля 2011 г., протокол

Зав. кафедрой МКиКН .

Декан факультет .