- •1. Основные этапы развития информационных технологий.
- •2. Роль Беббиджа в развитии вычислительной техники.
- •3. Понятие информации. Информация и сообщения. Информационные системы.
- •4. Свойства информации. Действия над сообщениями. Носители сообщений.
- •5. Непрерывные и дискретные сигналы и сообщения. Преобразования сообщений.
- •6. Развертка и квантование. Теорема Котельникова.
- •7. Случайные события. Действия над событиями. Измерение вероятностей событий.
- •8. Понятие и свойства энтропии. Расчет энтропии для зависимых событий.
- •9. Энтропия и информация. Формулы Хартли и Шеннона.
- •10. Информация и алфавит. Относительная избыточность сообщений.
- •11. Кодирование сообщений. Условие неисчезновения информации при кодировании.
- •12. Средняя длина кодовой цепочки. Первая теорема Шеннона.
- •13. Характеристики способов построения двоичных кодов. Примеры кодов.
- •14. Кодирование текстовой информации. Текстовые форматы.
- •15. Неравномерное кодирование. Коды с разделителями.
- •20. Двоичная система счисления. Действия в двоичной системе.
- •21. Шестнадцатеричная система счисления. Действия в шестнадцатеричной системе.
- •22. Переходы между системами счисления.
- •23. Кодирование числовой информации. Формат с фиксированной точкой. Беззнаковое представление.
- •24. Кодирование числовой информации. Формат с фиксированной точкой. Знаковое представление.
- •25. Кодирование числовой информации. Нормализованные числа. Формат с плавающей точкой.
- •*26. Нормализация и денормализация. Диапазон и точность представления в формате с плавающей точкой.
- •*28. Независимость кода и его интерпретации.
- •29. Разновидности компьютерной графики.
- •Кодирование черно-белых изображений
- •Кодирование растровых цветных изображений.
- •32. Графические растровые форматы.
- •33. Обор разновидностей компьютерной графики.
- •34. Кодирование звуковой и видео информации. Мультимедийные форматы.
- •35. Передача информации. Линии и каналы связи и их характеристики.
- •36. Надёжность передачи и хранения информации. Вторая теорема Шеннона.
- •37. Кодирование с обнаружением и исправлением ошибок.
- •38. Коды Хемминга.
- •39. Способы передачи информации по линиям связи.
- •40. Передача информации по телефонным линиям связи. Модемы.
- •41. Понятие модели. Роль моделирования в науке.
- •41. Классификация моделей.
- •43. Системы. Методы изучения систем.
- •44. Классификация систем.
- •45. Различные аспекты понятия алгоритм. Фундаментальный аспект
- •46. Логические теории алгоритмов. Тезис Черча.
- •47. Машина Поста.
- •48. Интуитивное понятие алгоритма. Роль алгоритмов в обществе и в информатике.
- •49. Основные свойства алгоритмов.
- •50. Основные типы алгоритмов.
- •51. Способы задания алгоритмов. Алгоритмические языки.
- •52. Понятие переменной. Имя, тип и значение переменной.
- •53. Присваивание.
- •54. Основные управляющие конструкции. Следование. Задача обмена значениями.
- •55. Общий порядок построения алгоритмов.
- •56. Решение системы двух алгебраических уравнений с двумя неизвестными.
- •*61. Пример алгоритма работы с рекуррентными последовательностями.
- •62. Алгоритмы накопления сумм и произведений.
- •62. Алгоритмы определения экстремального элемента массива.
- •63. Задача поиска. Алгоритмы линейного поиска.
- •64. Бинарный поиск.
- •66. Построение кратных циклов.
- •67. Задача сортировки. Сортировка прямым выбором.
- •68. Понятие верификации алгоритмов. Инварианты циклов.
- •69. Сложность алгоритмов. Классы сложности р и ехр.
- •*70. Примеры оценки сложности алгоритмов.
- •71. Понятие подпрограммы.
- •72. Итерация и рекурсия.
- •73. Основные статические структуры данных.
- •74. Основные динамические структуры данных.
8. Понятие и свойства энтропии. Расчет энтропии для зависимых событий.
Энтропия представляет собой численную меру неопределенности в результатах опыта.
Единица измерения энтропии при двух равновероятных исходах называется бит
Энтропия, вносимая каждым из n равновероятных исходов равна:
= = =
Полная энтропия опыта с n неравновероятными исходами
=
Энтропия является мерой неопределенности опыта, в котором проявляется случайные события. Энтропия равна средней неопределенности всех возможных его исходов При прочих равных условиях наибольшую энтропию имеет опыт с равновероятными исходами.
Энтропия произведения независимых опытов равна сумме энтропий отдельных опытов.
=
- условная энтропия опыта B, при условии, что известен результат опыта A.
=
=
=
Свойства условной энтропии:
1. Неотрицательна: , условная энтропия равна нулю , если любой исход опыта A полностью определяет исход опыта B;
2. Если опыты A и B независимы, то , причем ,
3.
9. Энтропия и информация. Формулы Хартли и Шеннона.
Разность между безусловной H(B) и условной энтропиями показывает какие сведения об опыте B были получены в ходе опыта A. Эта величина может рассматриваться как информация об опыте B, содержащаяся в опыте A
=
I(A,B) 0, I(A,B)=0 если A и B независимы.
Энтропия опыта равна той информации, которая получается в результате его осуществления I(A,A)=H(A), так как (A)=0.
Формула Хартли:
Формула Шеннона: I=
Количество информации это числовая характеристика, отображающая ту степень неопределенности, которая исчезает после получения сообщения. Количество информации численно равно количеству вопросов с равновероятными бинарными вариантами ответов, которые необходимо задать, чтобы полностью снять исходную неопределенность задачи.
При получении информации в 1 бит неопределенность уменьшается в два раза. Ответ на бинарный вопрос содержит 1 бит информации для равновероятных исходов и менее одного бита в случае неравновероятных исходов
10. Информация и алфавит. Относительная избыточность сообщений.
Получение очередного символа сообщения можно рассматривать как случайное событие. Следовательно, с появлением очередного символа связано некоторое количество информации. Каждый знак алфавита, с помощью которого передается сообщение, несет в себе определенное количество информации.
Сообщения, в которых вероятность появления каждого отдельного знака не меняется со временем, называются шенноновскими, а порождающий сообщения отправитель - шенноновский источник
- убывающая последовательность.
11. Кодирование сообщений. Условие неисчезновения информации при кодировании.
Дискретное сообщение исходя из технических соображений или из особенностей органов чувств человека, участвующих в приеме или передаче сообщений, разбивают на конечные подпоследовательности знаков, которые принято называть словами. Количество знаков в слове называется длиной слова. Если все слова языка имеют одно и то же количество знаков, то такие слова называются n-разрядными (n - длина слова)
Слова записанные в двоичном, шестнадцатеричном и некоторых других алфавитах, принято называть кодом (двоичное слово - двоичный код и т.д.).
Исходный алфавит, в котором записано сообщение, называется первичным алфавитом. Целевой алфавит, в который преобразуется сообщение называется вторичным алфавитом.
Правило, описывающее соответствие между знаками первичного алфавита и знаками или сочетаниями вторичного называется кодом.
Набор знаков вторичного алфавита, используемого для представления знаков или их сочетаний первичного алфавита называется кодом.
Кодированием называется последовательность действий по переводу сообщения из первичного во вторичный алфавита.
Декодирование представляет собой операцию, обратную кодированию, то есть это последовательность действий по восстановлению сообщения в исходном алфавите по его виду во вторичном.
Операции кодирования и декодирования считаются обратимыми, если их последовательное применение обеспечивает восстановление исходной информации без потерь.
Кодером называется устройство, обеспечивающее выполнение операции кодирования. Декодером называется устройство, обеспечивающее выполнение операции декодирования.
Первичный алфавит A: N знаков, I(A) бит средняя информация на знак, исходное сообщение содержит n знаков.
Вторичный алфавит B: M знаков, I(B) бит средняя информация на знак, закодированное сообщение содержит m знаков.
Условие неисчезновения информации при кодировании:
Среднее количество знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита, будем обозначать K(A,B) и называть средней длиной кодовой цепочки или просто длиной кода: