Процедура проведения вступительного испытания
1. Вступительное испытание проводится в соответствии с действующими Правилами приема в бакалавриат и специалитет и Положением о порядке проведения вступительных испытаний МФТИ.
2. Вступительное испытание по информатике и ИКТ проводится с совмещением письменной и устной форм.
3. Вступительное испытание состоит из двух частей.
4. Письменная часть вступительного испытания содержит задания с кратким ответом и с развернутым ответом. Длительность первой части – 2 астрономических часа.
5. На устной части вступительного испытания происходит:
- обсуждение решений заданий письменной части;
- опрос по билету;
- при необходимости могут быть предложены дополнительные задания или вопросы.
6. Билет устной части содержит 2 вопроса из разных разделов программы. Устная часть проходит в формате собеседования, время на подготовку не отводится.
7. Длительность устной части – до 30 минут.
Технические особенности проведения вступительного испытания
с применением дистанционных технологий
1. Письменная часть
Письменная часть вступительного испытания проводится через систему прокторинга МФТИ, расположенную по адресу: http://exams.mipt.ru
Абитуриент обязан до начала вступительного испытания зарегистрироваться в системе прокторинга, если это не было сделано, и проверить техническую возможность подключения к системе прокторинга. Не подключение к системе прокторинга приравнивается к неявке на письменную часть.
2. Устная часть
Устная часть проводится с использованием системы прокторинга МФТИ либо одного из общеиспользуемых средств групповой коммуникации (Hangouts, Google Meet, Zoom и пр.).
Программа вступительного испытания
1. ВВЕДЕНИЕ
1.1. Информация и информационные процессы. Данные.
Информация – одно из основных обобщающих понятий современной науки. Передача информации в системах различной природы. Роль информации и связанных с ней процессов в окружающем мире.
Данные — информация, представленная в формализованном виде, пригодном для хранения, передачи и обработки. Информационные процессы – процессы, связанные с хранением, преобразованием и передачей данных.
Способы представления данных. Различия в представлении данных, предназначенных для хранения и обработки в автоматизированных компьютерных системах и предназначенных для восприятия человеком.
Структурирование данных.
Системы. Компоненты системы и их взаимодействие. Символ, знак, сигнал. Информационное взаимодействие в системе, управление. Разомкнутые и замкнутые системы управления. Математическое и компьютерное моделирование систем управления.
2. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
2.1. Тексты и кодирование
Равномерные и неравномерные коды. Префиксные коды. Условие Фано. Обратное условие Фано. Алгоритмы декодирования при использовании префиксных кодов.
Примеры кодов, используемых для кодирования текстов: ASCII, стандарт UNICODE. Кодирование кириллицы и других национальных алфавитов; кодовые страницы.
Сжатие данных. Учет частотности символов при выборе неравномерного кода. Оптимальное кодирование Хаффмана. Использование программ-архиваторов. Алгоритм LZW.
Передача данных. Источник, приемник, канал связи, сигнал, кодирующее и декодирующее устройства.
Пропускная способность и помехозащищенность канала связи. Кодирование сообщений в современных средствах передачи данных.
Искажение информации при передаче по каналам связи. Коды с возможностью обнаружения и исправления ошибок.
Способы защиты информации, передаваемой по каналам связи. Криптография (алгоритмы шифрования). Стеганография.
Темы курса основной школы, рекомендованные для повторения:
Алфавит, текст, длина текста. Количество различных текстов данной длины в данном алфавите. Кодирование символов одного алфавита с помощью кодовых слов в другом алфавите; кодовая таблица, декодирование .
2.2. Дискретизация
Измерения и дискретизация. Частота и разрядность измерений. Универсальность дискретного представления информации.
Дискретное представление звуковых данных. Многоканальная запись. Размер файла, полученного в результате записи звука.
Дискретное представление графической информации. Цветовые модели. Модели RGB и CMYK. Модели HSB и CMY. Глубина кодирования.
Сжатие данных при хранении графической и звуковой информации.
2.3. Системы счисления
Свойства позиционной записи числа: количество цифр в записи, признак делимости числа на основание системы счисления.
Алгоритм перевода десятичной записи числа в запись в позиционной системе с заданным основанием. Алгоритмы построения записи числа в позиционной системе счисления с заданным основанием и вычисления числа по строке, содержащей запись этого числа в позиционной системе счисления с заданным основанием.
Арифметические действия в позиционных системах счисления.
Краткая и развернутая форма записи смешанных чисел в позиционных системах счисления. Перевод смешанного числа в позиционную систему счисления с заданным основанием.
Представление целых и вещественных чисел в памяти компьютера. Компьютерная арифметика.
Темы курса основной школы, рекомендованные для повторения:
Позиционные системы счисления. Разложение числа по степеням основания системы счисления. Двоичная система счисления.
Восьмеричная система счисления. Триады восьмеричной системы счисления. Алгоритм перевода из двоичной системы счисления в восьмеричную систему и обратно.
Шестнадцатеричная система счисления. Тетрады шестнадцатеричной системы счисления. Алгоритм перевода из двоичной системы счисления в шестнадцатеричную систему и обратно.
2.4. Элементы комбинаторики, теории множеств и математической логики
Операции «импликация», «эквиваленция». Логические функции.
Законы алгебры логики. Эквивалентные преобразования логических выражений. Логические уравнения.
Построение логического выражения с данной таблицей истинности. Дизъюнктивная нормальная форма. Конъюнктивная нормальная форма.
Логические элементы компьютеров. Построение схем из базовых логических элементов. Триггер. Сумматор.
Дискретные игры двух игроков с полной информацией. Выигрышные стратегии.
Темы курса основной школы, рекомендованные для повторения:
Расчет количества вариантов: формулы перемножения и сложения количества вариантов. Логические высказывания. Логические операции НЕ, И, ИЛИ. Таблицы истинности логических выражений Множества и операции с ними. Диаграммы Эйлера-Венна.
2.5. Дискретные объекты
Ориентированные и неориентированные графы; цикл и ациклические графы; начальная вершина (источник) и конечная вершина (сток) в ориентированном ациклическом графе; расстояние между вершинами.
Алгоритмические задачи, связанные с анализом графов (примеры: задача построения оптимального пути между вершинами ориентированного ациклического графа; задача определения количества различных путей между вершинами).
Деревья. Поддерево; обход узлов дерева в глубину. Упорядоченные деревья (деревья, в которых упорядочены ребра, выходящие из одного узла).
Использовании деревьев при решении алгоритмических задач (примеры: анализ работы рекурсивных алгоритмов, разбор арифметических и логических выражений).
Использование графов, деревьев, списков при описании объектов и процессов окружающего мира.
Темы курса основной школы, рекомендованные для повторения:
Список. Первый элемент, последний элемент, предыдущий элемент, следующий элемент. Вставка, удаление и замена элемента.
Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Понятие минимального пути. Матрица смежности графа (0/1 матрица) и весовая матрица (с указанием длин ребер).
Дерево. Корень, лист, вершина (узел). Предшествующая вершина, последующие вершины. Поддерево. Высота дерева. Бинарное дерево.
3. АЛГОРИТМЫ И ЭЛЕМЕНТЫ ПРОГРАММИРОВАНИЯ
3.1. Алгоритмы и структуры данных
Алгоритмы исследования квадратного уравнения с целыми и вещественными коэффициентами.
Алгоритмы анализа и преобразования записей чисел в позиционной системе счисления.
Алгоритмы, связанные с делимостью целых чисел. Алгоритм Евклида для определения НОД двух натуральных чисел.
Алгоритмы линейной (однопроходной) обработки последовательности чисел без использования дополнительной памяти, зависящей от длины последовательности (вычисление максимума, суммы; линейный поиск и т.п.). Обработка элементов последовательности, удовлетворяющих определенному условию (вычисление суммы таких элементов, их максимума и т.п.).
Рекурсивные алгоритмы. Возможность их записи без использования рекурсии. Вычисление элементов рекурсивной последовательности. Построение и анализ дерева рекурсивных вызовов.
Алгоритмы обработки массивов. Вставка и удаление элементов в массиве.
Сортировка одномерных массивов. Квадратичные алгоритмы сортировки (пример: сортировка пузырьком). Слияние двух отсортированных массивов в один без использования сортировки. Рекурсивная реализация сортировки путем слияния двух отсортированных подмассивов.
Вычисление значения многочлена заданной степени в заданной точке (значения коэффициентов многочлена задаются массивом).
Алгоритмы анализа символьных строк.
Построение графика функции, заданной формулой, программой или таблицей значений.
Алгоритмы приближенного решения уравнений. Алгоритмы приближенного вычисления длин и площадей. Приближенное вычисление площади фигуры методом Монте-Карло. Построение траекторий, заданных разностными схемами. Решение задач оптимизации. Алгоритмы вычислительной геометрии. Вероятностные алгоритмы.
Сохранение и использование промежуточных результатов. Метод динамического программирования.
Представление о структурах данных. Примеры: списки, словари, деревья, очереди. Хэш-таблицы.
3.2. Языки программирования
Подпрограммы (процедуры, функции). Параметры подпрограмм. Рекурсивные процедуры и функции.
Логические переменные. Символьные и строковые переменные. Операции над строками.
Двумерные массивы (матрицы). Многомерные массивы.
Средства работы с данными во внешней памяти. Файлы.
Подробное знакомство с одним из универсальных процедурных языков программирования. Запись алгоритмических конструкций и структур данных в выбранном языке программирования. Обзор процедурных языков программирования.
Понятие о непроцедурных языках программирования и парадигмах программирования. Изучение второго языка программирования.
Темы курса основной школы, рекомендованные для повторения:
Основные алгоритмические конструкции: «следование» (последовательное выполнение команд), «ветвление» «цикл». Табличные величины (массивы). Одномерные массивы. Двумерные массивы.
Кодирование базовых алгоритмических конструкция на выбранном языке программирования. Оператор присваивания. Константы и переменные. Переменная: имя и значение. Типы переменных: целые, вещественные.
3.3. Разработка программ
Этапы решения задач на компьютере.
Структурное программирование. Проверка условия выполнения цикла до начала выполнения тела цикла и после выполнения тела цикла: постусловие и предусловие цикла. Инвариант цикла.
Методы проектирования программ «сверху-вниз» и «снизу-вверх». Разработка программ, использующих подпрограммы.
Библиотеки подпрограмм и их использование.
Понятие об объектно-ориентированном программировании. Объекты и классы. Инкапсуляция, наследование, полиморфизм.
Среды быстрой разработки программ. Графическое проектирование интерфейса пользователя. Использование модулей (компонентов) при разработке программ.
Темы курса основной школы, рекомендованные для повторения:
Проверка работоспособности программы с использованием трассировочных таблиц.
3.4. Элементы теории алгоритмов
Формализация понятия алгоритма. Машина Тьюринга – пример абстрактной универсальной вычислительной модели. Тезис Чёрча – Тьюринга.
Другие универсальные вычислительные модели (пример: машина Поста). Универсальный алгоритм. Вычислимые и невычислимые функции. Проблема остановки и ее неразрешимость.
Абстрактные универсальные порождающие модели (пример: грамматики).
Сложность вычисления: количество выполненных операций, размер используемой памяти; их зависимость от размера исходных данных
Сложность алгоритма сортировки слиянием (MergeSort).
Примеры задач анализа алгоритмов: определение входных данных, при которых алгоритм дает указанный результат; определение результата алгоритма без его полного пошагового выполнения.
Доказательство правильности программ.
Темы курса основной школы, рекомендованные для повторения:
Исполнители. Необходимость формального описания исполнителя. Алгоритм как план управления исполнителем (исполнителями).
3.5. Математическое моделирование
Практическая работа с компьютерной моделью по выбранной теме. Проведение вычислительного эксперимента. Анализ достоверности (правдоподобия) результатов экспериментов.
Представление результатов моделирования в виде, удобном для восприятия человеком. Графические представление данных (схемы, таблицы, графики).
Построение математических моделей для решения практических задач.
Имитационное моделирование. Моделирование систем массового обслуживания.
Использование дискретизации и численных методов в математическом моделировании непрерывных процессов.
Использование сред имитационного моделирования (виртуальных лабораторий) для проведения компьютерного эксперимента в учебной деятельности.
Использование учебных систем автоматизированного проектирования.
Темы курса основной школы, рекомендованные для повторения:
Понятие математической модели. Задачи, решаемые с помощью математического (компьютерного) моделирования.
Цикл моделирования: построение математической модели, ее программная реализация, проверка соответствия модели объекту или процессу моделирования на простых примерах (тестирование), проведение компьютерного эксперимента, анализ его результатов, уточнение модели.
4. ИНФОРМАЦИОННО-КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ
И ИХ ИСПОЛЬЗОВАНИЕ ДЛЯ АНАЛИЗА ДАННЫХ
4.1. Компьютеры, аппаратное и программное обеспечение
Аппаратное обеспечение компьютеров. Персональный компьютер.
Многопроцессорные системы. Суперкомпьютеры. Распределенные вычислительные системы и обработка больших данных. Мобильные цифровые устройства и их роль в коммуникациях. Встроенные компьютеры. Микроконтроллеры. Роботизированные производства.
Соответствие конфигурации компьютера решаемым задачам. Тенденции развития аппаратного обеспечения компьютеров.
Программное обеспечение (ПО) компьютеров и компьютерных систем. Различные виды ПО и их назначение: системное ПО (операционные системы, встроенное программное обеспечение, системы программирования), прикладное ПО (текстовые процессоры, браузеры и др.). Программное обеспечение мобильных устройств.
Инсталляция и деинсталляция программного обеспечения. Системное администрирование.
Компьютерные вирусы и вредоносные программы. Использование антивирусных средств.
Профилактические работы с аппаратным и программным обеспечением компьютерной техники.
Правовые нормы использования компьютерных программ и работы в Интернете. Законодательство РФ в области программного обеспечения.
Техника безопасности и правила работы на компьютере. Гигиена, эргономика, ресурсосбережение, технологические требования при эксплуатации компьютерного рабочего места. Проектирование автоматизированного рабочего места в соответствии с целями его использования.
4.2. Средства представления и анализа данных
Технологии создания текстовых документов. Вставка графических объектов, таблиц. Использование готовых шаблонов и создание собственных.
Средства поиска и замены. Системы проверки орфографии и грамматики. Нумерация страниц. Вставка сносок и ссылок, режим структуры документа, создание гипертекстового документа. Библиографическое описание документов. Коллективная работа с документами.
Технические средства ввода текста. Распознавание текста. Распознавание устной речи. Компьютерная вёрстка текста. Настольно-издательские системы.
Средства создания и редактирования математических текстов.
Технические средства ввода графических изображений. Кадрирование изображений. Цветовые модели. Коррекция изображений. Работа с многослойными изображениями.
Работа с векторными графическими объектами. Группировка и трансформация объектов.
Технологии ввода и обработки звуковой и видео информации.
Форматы графических, звуковых и видео файлов.
Мультимедийные презентации. Создание и настройка анимации.
Компьютерное 3D-моделирование. Представление о системах автоматизированного проектирования.
Технология обработки числовой информации. Ввод и редактирование данных. Автозаполнение. Форматирование ячеек. Стандартные функции. Виды ссылок в формулах. Решение вычислительных задач из различных предметных областей.
Компьютерные средствами представления и анализа данных. Визуализация данных.
Технология выполнения исследовательского проекта: постановка задачи, выбор методов исследования, составление проекта и плана работ, подготовка исходных данных, проведения исследования, формулировка выводов, подготовка отчёта. Верификация (проверки надежности и согласованности) исходных данных и валидация (проверки достоверности) результатов исследования.
Статистическая обработка данных. Обработка результатов эксперимента.
Анализ данных с применением методов машинного обучения. Большие данные.
4.3. Базы данных
Понятие и назначение базы данных (далее – БД). Классификация БД. Системы управления БД (СУБД). Таблицы. Запись и поле. Ключевое поле. Типы данных. Запрос. Типы запросов. Запросы с параметрами. Сортировка. Фильтрация. Вычисляемые поля.
Формы. Отчёты.
Многотабличные базы данных. Связи между таблицами. Нормализация.
4.4. Сети
Интернет. Система доменных имен. Сервисы Интернета. Технология WWW. Облачные сервисы. Протоколы сети Интернет. IP-адреса, маски подсети.
Поисковые системы в компьютерных сетях. Правила построения запросов.
Личное информационное пространство пользователя в сети Интернет. Сетевые сообщества. Публикация материалов в сети Интернет. Использование информационных систем в Интернете. Электронная коммерция.
Разработка веб-сайтов. Язык HTML, каскадные таблицы стилей (CSS). Динамический HTML. Размещение веб-сайтов.
4.5. Нормы работы с ИКТ
Стандарты в сфере информатики и ИКТ. Государственные электронные сервисы и услуги. Мобильные приложения. Открытые образовательные ресурсы. Информационная культура.
Правила поведения и информационной безопасности при работе в сети Интернет. Электронная цифровая подпись. Сетевой этикет.
Правовое обеспечение информационной безопасности РФ. Средства защиты информации в компьютерах, автоматизированных информационных системах и компьютерных сетях.
Литература
Основная:
1. Ройтберг, М.А. Информатика и ИКТ. Подготовка к ЕГЭ в 2017 году. Диагностические работы / М.А. Ройтберг. - М.: МЦНМО, 2017. - 176 c.
2. Семакин И.Г., Хеннер Е.К., Шеина Т.Ю. Информатика, 11 класс. Базовый уровень.
3. Поляков К.Ю., Еремин Е.А. Информатика, 11 класс. Углубленный уровень.
4. Угринович Н.Д. Информатика, 11 класс. Профильный уровень.
Дополнительная:
1. Информатика и ИКТ. Практикум по программированию. 10–11 классы. Базовый уровень / Под ред. Макаровой Н.В.. - СПб.: Питер, 2015. - 16 c.
2. Астафьева, Н.Е. Информатика и ИКТ: Практикум для профессий и специальностей технического и социально-экономического профилей: Учебное пособие / Н.Е. Астафьева. - М.: Academia, 2016. - 447 c.
3. Астафьева, Н.Е. Информатика и ИКТ: Практикум для профессий и специальностей технического и социально-экономического профилей / Н.Е. Астафьева. - М.: Academia, 2019. - 384 c.
4. Астафьева, Н.Е. Информатика и ИКТ: Практикум для профессий и специальностей технического и социально-экономического профилей / Н.Е. Астафьева. - М.: Academia, 2017. - 94 c.
5. Малясова С.В. Информатика и ИКТ: Пособие для подготовки к ЕГЭ / С.В. Малясова; Под ред. Цветковой М.С.. - М.: Academia, 2018. - 637 c.
6. Плотникова, Н.Г. Информатика и информационно-коммуникационные технологии (ИКТ): Учебное пособие / Н.Г. Плотникова. - М.: Риор, 2018. - 132 c.
7. Путимцева, Ю.С. Информатика и ИКТ. Подготовка к ОГЭ в 2017 году. Диагностические работы / Ю.С. Путимцева. - М.: МЦНМО, 2017. - 128 c.
8. Цветкова, М.С. Информатика и ИКТ: Учебник / М.С. Цветкова. - М.: Academia, 2017. - 352 c.
9. Цветкова, М.С. Информатика и ИКТ: Практикум для профессий и специальностей естественно-научного и гуманитарного профилей: Учебное пособие / М.С. Цветкова. - М.: Academia, 2017. - 352 c.
10. Цветкова, М.С. Информатика и ИКТ: Практикум для профессий и специальностей естественно-научного и гуманитарного профилей / М.С. Цветкова, И.Ю. Хлобыстова. - М.: Academia, 2017. - 200 c.
Другие ресурсы для подготовки: