Программа вступительных испытаний для поступающих в магистратуру по направлению 010300. 68 Фундаментальная информатика и информационные технологии
Скачать 127.9 Kb.
|
| П Р О Г Р А М М А вступительных испытаний для поступающих в магистратуру по направлению 010300.68 – Фундаментальная информатика и информационные технологии Дисциплина: Алгебра и геометрия Система координат. Векторная алгебра. Скалярное, векторное и смешанное произведение векторов, их геометрический смысл и выражение через координаты сомножителей. Алгебра матриц. Определители. Ранг матрицы. Системы линейных уравнений. Однородные системы линейных уравнений (общее решение, фундаментальная система решений). Теорема Кронекера – Капелли. Прямая линия на плоскости. Эллипс, гипербола, парабола, их изображение и их каноническое уравнение. Поле комплексных чисел. Кольцо многочленов от одного неизвестного. Неприводимые многочлены в поле Р. Разложение в произведение неприводимых множителей. Основная теорема алгебры. Следствия. Формулы Виета. Рациональные корни целочисленных многочленов. Кратные корни. Теорема о кратных корнях. Прямая и плоскость в пространстве. Элементы общей алгебры. Линейные пространства. Линейная зависимость и независимость системы векторов. Базис пространства. Определение эллипсоида, однополостного гиперболоиды, эллиптического параболоида, их изображение и каноническое уравнение. Литература
Дисциплина: Основы дискретной математики Комбинаторика. Выборки. Перестановки. Сочетания. Перестановки с повторениями. Сочетания с повторениями. Число сочетаний. Число перестановок. Перестановки данного состава. Полиномиальная формула. Производящие функции. Формула включений и исключений. Рекуррентные соотношения. Булевы функции. Основные способы задания булевых функций. Существенные и фиктивные переменные. Формулы и эквивалентность формул. Элементарные функции. Разложение функций по переменным. Совершенная дизьюнктивная нормальная форма. Совершенная коньюктивная нормальная форма. Полнота и замкнутость. Представление булевых функций полиномами Жегалкина. Линейные функции. Принцип двойственности. Леммы о немонотонной, несамодвойственной, нелинейной функции. Теорема Поста. Элементы теории графов. Графы. Основные понятия. Изоморфизм графов. Связность. Компоненты связности. Планарность. Литература:
Дисциплины: Математический анализ I-II, Кратные интегралы и ряды Понятие множества. Операции над множествами и их свойства. Определение предела числовой последовательности. Арифметические свойства пределов. Определение предела функции одной переменной в точке. Арифметические свойства пределов. Критерий Коши существования предела функции. Определение непрерывности функции одной переменной в точке. Арифметические действия над непрерывными функциями. Теорема об обращении в нуль функции непрерывной на отрезке (формулировка). Теорема о промежуточном значении функции, непрерывной на отрезке. Теорема об ограниченности функции, непрерывной на отрезке (формулировка). Теорема о достижении наибольшего и наименьшего значения функции, непрерывной на отрезке. Теорема о непрерывности дифференцируемой функции одной переменной. Необходимое и достаточное условие дифференцируемости функции двух переменных. Теорема Ферма (формулировка). Теорема Ролля. Теорема Лагранжа. Теорема Коши (формулировка). Формула Тейлора для функции одной переменной. Определенный интеграл и его свойства. Теорема о существовании определенного интеграла. Теорема об интегрируемости непрерывной функции. Теорема о среднем значении интеграла непрерывной функции (формулировка и геометрический смысл). Формула Ньютона-Лейбница. Критерий Коши сходимости числового ряда. Числовой ряд. Сумма ряда. Теорема об остатке числового ряда. Геометрическая прогрессия. Необходимое условие сходимости ряда. Определение двойного интеграла для прямоугольной области. Сведение двойного интеграла к повторному (прямоугольной и произвольной области). Равномерная сходимость последовательности функций и функционального ряда. Формула Грина. Дисциплина: Теория вероятностей и математическая статистика Классическое определение вероятности. Аксиомы теории вероятностей. Свойства вероятности. Условная вероятность. Теорема умножения. Независимость событий. Формула полной вероятности и формулы Байеса. Схема Бернулли. Формула Бернулли. Теорема Пуассона. Локальная предельная теорема Муавра-Лапласа. Выборка. Вариационный ряд выборки. Эмпирическая функция распределения. Свойства. Гистограмма и полигон относительных частот. Медиана и мода реализации выборки. Дисциплина: Методы оптимизации и исследование операций Задачи линейного программирования. Графический метод. Симплекс метод. Метод искусственного базиса. Двойственный симплекс метод. Двойственные задачи линейного программирования. Транспортные задачи. Метод потенциалов нахождения оптимального плана транспортной задачи. Транспортные задачи с дополнительными ограничениями. Задачи целочисленного программирования. Метод ветвей и границ. Метод Гомори. Целочисленные задачи линейного программирования. Задачи теории игр. Дисциплина: Алгоритмы и анализ сложности Основы анализа алгоритмов. Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; стандартные классы сложности; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти; рекуррентные соотношения и анализ рекурсивных алгоритмов. Стратегии алгоритмов. Полный перебор; метод "разделяй и властвуй"; "жадные" алгоритмы; бэктрекинг (перебор с возвратами); метод ветвей и границ; эвристический поиск; поиск по образцу, алгоритмы обработки строк; алгоритмы аппроксимации числовых функций. Основные алгоритмы обработки информации. Основные алгоритмы над числами; алгоритмы последовательного и бинарного поиска; алгоритмы сортировки сложности O(N*N) и O(N*logN); хеш-функции и методы исключения коллизий; деревья бинарного поиска; представление графов (списки и матрицы смежности); поиск в глубину и поиск в ширину; алгоритмы поиска кратчайших путей (алгоритмы Дейкстры и Флойда); транзитивное замыкание (алгоритм Флойда); алгоритмы построения минимального покрывающего дерева (алгоритмы Прима и Крускала); топологическая сортировка. Дисциплина: Языки программирования Введение История ЯП, обзор основных парадигм программирования (процедурная, объектно-ориентированная, функциональная парадигмы). Роль трансляции в процессе программирования. Место транслятора в программном обеспечении. Структура языка программирования. Синтаксис языка. Семантика языка. Лексемы. Понятия. Атрибуты. Области действия. Способы описания языков Грамматики. Классификация грамматик по Хомскому. Контекстно-свободные языки. Эквивалентные преобразования грамматик. Однозначность грамматики и языка. Набор допустимых преобразований. Достижимые свойства грамматик. Распознаватели. Конечные автоматы. Автоматы с магазинной памятью. Общее представление о процессе трансляции Принципиальная схема трансляции. Построение абстрактной программы. Этап генерации. Лексический анализ Функции лексического анализа. Реализация лексического анализатора в трансляторе. Функции расстановки Синтаксический анализ Стратегии разбора. Методы синтаксического анализа. Нисходящий анализ. Неформальное описание нисходящего разбора. Алгоритм нисходящего разбора. Восходящий разбор. Неформальное описание восходящего разбора. Алгоритм восходящего разбора. Табличные методы синтаксического анализа. Алгоритм Эрли. Алгоритм Кока-Янгера-Касами. Синтаксический анализ без возвратов. LL(k)-грамматики. Предсказывающие алгоритмы разбора. Разбор для LL(1)-грамматик. Алгоритм рекурсивного спуска. Проверка LL(k)-условия. Детерминированный восходящий синтаксический анализ. LR(k)-грамматики. Грамматики предшествования. Грамматики простого предшествования. Грамматики слабого предшествования. Грамматики операторного предшествования. Контекстный анализ и генерация Контекстный анализ Идентификация. Простейшая реализация идентификации. Атрибутная индукция. Генерация Промежуточные (внутренние) представления программы. Представление в виде ориентированного графа. Трехадресный код. Линеаризованные представления. Общая схема генерации. Представление структур данных. Генерация выражений и оператора присваивания. Генерация простых выражений. Учет составных переменных и вызовов функций. Генерация управления вычислениями. Генерация условного оператора. Генерация операторов перехода. Генерация подпрограмм и обращений к ним. Распределение памяти. Статическое распределение. Регулярное (магазинное) распределение. Динамическое распределение. Дисциплина: Теория автоматов и формальных языков Основные понятия и методы синтеза, использования регулярных выражений, детерминированных конечных автоматов, недетерминированных конечных автоматов, недетерминированных конечных автоматов с пустыми переходами, машины Тьюринга, языков, определяемых конечными автоматами, грамматиками, машиной Тьюринга. Дисциплина: Теория конечных графов и ее приложения Представление графов матрицами и списками. Морфизмы и изоморфизм графов. Типы графов. Графы, подграфы. Лемма о рукопожатиях. Пути и циклы. Эйлеровы обходы. Связность и достижимость. Деревья. Эквивалентные определения дерева. Поиск в глубину и в ширину. Бинарные деревья поиска. Наименьшая высота дерева с заданным числом вершин. Простые пути и алгебраические процедуры их перечисления. Вершинное покрытие. Задача о наименьшем покрытии. Раскраска и раскрашиваемость графа. Хроматическое число. Теорема о пяти красках. Остовное дерево графа наименьшего веса. Алгоритмы Прима и Крускала. Двудольные графы. Критерий двудольности Алгоритм Дейкстры нахождения кратчайшего пути, связывающего две заданные вершины взвешенного графа. Дисциплина: Компьютерные сети Эталонная семиуровневая модель ISO/OSI. Сетевые протоколы. Интерфейсы между уровнями модели OSI. Краткая характеристика уровней. Физический уровень модели OSI. Задачи. Средства реализации. Стандарты Ethernet и Fast Ethernet. Общие принципы, физический и канальный уровни. Адреса Ethernet. Беспроводные сети: среда передачи данных; типы; технические характеристики; сравнительная характеристика беспроводных и кабельных сетей. Топологии локальных сетей. Сравнение топологий «звезда», «общая шина», «кольцо»; использующие их сетевые технологии. Канальный уровень модели OSI. Подуровни MAC и LLC. Задачи. Средства реализации. Пример стандарта канального уровня. Сетевой уровень модели OSI. Протокол IP. Адресация. Маски и подсети. IP-маршрутизация. Трансляция сетевых адресов NAT. Управление сетевым доступом к файлам в пользовательских ОС семейства Windows. Протокол ARP. Определение MAC-адресов по IP-адресам. Транспортный уровень модели OSI. Транспортный уровень модели OSI. Протокол UDP. Основные характеристики, отличия от TCP, область применения. Протокол TCP. Основные характеристики. Механизм обеспечения надежности: последовательные номера. Разрешение доменных имен в IP-адреса: система доменных имен DNS. Управление сетевым доступом к файлам в пользовательских ОС семейства Windows. Протоколы telnet и SSH. Протокол FTP. Команды передачи данных. Протокол HTTP. Понятие запроса и ответа. Методы HTTP. Механизм реализации виртуального хостинга: заголовок Host. Язык разметки гипертекста HTML. Заголовки, абзацы, разрывы строки. Списки. Таблицы. Язык каскадных таблиц стилей CSS. Дисциплина: Интеллектуальные системы Тест Тьюринга. Понятие и причины возникновения термина. «Китайская комната» Сёрла. Понятие и причины возникновения терминов. Машина Тьюринга и машина Поста. Понятие и причины возникновения терминов. Оценка сложности алгоритма, NP-полнота на примере задачи коммивояжера. Эвристики. Методы эвристического поиска. Понятие, примеры использования. Логика высказываний (исчисление высказываний, логика нулевого порядка). Основные операции и законы. Логика предикатов (исчисление предикатов, логика первого порядка). Свойства и отличия от логики высказываний. Экспертные системы. Определение и назначение. Операция аппликации (Application) в лямбда-исчислении. Операция абстракции (Abstraction) в лямбда-исчислении. Функции высшего порядка и их применение в функциональном программировании. Операция свертки списка (Reduce, Folding, Accumulate) в функциональном программировании. Хвостовая и обычная рекурсии в функциональном программировании. Отличия и применение. Дисциплина: Технологии баз данных Назначение и история ИС. Информационно-поисковые системы (IS&R). Области применения ИС. Накопление и представление информации; анализ и индексация; поиск, выборка, связывание, навигация; конфиденциальность, целостность, безопасность и защищенность, сохранность; масштабируемость, производительность, эффективность Базы данных - основа информационных систем. Традиционные файловые системы. Системы с базами данных. Распределение обязанностей в системах с базами данных. История развития СУБД. Преимущества и недостатки СУБД.. Базы данных на больших ЭВМ. БД на персональных компьютерах. Распределенные БД. Перспективы развития. Технология Баз данных. Основные понятия и определения. Архитектура базы данных. Физическая и логическая независимость. Пользователи БД. Функции администраторов БД. Модели данных. Иерархическая, сетевая. Определения, операции, языки для каждой. Примеры. Реляционная модель Определения. Операции. Реляционная алгебра. Проектирование реляционных БД на основе принципов нормализации. Системный анализ предметной области (пример). Даталогическое проектирование. Язык SQL. Структура и типы данных. Простые выборки, предикаты. Соединения. Функции. Вложенные запросы. Объединения. Поддержка целостности Моделирование данных. Концептуальные модели (сущность-связь, Унифицированный Язык Моделирования (UML)); объектно-ориентированная модель; реляционная модель. Дисциплина: Программная инженерия
Дисциплина: Вычислительная математика
Вычислительные методы как раздел современной математики. Роль компьютерно – ориентированных вычислительных методов в исследовании сложных математических моделей. Схема вычислительного эксперимента. Вычислительный алгоритм. Оценки погрешностей округления.
Метод Гаусса. Метод простой прогонки. Итерационные методы: простая итерация, метод Зейделя. Метод наискорейшего градиентного спуска.
Интерполяционный многочлен Лагранжа. Многочлены Чебышева. Наилучшее приближение в линейном нормированном пространстве. Существование элемента наилучшего приближения. Дискретное преобразование Фурье. Быстрое преобразование Фурье. Сплайны, экстремальные свойства сплайнов. Численное дифференцирование. Правило Рунге оценки погрешности.
Простейшие квадратные формулы. Метод неопределенных коэффициентов. Квадратурные формулы Ньютона-Котеса. Квадратурные формулы Гаусса. Оценки погрешностей квадратурных формул. Правило Рунге оценки погрешности. Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений: метод Эйлера, методы Рунге-Кутта, метод Адамса. Конечно-разностные методы.
Метод интераций для решения нелинейных уравнений и систем. Метод Ньютона. Метод спуска.
Простейшие методы решения краевой задачи для уравнения второго порядка. Метод конечных разностей.
Векторные и параллельные компьютеры. Основные понятия параллелизма и векторизации. Анализ методов умножения матриц для векторных и параллельных компьютеров. Прямые методы решения линейных систем для векторных и параллельных компьютеров. Итерационные методы решения линейных систем для векторных и параллельных компьютеров: методы Якоби, Гаусса-Зейделя, SOR. Дисциплина: Параллельное программирование Понятие параллельного программирования. Многопроцессорные вычислительные комплексы. Распределенная и общая память. Примеры реализаций. Основные парадигмы параллельного программирования. Инструменты и методы для программирования систем с общей и распределенной памятью. Характеристики производительности параллельных приложений. Характеристики производительности параллельных приложений: ускорение, параллельная эффективность, масштабируемость. Введение в MPI. Библиотека MPI. Модель SPMD. Инициализация и завершение MPI-приложения. Точечные обмены. Точечные обмены данными между процессами MPI-программы. Режимы буферизации. Отложенные пересылки. Прием по шаблону и "условие гонок". Пример параллельной реализации программы приближенного вычисления интеграла методами трапеций и адаптивной квадратуры. Парадигма управляющий-рабочие. Коллективные взаимодействия процессов. Причина введения коллективных взаимодействий. Основные функции коллективных взаимодействий. Пример параллельной программы для метода Якоби решения систем линейных уравнений. Управление группами и коммуникаторами. Назначение коммуникаторов. Интра- и интеркоммуникаторы. Создание и уничтожение коммуникатора. Применение коммуникаторов для разработки библиотек. Пример реализации библиотечной функции приближенного вычисления определенного интеграла. Система типов в MPI. Базовые и производные типы. Соответствие типов. Запаковка и распаковка данных. Среда OpenMP. Модель выполнения OpenMP-приложения. Директива parallel. Директивы для распределения работы и синхронизации в OpenMP. Дисциплина: Программирование в .NET
|
Добавить документ в свой блог или на сайт
Похожие:
 | Программа дисциплины Языки программирования для направления 010300.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010300.... | | Программа вступительных испытаний в магистратуру «менеджмент» ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ В МАГИСТРАТУРУ ПО НАПРАВЛЕНИЮ 080200.68 «МЕНЕДЖМЕНТ» ДЛЯ ПОСТУПАЮЩИХ В МГУП ИМЕНИ ИВАНА ФЕДОРОВА... |
