Рабочая программа по дисциплине «Теоретические основы информатики»

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Уральский государственный педагогический университет»

Институт информатики и информационных технологий

Кафедра новых информационных технологий в образовании

РАБОЧАЯ ПРОГРАММА

по дисциплине «Теоретические основы информатики»

для специальности 050202.65 Информатика

по циклу ДПП. Ф.08

Заочная форма обучения Курс – 5 Семестр – 9 Объём в часах всего – 144 в т. ч.: лекции – 12 практические занятия – лабораторные занятия – 24 самостоятельная работа – 108 Экзамен – 9 семестр

Екатеринбург – 2012

Рабочая программа по дисциплине «Теоретические основы информатики»

Уральский государственный педагогический университет.

Екатеринбург, 20с.

Составители:

доктор педагогических наук, профессор

Рабочая программа обсуждена на заседании кафедры НИТО

Протокол № 1 от 23 сентября 2012 г. Зав. кафедрой

I. Введение

Цели и задачи дисциплины

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

В процессе освоения дисциплины решаются задачи:

изучить:

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

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

  энтропийный подход к определению количества информации (теория К. Шеннона);

  элементы теории первичного кодирования дискретной информации;

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

  элементы теории помехоустойчивого кодирования;

  элементы теории конечных автоматов;

  элементы теории распознавания образов;

  математические аспекты кибернетики;

  элементы теории систем;

сформировать умения решения задач, связанных:

  с применением закономерностей теории информации;

  с построением помехоустойчивых кодов;

  с программированием машин Поста и Тьюринга;

  с построением комбинационных схем и конечных автоматов;

  с решением и моделированием задач кибернетики.

Специфика содержания программы

Курс «Теоретические основы информатики» занимает важное место в плане подготовки специалистов в области информатики, поскольку, с одной стороны, его можно отнести к категории мировоззренческих, поскольку он призван сформировать представление об единой информационной картине мира, значении информации и информационных процессов в жизни современного общества, а также о существующих научных методах их описания. С другой стороны, он служит основой для освоения других разделов информатики, программирования и информационных технологий. Курс носит пропедевтический характер по отношению к другим дисциплинам: теория алгоритмов, основы искусственного интеллекта, компьютерное моделирование и др. Ввиду большой значимости курса и относительно небольшим объемом учебных часов, отводимых на его освоение (72 акад. ч.) акценты в программе делаются на содержательных (смысловых) аспектах и в меньшей степени на математической и доказательной сторонах.

Формы и методы реализации практического
компонента дисциплины

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

  Формы обучения: очная, заочная.

  Форма обучения по количеству учащихся: групповая.

  По месту обучения: аудиторная форма обучения; самостоятельная аудиторная работа (не менее 50 % учебной нагрузки для очной формы обучения и не менее 80% для заочной формы).

  По длительности обучения: спаренные занятия 90 мин (2 ´ 45 мин).

  По организационной форме: лекция, лабораторная работа, контрольные занятия с применением компьютерного контроля, самостоятельная работа.

Методы обучения:

При проведении лекционных занятий:

  словесные методы – лекция, объяснение;

  наглядные методы – демонстрация (компьютерные демонстрации и презентации), в т. ч. с использованием ресурсов сети Internet.

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

  когнитивные: методы наук – информационное моделирование; методы учебных предметов – метод системно-объектного подхода к изучению программного обеспечения и др.; метапредметные методы – сравнения, аналогии, смыслового видения, прогнозирования и др.;

  креативные методы: проблемный, дискуссионный, моделирования;

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

Рекомендации по формам контроля
и организации самостоятельной работы

Формы контроля:

  текущего: электронные отчеты по практическим занятиям и самостоятельной работе;

  итогового: компьютерный тестовый контроль теоретических знаний.

Организация самостоятельной работы:

  условия проведения СР: наличие компьютера с необходимым программным обеспечением; наличие (доступ) к УМК по дисциплине;

  учебно-методические материалы на электронных носителях: тексты лекций, электронные учебные курсы, комплекс лабораторных работ, средства компьютерного контроля и самоконтроля;

  организация информационного взаимодействия преподаватель-студент: в аудитории, посредством сети Internet (e-mail, форум);

II. Учебно-тематический план

№ разд	Наименование темы, раздела	Всего трудоёмкость	Аудиторные часы	Самост. работа
Всего	Лекции	Практики	Лаборат. зан.
0	Введение	2	1	1	–	–	1
1	Теория информации	20	4	2	–	2	16
2	Кодирование информации	18	6	2	–	4	12
3	Передача и хранение информации	18	6	2	–	4	12
4	Помехоустойчивое кодирование	18	5	1	–	4	13
5	Элементы теории автоматов	26	5	1	–	4	21
6	Системы и модели	8	1	1	–	–	7
7	Элементы теории распознавания	16	5	1	–	4	11
8	Математическая кибернетика	16	3	1	–	2	13
ИТОГО:	144	36	12	–	24	108

III. Содержание дисциплины

Краткое содержание дисциплины

Введение. Информатика как наука и как вид практической деятельности. Место информатики в системе наук. Предмет, задачи, структура курсов области «Информатика» в педвузе; роль и значение курса «Теоретическая информатика».

1. Теория информации. Исходные понятия информатики: сообщение, информация, источник и приемник информации. Сигнал и его информационные параметры. Формы представления информации (непрерывная, дискретная). Преобразование сообщений. Теорема отсчетов. Возможности обработки информации. Универсальность дискретного представления информации. Знак, алфавит.

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

Понятие энтропии. Свойства энтропии. Условная энтропия. Энтропия и информация. Формулы Хартли и Шеннона. Измерение количества информации. Информация и алфавит.

2. Кодирование информации. Кодирование символьной информации. Понятие кода, кодирования. Избыточность кода. Первая теорема Шеннона. Постановка задачи кодирования. Алфавитное неравномерное кодирование. Оптимальные коды (код Хаффмана). Равномерное алфавитное кодирование. Байтовый код. Стандарты кодов. Код Морзе. Блочное кодирование.

* Представление чисел в компьютере. Системы счисления. Преобразование целых и вещественных чисел. Экономичность системы счисления. Преобразование нормализованных чисел. Кодирование и обработка в компьютере целых и вещественных чисел[1].

3. Передача и хранение информации. Общая схема передачи информации. Канал связи. Характеристики канала: ширина полосы пропускания, пропускная способность, скорость передачи. Влияние шумов на пропускную способность канала. Вторая теорема Шеннона. Дискретные каналы (симметричный, асимметричный, со стиранием). Обеспечение надежности передачи.

Последовательный и параллельный способ передачи информации. Связь компьютеров по телефонным линиям.

(*) Хранение информации. Классификация данных, уровни представления данных: концептуальный, логический, физический. Представление элементарных данных в ОЗУ (целые и вещественные числа, символы, логические данные). Классификация структур данных; примеры структур: массив, стек (очередь), множество, дерево, запись. Организация структур данных в ОЗУ. Иерархия структур данных на внешних носителях. Организация доступа к данным: произвольный, последовательный, прямой.

4. Помехоустойчивое кодирование. Общие принципы помехоустойчивого кодирования. Классификация корректирующих кодов. Избыточность помехоустойчивого кода. Принципы обнаружения и исправления ошибок в систематических кодах. Понятие кодового вектора, кодового расстояния. Граница Хемминга.

Построение систематического кода. Таблица проверок. Кодер и декодер систематического кода. (*) Канонический систематический код. Код Хемминга.

5. Элементы теории автоматов. Понятие автомата. Классификация автоматов. Описание автомата. Автоматные функции.

Дискретные устройства без памяти (комбинационные схемы). Логические элементы. Базис элементов. Решение прямой и обратной задачи.

Машины Поста и Тьюринга как автоматы с бесконечной памятью. Решение алгоритмических задач с использованием машин Поста и Тьюринга.

Понятие конечного автомата. Способы описания конечного автомата (табличный, диаграмма Мура). Виды элементов памяти конечных автоматов (задержка, триггер, двоичный счетчик). Понятие о полноте элементов. Правила построения схем. Решение прямой и обратной задачи. (*) Эквивалентные автоматы.

