В философии атрибутивная концепция трактует информацию как

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ

 

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

 

«5В011100 - Информатика»

 

Алматы, 2016

Учебно-методический комплекс дисциплины составлен на основании:

§ Государственного общеобязательного стандарта высшего профессионального образования по специальности «5В011100 - Информатика»;

§ Рабочего учебного плана по специальности «5В011100 - Информатика», утвержденного «___» ______________ 2016 г.

 

 

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

Старший преподаватель                                                        Киселёва Е.А.

 

Заведующий кафедрой                                                     Бидайбеков Е.Ы.

 

«____» _________________ 2016 г.

 

 

 

 

Опись содержания учебно-методического комплекса дисциплины

 

1. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА.. 5

2. СИЛЛАБУС ДИСЦИПЛИНЫ ДЛЯ СТУДЕНТОВ.. 18

3. КАРТА УЧЕБНО-МЕТОДИЧЕСКОЙ ОБЕСПЕЧЕННОСТИ.. 20

4. ТЕЗИСЫ ЛЕКЦИЙ.. 22

Лекция 1. Предмет и задачи информатики. 22

Лекция 2. Информация и её свойства. 23

Лекция 3. Абстрактные автоматы.. 25

Лекция 4. Представление информации в цифровых автоматах. 27

Лекция 5. Выполнение арифметических операций на двоичных сумматорах. 30

Лекция 6. Основные понятия алгебры логики. 32

Лекция 7. Основные понятия теории алгоритмов. 35

Лекция 8. Анализ эффективности и сложности алгоритмов. 38

Лекция 9. Алгоритмы вида «разделяй и властвуй». 40

Лекция 10. Алгоритмы поиска и выборки. 43

Лекция 11. Простые алгоритмы сортировок. 44

Лекция 12. Усовершенствованные алгоритмы сортировок. 45

Лекция 13. Основы информационного моделирования. 47

Лекция 14. Информационные системы.. 48

5. ПЛАНЫ СЕМИНАРСКИХ, ПРАКТИЧЕСКИХ, ЛАБОРАТОРНЫХ И СТУДИЙНЫХ  ЗАНЯТИЙ 65

6. РУКОВОДСТВО ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ И СТУДИЙНЫХ РАБОТ. 66

Лабораторная работа № 1. Измерение информации. 66

Лабораторная работа № 2. Кодирование текстовой, звуковой, графической информации. 68

Лабораторная работа № 3. Абстрактные автоматы. Машина Поста. 70

Лабораторная работа № 4. Абстрактные автоматы. Машина Тьюринга. 72

Лабораторная работа № 5. Представление информации в цифровых автоматах. Системы счисления 74

Лабораторная работа № 6. Выполнение арифметических операций на двоичных сумматорах. 75

Лабораторная работа № 7. Основные понятия алгебры логики. 77

Лабораторная работа № 8. Способы описания алгоритмов. 79

Лабораторная работа № 9. Рекурсивные алгоритмы.. 81

Лабораторная работа № 10. Алгоритмы поиска в последовательности. 83

Лабораторная работа № 11. Алгоритмы сортировок методами прямого включения и прямого выбора. 86

Лабораторная работа № 12. Алгоритм сортировки методом прямого обмена (пузырьковая и шейкерная сортировки) 88

Лабораторная работа № 13. Алгоритм сортировки методом Шелла. 90

Лабораторная работа № 14. Алгоритм сортировки методом дерева. 91

7. МАТЕРИАЛЫ ДЛЯ ОРГАНИЗАЦИИ И УПРАВЛЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТОЙ ОБУЧАЮЩИХСЯ: 95

Задания для СРСП.. 95

Задания для СРС (семестровое задание) 105

8. МАТЕРИАЛЫ ДЛЯ МОНИТОРИНГА И КОНТРОЛЯ ОБРАЗОВАННОСТИ ОБУЧАЮЩИХСЯ (УРОВНЯ СФОРМИРОВАННОСТИ ПРЕДМЕТНЫХ КОМПЕТЕНЦИЙ): 108

Экзаменационные вопросы.. 108

Тестовые задания. 108

Задания для текущего, рубежного и промежуточного контроля. 116

9.МЕТОДИЧЕСКИЕ РАЗРАБОТКИ (РЕКОМЕНДАЦИИ) 122