| Радиофизический факультет Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной... | | Программа вступительных испытаний в магистратуру по направлению 050100.... Программа вступительных испытаний в магистратуру по направлению обсуждена и утверждена на заседании общеинститутской кафедры педагогики... |
 | Программа вступительных испытаний для поступающих в магистратуру... Список литературы введение 3 | | Программа вступительных испытаний в магистратуру по направлению 080100... Программа предназначена для поступающих в магистратуру фгбоу впо «Бурятский государственный университет» по направлению 080100 «Экономика»... |
| Программа дисциплины Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений 231300. 62 «Прикладная... | | Программа вступительных испытаний в магистратуру по направлению 040100.... Программа вступительного экзамена по рекламе и связям с общественностью для поступающих в магистратуру по направлению 031600. 68.... |
| Программа вступительных испытаний в магистратуру по направлению подготовки... Программа предназначена для поступающих в магистратуру фгбоу впо «Бурятский государственный университет» по направлению 032700. 68... | | Программа вступительных испытаний (тестирования) для поступления... Программа вступительных испытаний содержит требования по уровню знаний абитуриентов, поступающих в магистратуру по направлению подготовки... |
| Программа вступительных испытаний для поступающих в магистратуру по направлению подготовки Среда обитания. Особенности строения: специализация клеток, два клеточных слоя(наружный и внутренний) | | Программа вступительных испытаний в магистратуру по направлению 030300. 68 «Психология» Программа вступительных испытаний в магистратуру по направлению 030300. 68 «Психология» («Социальная психология больших и малых групп»)... |
| Программа вступительных испытаний в магистратуру по направлению 030300. 68 «Психология» Программа вступительных испытаний в магистратуру по направлению 030300. 68 «Психология» («Психология профессионализации личности»)... | | Iii вопросы к собеседованию: Информатика Целью вступительных испытаний является отбор наиболее квалифицированных выпускников бакалавриата и специалитета для поступления в... |
| Программа вступительных испытаний в магистратуру по направлению 050100.... Программа вступительных испытаний в магистратуру по направлению 050100. 68 «Педагогическое образование» («Менеджмент в образовании»)... | | Программа вступительных испытаний для поступающих в магистратуру... ... |
