Вопросы к экзамену по дисциплине «Информатика»
Специальность 230100 «Информатика и вычислительная техника»
1 курс бакалавры
1. Понятие информации и ее качественные характеристики.
2. Принципы измерения информации. Энтропия. Свойства энтропии.
3. Условная вероятность и условная энтропия.
4. Взаимная информация. Потери информации от помех. Избыточность.
5. Информационные характеристики дискретных источников.
6. Цепи Маркова. Характеристики Марковских источников.
7. Теоремы об эффективном кодировании.
8. Метод Хаффмана и другие методы сжатия данных.
9. Спектры и энтропия непрерывных источников.
10. Информационные характеристики каналов связи.
11. Теоремы ШеннОна. Помехоустойчивое кодирование.
12. Представление целых чисел в ЭВМ. Сложение и вычитание.
13. Представление вещественных чисел. Умножение и деление.
14. Представление текста в ЭВМ. Кодировки и обработка текстов.
15. Представление графики и звука в ЭВМ.
16. Основные типы данных и процедуры их обработки.
17. Основные алгоритмы обработки массивов.
18. Основные алгоритмы обработки динамических структур.
19. Hash-таблицы и поиск информации.
20. Системы управления базами данных. Реляционная модель.
21. Функциональные зависимости и нормальная форма БД.
22. Объекты и классы. Объектно-ориентированная методология программирования.
23. Технические средства хранения и передачи информации.
1. Понятие информации и ее качественные характеристики.
Информация - прослойка между субъективным восприятием и объективной реальностью. Субъекты взаимодействуют с окружающей средой только за счет обмена информацией.
Характеристики:
Семантическая
Знак:
а) концепт (формулировка, понятие)
б) денотат (множество объектов)
Синтаксическая
набор четких правил, задающих логическую структуру
Гносеологическая
степень новизны и актуальность информации
Аксиологическая
ценность для субъекта
Коммуникативная
Отношение данной информации к средствам общения людей
Физическая
свойства носителя информации
Информация:
- первичная (получается из непосредственного наблюдения за объективной реальностью)
- вторичная (результат обработки первичной информации. При этой обработке количество информации не увеличивается!)
2. Принципы измерения информации. Энтропия. Свойства энтропии.
1) Количество информации должно обладать свойствами меры (положительность, монотонность, аддитивность)
2) Количество информации зависит от вероятности наступления события (если событие наступает с вероятностью 1, то информация о нем нулевая; чем меньше вероятность наступления события, тем больше количество информации о его наступлении)
3) Получение информации уменьшает неопределенность при принятии решений.
Энтропия (Н) - мера неопределенности. Энтропия определяется не для отдельного события, а для полной группы событий.
(основание роли не играет)
Свойства энтропии
1. H(X)>=0
2. Если одно из pi=1, а остальные равны 0, то из log1=0 и lim p->0 (p log(p)) = 0 следует H(X)=0, т.е. неопределенность отсутствует.
3. При заданном N наибольшая энтропия будет, когда все pi=1/N.
4. 
3. Условная вероятность и условная энтропия.
Условная вероятность
Условная энтропия
Совместная и условная энтропия связаны равенством
H (XY) = H (X) + H (Y | X)
Условная энтропия не больше безусловной, потому что добавление ограничений уменьшает неопределенность
H (Y | X) <= H (Y)
H (X | Y) <= H (X)
Следовательно: H (XY) <= H(X) + H(Y)
4. Взаимная информация. Потери информации от помех. Избыточность.
I(X,Y) = H(Y) - H(Y | X) >=0
Симметрично I(X,Y) = H(X) - H(X | Y).
Взаимная информация – мера снятой неопределенности при получении сообщений Y
Таким образом, имеет место полная симметрия между X и Y
H (XY) = H(X) + H(Y | X) = H(Y) + H(X | Y)
I (X,Y) = H(X) - H(X | Y) = H(Y) - H(Y | X)
H(XY) = H(X) + H(Y) – I(X,Y)
Если X и Y независимы, то H(Y | X) = H(Y) и H(X | Y) = H(X), значит, I(X,Y) = 0 и H (XY) = H(X) + H(Y)
В теории информации избыточность означает, что количество информации в сообщении меньше чем объем используемого алфавита
От избыточности можно избавиться, применяя эффективное кодирование, объем сообщения при этом уменьшается
При передаче по каналу связи с помехами, наоборот, добавляют проверочные символы для обнаружения ошибок, увеличивая избыточность
5. Информационные характеристики дискретных источников.
Без памяти:
С памятью:
6. Цепи Маркова. Характеристики Марковских источников.
Математической моделью ДИСП является цепь Маркова, Это последовательность состояний S[1], S[2],…,S[n],…, каждое из которых принадлежит множеству {S1, S2,…,Sm}, и заданные вероятности перехода πn2n1(j2 | j1) = P(S[n2]=Sj2 | S[n1] = Sj1)
Они должны удовлетворять следующим свойствам:
Стационарный источник – источник, у которого совместные вероятности последовательностей букв не зависят от начала отсчета.
Эргодичный источник – если по одной достаточно большой реализации можно судить о всех возможных реализациях.
Информационные характеристики ДИСП
7. Теоремы об эффективном кодировании.
· Цель эффективного кодирования – уменьшить избыточность источника
· Каждому символу однозначно соответствует последовательность из 0 и 1 (кодовое слово)
· Чем больше вероятность появления символа, тем меньше длина соответствующего кодового слова
· Наиболее эффективно кодирование больших блоков информации, но оно и более трудоемко
· Целесообразно обеспечить однозначное декодирование без дополнительных разделительных символов
Теорема кодирования 1