10. ОФИЦИАЛЬНО ИЗДАННЫЕ ПРЕПОДАВАТЕЛЯМИ УЧЕБНЫЕ И УЧЕБНО-МЕТОДИЧЕСКИЕ ПОСОБИЯ (ПРИ УСЛОВИИ ПУБЛИКАЦИИ) 122

11. ПЕРЕЧЕНЬ: 122

12. УЧЕБНАЯ ЛИТЕРАТУРА И/ИЛИ МАТЕРИАЛЫ НА ЭЛЕКТРОННЫХ НОСИТЕЛЯХ.. 123

 

 

 

1. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

дисциплины «Теоретические основы информатики»
для специальности «5В011100 - Информатика»

 

Форма обучения	Заочная СО
Кафедра	ИИО
Курс	2
Семестр	3
Количество кредитов	3
Всего часов	135
Лекций	15
Практические (сем., студийные) занятия	-
Лабораторные занятия	30
СРСП	45
СРС	45
Экзамен	3 семестр

 

Рабочая учебная программа составлена на основании:

§ Государственного общеобязательного стандарта высшего профессионального образования по специальности 5B011100-«Информатика»;

§ Рабочего учебного плана по специальности   5B011100-«Информатика», утвержденного «__»______________ 2016г.

 

 

Рабочая учебная программа дисциплины «Теоретические основы информатики» составлена ст. преп. Киселёвой Е.А. и обсуждена на заседании кафедры ИИО «___» _____________2016 г., протокол №_________

 

Киселева Е.А. _______________

 

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

Бидайбеков Е.Ы. ______________

 

 

Рабочая учебная программа рекомендована Советом института математики, физики и информатики «___»_____________2016г., протокол №_________.

 

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

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

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

• формирование представлений об основных направлениях теоретической информатики;

• формирование знаний о научных принципах функционирования ЭВМ, о понятии алгоритма и способах его оценки;

• формирование умений использования теоретических знаний на практике;

• подготовка к профессиональной деятельности

В результате изучения дисциплины «Теоретические основы информатики» студент должен знать:

• о проблемах и задачах теоретической информатики и об основных принципах и этапах информационных процессов;

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

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

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

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

 

ПЕРЕЧЕНЬ ПРЕРЕКВИЗИТОВ
 

№	Наименование дисциплин, их разделы (темы)
1.	Дискретная математика
2.	Информатика и информационные технологии
3.	Программирование 1

 

ПЕРЕЧЕНЬ ПОСТРЕКВИЗИТОВ

 

№	Наименование дисциплин
1.	Программирование 3
2.	Численные методы
3.	Системное программирование

 

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

2.1.Лекционный курс

№ темы	Наименование тем лекций	Содержание тем	Объем в часах	Неделя семестра
Тема 1.	Предмет и задачи информатики. Теоретическая информатика	Появление и развитие информатики. История развития вычислительной техники. Появление информатики как науки. Структура информатики. Направления научных исследований (теоретическая информатика, средства информатизации, информационные технологии, социальная информатика). Информатика как отрасль народного хозяйства, фундаментальная наука и прикладная дисциплина. Цели и задачи информатики. Направления исследований теоретической информатики	1	1
Тема 2.	Информация и её свойства	Информация как философская категория. Преобразование информации. Сообщение – носитель информации. Передача сообщений с помощью сигналов. Источник информации, приёмник информации и канал передачи. Дискретизация сообщений. Формы представления информации. Статическая. Динамическая. Кодирование. Декодирование. Измерение информации. Структурная мера (геометрическая, комбинаторная, аддитивная (мера Хартли)). Статистическая мера (понятие энтропии, свойства энтропии). Семантическая мера (содержательность, логическое количество, целесообразность и существенность информации). Передача информации. По каналу без помех. По каналу с помехами	1	2
Тема 3.	Автомат как основной элемент информационных систем	ЭВМ – программно-управляемый цифровой автомат. Машина Тьюринга. Машина Поста	2	3-4
Тема 4.	Представление информации в цифровых автоматах. Системы счисления	Выбор системы счисления для представления информации. Перевод числовой информации из одной позиционной системы в другую. Формы представления числовой информации. Представление чисел с фиксированной запятой (точкой). Представление чисел в форме с плавающей запятой. Представление отрицательных чисел. Погрешности представления числовой информации	1	5
Тема 5.	Выполнение арифметических операций на двоичных сумматорах	Двоичные сумматоры прямого, обратного и дополнительного кода. Реализация сложения, вычитания, умножения и деления на двоичных сумматорах	1	6
Тема 6.	Основные понятия алгебры логики	Высказывание. Логическая (булева) переменная. Логическая функция. Свойства элементарных функций алгебры логики.	1	7
Тема 7.	Понятие алгоритма. Основные понятия теории алгоритмов	Уточнение понятия «алгоритм» с помощью машин Тьюринга и Поста. Нормальные алгоритмы Маркова. Рекурсивные алгоритмы по Маккарти. Алгоритмически неразрешимые задачи	1	8
Тема 8.	Анализ эффективности и сложности алгоритмов	Понятие сложности алгоритма. Асимптотическая сложность алгоритма. Сложность задачи. Верхние, нижние и средние оценки сложности. Асимптотическая временная сложность алгоритма. Сравнение эффективности различных алгоритмов	1	9
Тема 9.	Рекурсивные алгоритмы	Алгоритмы вида «разделяй и властвуй». Эффективность рекурсивного алгоритма. Метод турниров	1	10
Тема 10.	Алгоритмы поиска и выборки	Последовательный поиск. Двоичный поиск. Выборка	1	11
Тема 11.	Простые алгоритмы сортировок	Сортировка вставками. Пузырьковая сортировка. Сортировка Шелла.	1	12
Тема 12.	Усовершенствованные алгоритмы сортировок	Корневая сортировка. Пирамидальная сортировка. Сортировка слиянием. Быстрая сортировка. Внешняя многофазная сортировка	1	13
Тема 13.	Информационное моделирование	Понятие об информационном моделировании. Основные этапы построения моделей. Формализация. Математическое моделирование и вычислительный эксперимент	1	14
Тема 14.	Информационные системы	Понятие ИС. Этапы развития ИС. Структура и классификация ИС.	1	15
…		Всего:	15

 

2.2. Лабораторные, студийные занятия

№№ п.п.	Наименование и содержание лабораторных занятий	Оборудова ние для проведения лаб.раб.	Объем в часах	Неделя семестра
1.	Измерение информации	видеопроектор, комплекс программ-эмулчторов	2	1
2.	Кодирование текстовой, звуковой, графической информации		2	2
3.	Абстрактные автоматы. Машина Поста		2	3
4.	Абстрактные автоматы. Машина Тьюринга		2	4
5.	Представление информации в цифровых автоматах. Системы счисления		2	5
6.	Выполнение арифметических операций на двоичных сумматорах		2	6
7.	Основные понятия алгебры логики		2	7
8.	Способы описания алгоритмов		2	8
9.	Рекурсивные алгоритмы		2	9
10.	Алгоритмы поиска в последовательности		2	10
11.	Алгоритмы сортировок методами прямого включения и прямого выбора		2	11
12.	Алгоритм сортировки методом прямого обмена (пузырьковая и шейкерная сортировки)		2	12
13.	Алгоритм сортировки методом Шелла		2	13
14.	Алгоритм сортировки методом дерева		2	14
15.	Информационное моделирование		2	15
Всего:			30

 

 

2.3. Самостоятельная работа студентов под руководством преподавателя

№№ п.п.	Наименование тем и содержание заданий для СРСП	Формы проведения	Объем в часах	Неделя семестра
1.	Представление информации. Кодирование информации. Количество Информации.	Индивидуальные и групповые консультации по решению индивидуальных задач	3	1
2.	Абстрактные машины Поста и Тьюринга		4	2-3
3.	Системы счисления		3	4
4.	Формы представления числовой информации		3	5
5.	Основные понятия алгебры логики		3	6
6.	Основы теории алгоритмов		3	7
7.	Способы описания алгоритмов		3	8
8.	Рекурсивные алгоритмы.		3	9
9.	Алгоритмы поиска и выборки		3	10
10.	Сортировка с помощью прямого включения		3	11
11.	Сортировка с помощью прямого выбора		3	12
12.	Пузырьковая сортировка. Шейкерная сортировка		4	13
13.	Сортировка Шелла		3	14
14.	Сортировка деревом (пирамидальная сортировка)		4	15
Всего:			45

 

 

