Аннотация к вопросам ГЭК по информатике

1. Сформулировать принципы сложение и умножения. Пример задачи и общее правило на размещения с повторением. Примеры и правила для размещения без повторений, перестановки и сочетания без повторений. Биномиальные коэффициенты, некоторые из основных соотношений, их комбинаторные доказательства. Пример на перестановки и сочетания с повторениями. [26, 66, 71]

2. Понятие и примеры рекуррентных соотношений. Линейные рекуррентные соотношения, общий способ их решения, описание множества всех решений, примеры второго (третьего) порядков. Общее описание метода динамического программирования. Примеры применения рекуррентных соотношений к решению задач этим методом. [26, 66, 71]

3. Основные понятия теории графов: ребро, вершина, кратность, путь, цикл, ориентированный и мультиграф, взвешенный граф. Представление структуры графа с помощью матрицы смежности и матрицы инцидентности, примеры. Связность, компоненты связности, алгоритмы обхода вершин связного графа «в глубину» и «в ширину» с примерами. [26, 66, 71, 166, 178]

4. Понятие эйлерова цикла в обычном и ориентированном графе, условие его существования и алгоритм поиска. Примеры. Описание алгоритмов Дейкстры и Флойда (с примерами) для нахождения кратчайших путей в обычном и взвешенном графах. Постановка задачи нахождения остовного дерева в графе, описание алгоритмов Краскала и Прима, примеры. [26, 66, 71, 166, 178]

5. Школьное определение алгоритма, свойства, способы задания. Необходимость строгого определения. Три различных подхода – Чёрча, Тьюринга и Маркова. Общее описание подходов, их эквивалентность. Примеры неразрешимых задач. Подробное описание одного из трёх подходов (на выбор отвечающего). [3, 105, 143, 178]

6. Моделирование и формализация. Этапы построения действующей модели. Классификация моделей. Прикладные модели из естественных наук – много примеров. Рассмотрение всех этапов на примере конкретной модели, например, колебаний маятника. [51, 76, 104, 105, 137, 138, 150, 165]

7. Общий принцип стохастического моделирования. Метод Монте-Карло и его приложения. Моделирование произвольной дискретной случайной величины. Моделирование абсолютно непрерывных случайных величин. Примеры – равномерно распределённая величина, нормально распределённая величина, случайная величина с пуассоновским законом распределения. Применение в системах массового обслуживания. [51, 76, 105, 137, 138, 150, 165]

8. Различные определения информации в школьных учебниках. Свойства информации: объективность, полнота, достоверность, адекватность, доступность, актуальность. Носители информации, классификация по формам представления, по способам восприятия, по общественному значению. Основные информационные процессы (по одному из школьных учебников). Методы и модели оценки количества информации (объемный, алгоритмический, энтропийный). Примеры. [104, 109, 150, 165]

9. Понятие позиционной и непозиционной системы счисления, примеры. Примеры таблиц умножения и сложения в системах счисления с основанием, отличным от 10. Алгоритмы перевода целых и дробных чисел из десятичной системы в любую другую и обратно. Перевод вещественных чисел из восьмеричной системы в 16-ю. [4, 5, 6, 168]

10. Основные понятия кодирования. Двоичный принцип кодирования информации в ПК. Кодирование текста, таблицы кодировки. Представление натуральных чисел в беззнаковой арифметике и действия с ними. Представление целых чисел в знаковой арифметике и действия с ними в ПК. Обработка переполнений в обоих случаях. Примеры. Представление вещественных чисел в ПК, мантисса и порядок. [4, 5, 6, 168]

11. Суть арифметического подхода, примеры кодирования. Суть алгоритмов Хаффмана и Шеннона-Фано, примеры построения деревьев и кодирования. Дополнительно – кодирование повторяющихся последовательностей, принципы работы известных архиваторов. [88, 105, 168, 143, 178]

12. Школьные алгоритмы сортировки – «пузырек», метод вставок, их трудоемкость. Примеры, когда эти методы работают долго. Метод слияния, оценка его трудоемкости. Обзор других методов. [25, 121, 122, 147, 168, 178]

13. Общая структура программы на языке Паскаль. Конструкции ветвления и выбора на Паскале, примеры. Различные виды команды повторения на Паскале, их взаимосвязь. Работа с процедурами и функциями на Паскале, привала записи и исполнения, команда вызова. Процедуры и функции обработки строк на Паскале. Примеры простейших программ. [85, 121, 122, 147, 168]

14. Массивы в Паскале, правила описания, обращения к элементам, базовые задачи обработки массивов: сумма и произведение всех элементов и ли их части, поиск, счетчик, минимум. Работа с множествами в Паскале: описание, ввод и вывод, примеры программ. Записи, их описание и обращение к отдельным полям, оператор присоединения. Примеры использования записей в программах. Файлы, их типы и виды (по доступу в элементам). Основные команды для работы с файлами, примеры программ. [25, 85, 121, 122, 147, 168]

15. Статическая и динамическая память при работе программы на Паскале. Понятие адреса и указателя. Принцип организации списков и деревьев. Виды списков: стеки, очереди, деки. Описание списков и примеры базовых задач работы со списками: удаление и добавление элементов, печать списка, поиск элемента и т.п. Примеры решения задач с использованием списков. Описание деревьев, примеры базовых задач работы с деревьями: обход, удаление и добавление элементов, печать дерева, поиск элемента и т.п. Примеры решения задач с использованием деревьев. [25, 85, 144, 147, 168, 178]

16. Представление о программировании в машинных кодах, о машинно-ориентированных языках низкого уровня (ассемблер). Языки высокого уровня. Изменение структуры программ по мере увеличения ее объема – возникновение процедур и функций для структурирования программ, объединение их в модули, смысл объектно-ориентированного программирования и три его основных свойства: инкапсуляция, наследование и полиморфизм. Жизненный цикл программ: написание, отладка, тестирование, эксплуатация, модернизация и отмирание. [25, 85, 144, 147, 168]

17. Смысл логического программирования и его отличия от процедурного программирования. Структура программы на языке Пролог. Описание фактов и правил, запросы, простейшие примеры. Правило резолюции для вывода новых фактов в Прологе, примеры его применения. Механизм вывода в Прологе, (прямая и) обратная стратегия вывода. Организация, описание и работа со списками в Прологе, простейшие примеры программ. Использование рекурсии для решения базовых задач: поиск, удаление и добавление элементов, организация счетчиков, вычисление сумм, нахождение максимумов и т.п. Работа с файлами в Прологе, примеры простейших программ. [22, 56]

18. Язык HTML. Назначение языка, общая структура, основные конструкции. Примеры. [47, 54, 65]

19. Операционная система DOS, ее состав и возможности. Оболочки над DOS, их назначение и устройство на примере Norton. Графическая оболочка и операционная система Windows, ее различные версии. Различные виды окон, стандартные программы Windows, объекты рабочего стола. Многозадачные и многопользовательские системы. Управление процессами и потоками. Дополнительно – обзор других операционных систем. [54, 65, 88, 105, 143]

20. Обзор прикладного программного обеспечения. Вирусы и антивирусные программы. Архиваторы, назначение, функции и использование. Органайзеры, назначение, функции и использование. Другие типы программ. [54, 65, 88, 104, 143]

21. Типы баз данных: реляционные, иерархические и сетевые. Устройство таблиц и их взаимосвязь в реляционных базах данных. Процесс нормализации данных, нормальные формы (первые три обязательно). Типы полей в СУБД Access. Варианты создания и редактирования таблиц, запросов, форм и отчетов. Различные виды запросов и форм (желательно с примерами). Использование макросов и модулей. Распределённые базы данных. [54, 65, 88, 105]

22. SQL. Назначение, функции и использование. Примеры использования SQL для выборки данных из таблицы, создание SQL- запросов. [54, 65, 88, 105, 143]

23. Понятие компьютерной математической системы (КМС). Отличия от других классов программ, предоставляющих возможность проведения вычислений. Функции и основные возможности КМС. Компьютерные математические системы MathCAD, Derive, Mathematica, Maple: сравнительный анализ возможностей, интерфейса. Ввод и редактирование математических выражений, построение графиков функций в прямоугольной декартовой системе координат, полярной системе координат, графиков функций, заданных параметрически. Построение графиков функций двух переменных. Символьные преобразования многочленов, символьное интегрирование и дифференцирование, решение уравнений, неравенств, систем уравнений; подстановки для переменных. Упрощение выражений. [48, 49, 50, 67]

24. Локальные и глобальные компьютерные сети, их топология. Доменный принцип адресации в сети Интернет, примеры. Основные сервисы Интернет и их описание: www, ftp, телеконференции. Поиск информации в Интернет. Электронная почта, организация ее работы. [47, 54, 65, 88, 105, 143]

25. Постановка перечисленных задач, условия применения различных методов их решения, суть предлагаемых методов, условия окончания вычислений и оценки погрешностей в них, как теоретические, так и применяемые на практике. Примеры. [8, 70, 105]

26. Постановка задачи решения систем линейных уравнений. Качественный анализ. Описание общего метода Гаусса. Применения метода Гаусса для нахождения ранга матрицы, вычисления определителей, определения совместности системы, нахождения обратной матрицы. Условия применимости и этапы метода квадратного корня. Суть и условия применения метода прогонки. Общее описание, условие применимости и условие окончания вычислений метода простых итераций. Постановка задачи, качественный анализ, суть метода наименьших квадратов. [8, 70, 88, 105, 143]

27. Постановка основных задач линейного программирования. Примеры. Общая, каноническая и двойственные задачи, теоремы двойственности. Графический способ решения для случая двух переменных. Алгоритм и геометрический смысл симплекс-метода. [8, 70, 88, 105, 143]

28. Понятие ошибок первого и второго рода в статистике, уровня значимости, мощности критерия. Параметрические и непараметрические критерии. Обзор критериев Стьюдента, Манна-Уитни и Вилкоксона, χ ² -Пирсона, λ -критерия Колмогорова-Смирнова. [31, 51, 125, 142]

29. Антагонистическая конечная игра двух игроков с нулевой суммой. Понятия платежной матрицы, нижней и верхней цены игры, решения игры. Условие существования решения в чистых стратегиях, примеры. Понятие смешанной стратегии, формулировка теоремы о существовании решения в смешанных стратегиях. Сведение к задаче линейного программирования, графический способ решения для случая двух стратегий у одного из игроков. Примеры. [24, 29, 110]

30. Основные понятия теории систем массового обслуживания. Простейшие потоки событий. Граф состояний системы, вывод уравнений для нахождения предельных вероятностей. Примеры. Основные характеристики СМО. Нахождение предельных вероятностей и вычисление основных характеристик для случая одноканальных и многоканальных СМО с отказами, с ограниченной и неограниченной очередью. [24, 29]