- •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. Основные динамические структуры данных.
74. Основные динамические структуры данных.
У данных с динамической структурой с течением времени изменяется сама структура, а не только количество элементов, как у файлов или последовательностей. Базовыми динамическими структурами данных являются:
1. линейный список;
2. дерево;
3. граф.
У линейного списка каждый элемент связан с предшествующим ему. У линейного списка известно, какой элемент находится в начале списка, какой в конце, а также, какой элемент стоит перед текущим. В линейном списке переходить от текущего элемента к следующему можно только с помощью указанных связей между соседними элементами.
В целом получается цепочка элементов, в которой можно осуществлять поиск, куда можно вставлять элементы или откуда исключать их.
На базе линейного списка организуются много других типов динамических структур. Это в частности: кольца, очереди, деки и стеки.
Структура кольца
Отличие кольца от линейного списка в том, что у кольца имеется связь между последним элементов списка и его первым элементом.
У линейного списка и у кольца возможен доступ к любому элементу структуры. Для этого нужно последовательно перемещаться от одного элемента к другому. Во многих реальных ситуациях такой доступ отсутствует. Можно взаимодействовать только с первым и последним элементами или же только с одним из них. Для моделирования таких объектов используются очереди, деки и стеки.
Структура очереди
У очереди доступен для включения конец, а для исключения (выборки) ─ начало. Элемент, поступивший в очередь раньше и обслуживается раньше. Говорят, что очередь это структура с дисциплиной обслуживания FIFO (First In, First Out) ─ «первый пришёл, первый ушел».
Структура дека
У дека оба конца доступны, как для включения, так и для выборки. Таким образом, можно сказать, что дек ─ это двусторонняя очередь.
Структура стека
У стека для взаимодействия доступна только один конец структуры ─ вершина стека. И включение нового элемента в стек и выборка последнего ранее включенного идет через вершину стека. Таким образом на обслуживание попадает первым элемент, поступивший последним. Говорят, что стек ─ это структура с дисциплиной обслуживания LIFO (Last In, First Out) ─ «последним пришёл, первым ушёл».
Структура дерева
Деревом называется структура данных, элементы которой связаны отношениями подчиненности, когда одному элементу может быть подчинено несколько, но при этом он может сам быть подчинен только одному. В структуре имеется только один элемент, не подчиняющийся никаким другим. Это элемент называется корнем дерева.
Корнем дерева является элемент a, он находится на самом высоком уровне. В дереве нет элементов, которым подчиняется корень. Узлы b, c и d подчиняются (порождаются, являются дочерними узлами) узлу а. Узел а является для них родительским, порождающим. В свою очередь узлы b и d имеют по несколько дочерних узлов, а узел с таковых не имеет.
Структура графа
Структурой данных наиболее общего вида является граф. Любые элементы графа могут быть связаны с любыми другими элементами.