2.4. Самостоятельная работа студентов

№№ п.п.	Наименование тем и содержание заданий для СРС	Формы контроля	Объем в часах	Неделя семестра
	Информация как философская категория	сдача индивидуальных задач	3	1
	Преобразование информации		3	2
	ЭВМ – программно-управляемый цифровой автомат		3	3
	Погрешности представления числовой информации в ЭВМ		4	4
	Алгоритмически неразрешимые задачи		4	5-6
	Сравнение эффективности различных алгоритмов		4	7-8
	Алгоритмы вида «разделяй и властвуй»		4	9
	Метод турниров		4	10
	Алгоритм двоичного поиска		4	11
	Быстрая сортировка. Внешняя многофазная сортировка		4	12
	Формализация как этап информационного моделирования		4	13-14
	Компьютерные семантические системы		4	15
Всего:			45

 

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

 

3.1.Список рекомендуемых источников:

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

1. Могилев А.В. и др. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.
2. Информатика: Учебник. – 3-е перераб. изд. /Под. ред. проф. Н.В. Макаровой. – М.: Финансы и статистика, 2001. – 768 с.: ил.
3. Дж. Макконнелл. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002. – 304 с.

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

1. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Пер. с нем. – М.: Мир, 1990. – 336 с., ил.

1. Савельев А.Я. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001 – 328 с., ил. (Сер. Информатика в техническом университете)
2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – 2-е изд., испр. – СПб.: Невский Диалект, 2001. – 352 с.: ил.
3. Бурин Е.А. Введение в основы информатики и вычислительной техники: Курс лекций. – Алма-Ата: Мектеп, 1988. – 144 с.
4. А.Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

Программные средства

Комплекс программ-эмуляторов

Программные педагогические средства

Cистема программ "1С:Образование 3.0". Вычислительная математика и программирование

 

3.2. Вопросы для подготовки к экзамену

Таблица значений какой логической функции приведена ниже

x1 x2	00	01	10	11
f	0	1	1	0

A)   (конъюнкция)

B)   (дизъюнкция)

C)   (импликация)

D)   (равнозначность)

E) &   (сложение по модулю 2)

18. *****

Выбирается элемент с наименьшим ключом. Он меняется местами с первым элементом а1. Затем этот процесс повторяется с оставшимися n –1 элементами, n –2 элементами, и т.д. до тех пор, пока не останется один, самый большой элемент.

A) сортировка с помощью прямого включения;

B) &сортировка с помощью прямого выбора;

C) пузырьковая сортировка;

D) шейкерная сортировка;

E) сортировка Шелла.

22. *****

Недели

Аудиторные занятия

Вид задания

Всего (ч.)

Лекц (ч.) Лаб. (ч.) СРСП (ч.) СРС (ч) 1. Предмет и задачи информатики. Теоретическая информатика   1 2 3 3 9 2. Информация и её свойства   1 2 3 3 9 3. Автомат как основной элемент информационных систем   2 4 3 3 12 4. Представление информации в цифровых автоматах. Системы счисления   1 2 4 4 11 5. Выполнение арифметических операций на двоичных сумматорах   1 2 4 4 11 6. Основные понятия алгебры логики   1 2 4 4 11 7. Понятие алгоритма. Основные понятия теории алгоритмов   1 2 3 3 9 8. Анализ эффективности и сложности алгоритмов   1 2 3 3 9 9. Алгоритмы поиска и выборки   1 2 3 3 9 10. Простые алгоритмы сортировок   1 2 3 3 9 11. Усовершенствованные алгоритмы сортировок   1 2 3 3 9 12. Рекурсивные алгоритмы   1 2 3 3 9 13. Информационное моделирование   1 2 3 3 9 14. Информационные системы   1 2 3 3 9       15 30 45 45 135

Литература для изучения

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

1. Могилев А.В. и др. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.
2. Информатика: Учебник. – 3-е перераб. изд. /Под. ред. проф. Н.В. Макаровой. – М.: Финансы и статистика, 2001. – 768 с.: ил.
3. Дж. Макконнелл. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002. – 304 с.

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

6. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Пер. с нем. – М.: Мир, 1990. – 336 с., ил.