6. Системы и модели. Объект, его свойства, методы. Понятие системы. Классификация систем. Понятие модели. Классификация моделей. Математическая модель. Свойства отношений между элементами математической модели: рефлексивность, симметричность, транзитивность.

Представление об объектно-ориентированном подходе. Реализация объектно-ориентированного подхода в современном пользовательском интерфейсе и программном обеспечении компьютера.

(*) Понятие формальной системы. Свойства формальной системы. Значение формализации. Этапы алгоритмического решения задачи.

7. Элементы теории распознавания. Общая характеристика задач распознавания образов и их типы. Математическая теория распознавания образов.

8. Математическая кибернетика. Информация и управление. Кибернетический подход к решению задач управления. Схемы управления (разомкнутая, с обратной связью). Автоматическое управление. Коллективное поведение автоматов. Математические аспекты кибернетики. (*) Нейрокибернетика.

Вопросы для контроля после тем (разделов) дисциплины

1. Теория информации

1)  Исходные понятия информатики: сообщение, информация, источник и приемник информации.

2)  Сигнал и его информационные параметры.

3)  Виды информации (непрерывная, дискретная).

4)  Преобразование форм представления информации

5)  Универсальность дискретного представления информации.

6)  Понятие энтропии. Свойства энтропии.

7)  Энтропия и информация. Статистическое определение информации.

8)  Информация и алфавит. Формула Шеннона.

2. Кодирование информации

1)  Математическая постановка задачи кодирования.

2)  Неравномерное алфавитное кодирование с разделителем кодов.

3)  Оптимальные коды (Хаффмана, Шеннона-Фано).

4)  Равномерное двоичное кодирование. Байт. Стандарты компьютерных кодов.

5)  Системы счисления. Позиционные системы счисления.

6)  Перевод целых и дробных чисел в различные системы счисления.

7)  Системы счисления, используемые в компьютере. Перевод целых и дробных чисел между системами счисления с основанием 2 – 8 – 16.

8)  Представление целых чисел в компьютере. Сложение и умножение целых чисел.

9)  Дополнительный код двоичного числа. Вычитание двоичных целых чисел.

10)  Нормализованная форма вещественного числа. Представление вещественных чисел в компьютере.

11)  Сложение и умножение нормализованных двоичных чисел. Влияние ограниченной разрядности чисел на точность вычислений. Понятие переполнения и машинного нуля.

3. Передача и хранение информации

1)  Понятие канала и линии связи. Характеристики канала связи: ширина пропускания, пропускная способность, скорость передачи.

2)  Влияние шумов на пропускную способность канала.

3)  Параллельная передача данных в компьютерных линиях.

4)  Последовательная передача. Модемная связь.

5)  Постановка задачи хранения информации. Хранение элементарных данных в памяти компьютера. Идентификаторы.

6)  Структуры данных. Классификация и примеры структур данных. Размещение структур данных в ОЗУ: последовательные и связанные списки.

7)  Размещение данных на внешних носителях. Понятия физической записи, файла, каталога (папки), структур каталогов. Блок, кластер.

4. Помехоустойчивое кодирование

1)  Общие принципы помехоустойчивого кодирования. Классификация корректирующих кодов. Избыточность помехоустойчивого кода.

2)  Принципы обнаружения и исправления ошибок в систематических кодах.

3)  Понятие кодового вектора, кодового расстояния. Граница Хемминга.

4)  Порядок построения систематического кода. Таблица проверок.

5)  Кодер и декодер систематического кода.

6)  Построение систематического кода по заданной производящей матрице или схеме кодера.

7)  Построение кода Хемминга.

5. Элементы теории автоматов

1)  Понятие автомата. Описание автомата. Автоматные функции.

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

3)  Решение алгоритмических задач с помощью машин Поста и Тьюринга.

4)  Конечные автоматы. Способы описания конечных автоматов (табличный, с помощью диаграмм).

5)  Виды элементов памяти конечных автоматов; их диаграммы.

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