1. Савельев А.Я. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001 – 328 с., ил. (Сер. Информатика в техническом университете)
2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – 2-е изд., испр. – СПб.: Невский Диалект, 2001. – 352 с.: ил.
3. Бурин Е.А. Введение в основы информатики и вычислительной техники: Курс лекций. – Алма-Ата: Мектеп, 1988. – 144 с.
4. А.Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

Программные средства

Комплекс программ-эмуляторов

Программные педагогические средства

Система программ "1С:Образование 3.0". Вычислительная математика и программирование

 

Критерии оценки

№	Вид работы	Оценка (max балл)	Количество	Сумма
	Коллоквиум (лек)	40	1	40
	Актив. на зан. (лаб)	2	10	20
	Индив. задания (лаб)	20	5	100
	Семестровый проект	40	1	40
	Экзамен	100	1	100
	Итого	((I+II)/2)*0,6+Экз*0,4

КАРТА УЧЕБНО-МЕТОДИЧЕСКОЙ ОБЕСПЕЧЕННОСТИ

 

Специальность 5В011100 – Информатика,         дисциплина «Теоретические основы инфоматики»

                                             (шифр)                 (наименование специальности)

 

№	Изучаемый раздел	Основная литература (автор, наименование, год издания, стр. по изучаемому разделу)	Дополнительная литература и Интернет источники	Прочие ресурсы в случае необходимости (программное обеспечение, презентации, нагл.пособия и др.)
1.	Информация и её свойства	Могилев А.В. и др. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.	Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2-х ч. Пер. с нем. – М.: Мир, 1990. – 336 с., ил.	Комплекс программ-эмуляторов и слайд-лекций
2.	Автомат как основной элемент информационных систем	Могилев А.В. и др. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.	Савельев А.Я. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001 – 328 с., ил.	Комплекс программ-эмуляторов и слайд -лекций
3.	Основные понятия алгебры логики	Могилев А.В. и др. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.	Савельев А.Я. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001 – 328 с., ил	Комплекс программ-эмуляторов и слайд -лекций
4.	Понятие алгоритма. Основные понятия теории алгоритмов	Дж. Макконнелл. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002. – 304 с.	Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – 2-е изд., испр. – СПб.: Невский Диалект, 2001. – 352 с.: ил.	Комплекс программ-эмуляторов и слайд-лекций
5.	Анализ эффективности и сложности алгоритмов	Дж. Макконнелл. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002. – 304 с.	А.Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.	Комплекс программ-эмуляторов и слайд -лекций
6.	Информационное моделирование	Информатика: Учебник. – 3-е перераб. изд. /Под. ред. проф. Н.В. Макаровой. – М.: Финансы и статистика, 2001. – 768 с.: ил.	Савельев А.Я. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001 – 328 с., ил.	Комплекс программ-эмуляторов и слайд -лекций

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

Ст.преп                                                    Киселёва Е.А.

 

Зав.кафедрой                                           Бидайбеков Е.Ы.

 

ТЕЗИСЫ ЛЕКЦИЙ

 

Лекция 1. Предмет и задачи информатики

(1 неделя, 1 час)

 

Термин информатика возник в 60-х гг. во Франции для названия области, занимающейся автоматизированной обработкой информации с помощью электронных вычислительных машин. Французский термин informatigue (информатика) образован путем слияния слов information (информация) и automatigue (автоматика) и означает "информационная автоматика или автоматизированная переработка информации". В англоязычных странах этому термину соответствует синоним computer science (наука о компьютерной технике).

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

Сегодня выделяют четыре самостоятельных и независимых направления, являющихся основой для соответствующей профессии:

• информатика (computer science);
• разработка аппаратных платформ (сomputer engineering);
• программная инженерия (software engineering);
• информационные системы (information systems).

Информатика как фундаментальная наука занимается разработкой методологии создания информационного обеспечения процессов управления любыми объектами на базе компьютерных информационных систем. Существует мнение, что одна из главных задач этой науки — выяснение, что такое информационные системы, какое место они занимают, какую должны иметь структуру, как функционируют, какие общие закономерности им свойственны. В Европе можно выделить следующие основные научные направления в области информатики: разработка сетевой структуры, компьютерно-интегрированные производства, экономическая и медицинская информатика, информатика социального страхования и окружающей среды, профессиональные информационные системы.

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

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

■ изучением закономерностей в информационных процессах (накопление, переработка, распространение);

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

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

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

Задачи информатики состоят в следующем:

■ исследование информационных процессов любой природы;

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

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

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

 

Лекция 2. Информация и её свойства

(2 неделя, 1 час)

 

ПЛАНЫ СЕМИНАРСКИХ, ПРАКТИЧЕСКИХ, ЛАБОРАТОРНЫХ И СТУДИЙНЫХ ЗАНЯТИЙ

 

№ недели	Название семинарских, практических, лабораторных и студийных занятий	Объем в часах
1	Измерение информации	2
2	Кодирование текстовой, звуковой, графической информации	2
3	Абстрактные автоматы. Машина Поста	2
4	Абстрактные автоматы. Машина Тьюринга	2
5	Представление информации в цифровых автоматах. Системы счисления	2
6	Выполнение арифметических операций на двоичных сумматорах	2
7	Основные понятия алгебры логики	2
8	Способы описания алгоритмов	2
9	Рекурсивные алгоритмы	2
10	Алгоритмы поиска в последовательности	2
11	Алгоритмы сортировок методами прямого включения и прямого выбора	2
12	Алгоритм сортировки методом прямого обмена (пузырьковая и шейкерная сортировки)	2
13	Алгоритм сортировки методом Шелла	2
14	Алгоритм сортировки методом дерева	2
15	Информационное моделирование	2
Всего:		30

 

Формула Шеннона

В общем случае, энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P: {p₀, p₁, …p_N-1}, т.е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье "Математическая теория связи".

В частном случае, когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов, т.е. H=F(N). В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. не 20 лет раньше.

Формула Шеннона имеет следующий вид:

(1)

Знак минус в формуле (1) не означает, что энтропия – отрицательная величина. Объясняется это тем, что p_i<=1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма , поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

интерпретируется как частное количество информации I_i, получаемое в случае реализации i-ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I₀, I₁, … I_N-1}.

Приведем пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ¾ - женщины, ¼ - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.

Если же априори известно, что мужчин и женщин в учреждении поровну (два равновероятных варианта), то при расчете по той же формуле мы должны получить неопределенность в 1 бит. Проверка этого предположения проведена в таблице 2.

Формула Хартли

Мы уже упоминали, что формула Хартли – частный случай формулы Шеннона для равновероятных альтернатив.

Подставив в формулу (1) вместо p_i его (в равновероятном случае не зависящее от i) значение , получим:

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

(2)

Из нее явно следует, что чем больше количество альтернатив (N), тем больше неопределенность (H). Эти величины связаны в формуле (2) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации – битам.

Задачи для решения

1. Априори известно, что шарик находится в одной из трех урн: А, В или С. Определите, сколько бит информации содержит сообщение о том, что он находится в урне В. Варианты: 1 бит, 1,58 бита, 2 бита, 2,25 бита.

2. Вероятность первого события составляет 0,5, а второго и третьего 0,25. Чему для такого распределения равна информационная энтропия. Варианты: 0,5 бита, 1 бит, 1,5 бита, 2 бита, 2,5 бита, 3 бита.

3. Вот список сотрудников некоторой организации:

Год рождения	Фамилия	Имя
1970	Иванова	Марина
1970	Иванова	Наталья
1970	Петрова	Татьяна
1970	Звягина	Ирина

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

a) Пожалуйста, позовите к телефону Иванову.

b) Меня интересует одна ваша сотрудница, она 1970 года рождения.

4. Какое из сообщений несет больше информации:

• В результате подбрасывания монеты (орел, решка) выпала решка.
• На светофоре (красный, желтый, зеленый) сейчас горит зеленый свет.
• В результате подбрасывания игральной кости (1, 2, 3, 4, 5, 6) выпало 3 очка.

5. Объем сообщения, содержащего 1024 символов, составил 1/512 часть Мбайта. Определить мощность алфавита.

 

 

Пример 1.

На ленте записано некоторое число, и головка обозревает одну из помеченных секций (любую). Составить программу прибавления единицы к этому числу. Ситуация иллюстрируется рисунком

Программа, обеспечивающая решение задачи, состоит из 4-х команд:

1.		3
		2
2.		1
3.	М	4
4.	стоп

 

Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо. Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустой ячейки – тогда по команде 3 в нее будет поставлена метка и по команде 4 машина оста