6. Системы и модели

1)  Понятие модели. Классификация моделей. Особенности информационных моделей.

2)  Понятие объекта. Понятие системы. Классификация систем.

3)  Значение формализации. Порядок решения задач с применением компьютера.

7. Элементы теории распознавания

1)  Постановка задачи распознавания образов (признаки объекта, отношения, отнесение к классу).

2)  Связь задач распознавания образов с исследованием операций, искусственным интеллектом, теорией управления.

8. Математическая кибернетика

1)  Информация и управление. Схемы управления (разомкнутая, с обратной связью).

2)  Управление и регулирование. Автоматическое регулирование.

3)  Автомат. Коллективное поведение автоматов.

4)  Нейрокибернетика. Персептрон. Нейрокомпьютер. Нейронные сети.

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

Итоговый контроль усвоения теории осуществляется посредством системы компьютерного тестирования Magistr 2000 (вопросы представлены в электронном формате контролирующей системы.

Содержание лабораторного практикума

№ разд	№ ЛР	Тематика лабораторных работ
1	Теория информации (4 уч. ч.)
1.1	Расчет энтропии, количества информации.
1.2	Частотный анализ текста. Определение типа сообщения.
2	Кодирование информации (4 уч. ч.)
2.1	Построение неравномерных кодов.
2.2	Построение равномерных кодов.
3	Передача и хранение информации (6 уч. ч.)
3.1	Расчет характеристик передачи информации
3.2	Исследование дискретного симметричного канала связи.
3.3	Исследование дискретного канала со стиранием.
4	Помехоустойчивое кодирование (6 уч. ч.)
4.1	Расчет характеристик помехоустойчивого кода
4.2	Построение систематического кода.
4.3	Построение канонического систематического кода.
5	Элементы теории автоматов (6 уч. ч.)
	5.1	Построение комбинационных схем
	5.2	Решение задач с применением машины Поста
	5.3	Решение задач с применением машины Тьюринга
	5.3	Построение конечных автоматов.
7	Элементы теории распознавания (4 уч. ч.)
	7.1	Постановка и решение задач теории распознавания образов.
	7.2	Экспериментирование с программой распознавания образов.
8	Математическая кибернетика (4 уч. ч.)
	8.1	Решение задач на расчет информационных потоков при управлении.
	8.2	Работа с программным эмулятором коллективного поведения автоматов.

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

Темы, вынесенные на самостоятельное изучение:

1.  Представление чисел в компьютере. Системы счисления.

2.  Хранение информации.

3.  Построение канонического систематического кода.

4.  Эквивалентные автоматы.

5.  Понятие формальной системы.

6.  Нейрокибернетика.

Темы контрольных работ

Предусматривается заключительная (итоговая) контрольная работа, включающая следующие типы задач:

·  вычисление энтропии или количества информации;

·  первичное кодирование символьной информации;

·  помехоустойчивое кодирование;

·  конечные автоматы.

Вопросы для зачета

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

Зачет по дисциплине выставляется по совокупности 3-х позиций:

·  сдан на положительную оценку компьютерный тест по теоретическому материалу (в объеме рабочей программы дисциплины);

·  представлены и зачтены отчеты по всем лабораторным работам;

·  зачтена итоговая контрольная работа по решению задач.

Для получения зачет должны быть успешно зачтены все три составляющие (по системе «зачет-незачет»).

Примерные темы выпускных квалификационных работ

1.  Электронный учебно-методический комплекс по разделу «Теоретическая информатика» для школьников.

2.  Программный эмулятор обработки двоичных целых чисел в компьютере.

3.  Программный эмулятор обработки двоичных дробных чисел в компьютере.

4.  Программный эмулятор обработки двоичных нормализованных чисел в компьютере.

5.  Программный эмулятор кодера кода Хаффмана (Шеннона-Фано).

6.  Программный эмулятор кодера-декодера систематического кода.

7.  Программный эмулятор матричного систематического кода.

8.  Программный эмулятор дискретных каналов связи.

9.  Система учебных заданий для освоения машины Поста (Тьюринга).

10.  Программный эмулятор распознавания образов знаков.

V. Требования к уровню подготовки выпускников,
обучающихся по данной программе

После освоения дисциплины «ИКТ в образовании»

студент должен знать:

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

·  энтропийный подход к определению количества информации в теории Шеннона;

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

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

·  подходы к построению помехоустойчивых кодов;

·  элементы теории автоматов (типизация, математическое описание, методы решения задач);

·  соотношение понятий модель-объект-система;

·  элементы теории распознавания образов;

·  элементы математической киберненики;

студент должен уметь:

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

·  производить статистический анализ текста с определением его типа (шенноновский, марковский);

·  строить первичные алфавитные двоичные коды;

·  строить помехоустойчивый систематический код;

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

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

·  использовать эмулятор машины Поста (Тьюринга) для решения алгоритмических задач.

VI. Учебно-методическое обеспечение дисциплины

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

Программное обеспечение

·  программный пакет MS Office - 2003 (XP, 2000);

·  программа распознавания текстов ABBYY FineReader 8.0;

·  инструментальная система компьютерного контроля Magister-2000 (v. 2.0);

·  программа NetSupport School (v.2.0 и выше)

·  программный эмулятор машин Поста, Тьюринга ALGO 2000.

Техническое обеспечение

·  учебные мультимедиа-компьютеры;

·  локальная компьютерная сеть;

·  сканер;

·  проекционное оборудование (цифровой проектор, экран, переносной ПК).

Методическое обеспечение на электронных носителях

·  Стариченко, основы информатики [Электронный курс] : Электронное учебное пособие для студентов педвуза / ; Урал. гос. пед. ун-т. — Электрон. дан. и прогр. — Екатеринбург, 2005. — 1 CD. — Систем. требования : IBM PC, Windows XP (2000), Internet Explorer (v.5 и выше).

·  Стариченко, основы информатики [Электронный курс] : Электронный лабораторный практикум для студентов педвуза / ; Урал. гос. пед. ун-т. — Электрон. дан. и прогр. — Екатеринбург, 2006. — 1 CD. — Систем. требования : IBM PC, Windows XP (2000), Internet Explorer (v.5 и выше), MS Office XP (2003).

·  Стариченко, основы информатики [Электронный курс] : Библиотека тестов для системы Magister-2000 / ; Урал. гос. пед. ун-т. — Электрон. дан. и прогр. — Екатеринбург, 2006. — 1 CD. — Систем. требования : IBM PC, Windows XP (2000), Magister-2000.

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

1.  Могилев, : Учеб. пособие для студ. пед. вузов / , , . – М. : ИЦ “Академия”, 1999. – 816 с.

2.  Стариченко, основы информатики: Учеб. пособие для студ. вузов / . – 2-е изд., испр. и доп. – М : Горячая линия – Телеком, 2003. – 312 с.

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

1.  Бауэр, Ф. Информатика. Вводный курс / Ф. Бауэр, Г. Гооз. М. : Мир, 1976. – 484 с.

2.  Бриллюэн, Л. Наука и теория информации / Л. Бриллюэн. – М. : ГИФМЛ, 1960.  – 392 с.

3.  Глушков, безбумажной информатики / . – М. : Наука, 1987. – 552 с.

4.  Стратонович, информации / – М. : Советское радио, 1975. – 424с.

5.  Успенский, Поста / . – М. : Наука, 1988. – 96 с.

6.  Файнстейн, А. Основы теории информации / А. Файнстейн. – М.: ИЛ, 1960.  – 233 с.

7.  Фомин, счисления / . – М. : Наука, 1987. – 48 с.

8.  Шеннон, К. Математическая теория связи. В кн.: Работы по теории информации и кибернетике / К. Шеннон. – М. : ИЛ, 1963. С. 243–332.

9.  Яглом, и информация / . . – М. : Наука, 1973. – 511 с.

VII. Выходные данные коллектива авторов программы

доктор педагогических наук, профессор

проректор по информатизации, зав. кафедрой НИТО УрГПУ

р. ,

[1] Материал, отмеченный (*), выносится на самостоятельное освоение.