Министерство образования и науки Российской Федерации
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
УТВЕРЖДАЮ
Председатель приёмной комиссии
Е.А. Ваганов
31 января 2014 г.
ПРОГРАММА
вступительного испытания в магистратуру в форме письменного экзамена Направление 09.04.01 «Информатика и вычислительная техника»Красноярск 2014
СОДЕРЖАНИЕ ПРОГРАММЫ
(по дисциплине «Информатика и вычислительная техника») Организация и архитектура ЭВМ Архитектура системы. Основные понятия, определения и характеристики вычислительных систем. Архитектура простейших вычислительных систем, магистрально-модульный принцип построения.Классификация компьютеров по областям применения. Классификация Флинна. Параллельные системы. Понятие о многомашинных и многопроцессорных вычислительных системах (ВС). Области применения ЭВМ различных классов. Персональные компьютеры и рабочие станции. Xтерминалы. Серверы. Мейнфреймы. Кластерные архитектуры.
Информационно-логические основы ЭВМ.
Способы представления информации в ЭВМ. Позиционные системы счисления. Операции преобразования двоичных кодов. Машинные коды двоичных чисел. Алгебра Буля и системы логических элементов ЭВМ.
Машинные коды: прямой, обратный, дополнительный, модифицированный.
Формы представления информации в ЭВМ. Арифметические операции с двоичными числами. Операции двоично-десятичной арифметики. Аксиомы и законы алгебры логики. Кодирование текстовой и числовой информации в ЭВМ.
Элементы и узлы ЭВМ. Классификация элементов и узлов ЭВМ. Семейства логических схем и системы элементов. Функциональная полнота систем логических элементов. Минимизация логических функций. Правила преобразования логических функций. Комбинационные узлы ЭВМ.
Дешифраторы. Мультиплексоры. Шифраторы. Арифметическо-логические устройства. Последовательностные логические узлы. Триггеры. Регистры.
Счетчики.
Архитектурные особенности ЭВМ. Архитектурные особенности ЭВМ различных классов. ЭВМ с непосредственными связями, с канальной организацией и магистральной структурой. Основные тенденции развития ЭВМ.
Компонентная база и аппаратное обеспечение ЭВМ Архитектура базового процессора. Функциональная и структурная организация процессора. Система команд базового микропроцессора.
Программно - структурные модели команд (микроархитектура). Основные стадии выполнения команд. Типы и форматы команд. Способы адресации:
непосредственная, прямая, регистровая, косвенная регистровая адресация.
Архитектура универсальных микропроцессоров. Особенности системы команд микропроцессоров семейства Х86. Способы адресации данных и переходов. Адресации со смещением: относительная, базовая, комбинированная. Программная модель 32 – разрядных микропроцессоров.
Понятие режима виртуального V86.
Микропроцессорные и встраиваемые системы.
Классификация микропроцессоров. Понятие о разрядности и системе команд.
Тактирование и синхронизация. Эволюция микропроцессорной техники.
Микропроцессоры Intel 8086-i7.Универсальные микроконтроллеры в составе встраиваемых систем. Архитектурные особенности современных микроконтроллеров. Критерии и методики оценки показателей микропроцессорных систем. ПЛИС в системах обработки данных.
Встраиваемые процессорные ядра. Методы и способы ввода аналоговой информации в микропроцессорную систему.
Организация памяти ЭВМ. Организация регистровой и оперативной памяти (запомнающих устройств, ЗУ) в ЭВМ. Иерархия памяти. Статические и динамические ЗУ произвольной выборки (RAM). Типы статической и динамической памяти. Методы организации доступа в ЗУ (адресная, магазинная, стековая и ассоциативная организации доступа). Постоянные ЗУ (ПЗУ, ROM). Классификация и основные характеристики ПЗУ. Типы ПЗУ.
Кэш-память. Методы доступа к кэш-памяти.
Организация памяти в защищенном режиме. Общие понятия и терминология защищенного режима. Многоуровневая модель защиты вычислительных ресурсов. Аппаратные (регистровые) средства микропроцессора, обеспечивающие работу в защищенном режиме.
Адресация памяти в защищенном режиме. Механизм сегментации памяти.
Дескрипторы и таблицы. Механизм переключения задач. Страничная адресация в универсальных микропроцессорах.
Организация ввода-вывода информации в ЭВМ. Организация параллельного и последовательного ввода-вывода. Программируемые параллельные адаптеры и организация параллельного обмена в ЭВМ.
Структурная схема программируемого параллельного адаптера. Назначение сигналов и шин. Режимы работы программируемого параллельного адаптера.
Форматы управляющих слов. Примеры конфигурации в режиме «0».
Стробируемый ввод-вывод. Временные диаграммы для режима «1».
Двунаправленная магистраль. Временные диаграммы для режима «2».
Пример организации параллельного ввода-вывода. Режимы последовательного обмена данными в ЭВМ. Программируемые связные адаптеры. Архитектура. Режимы обмена. Форматы управляющих слов и слова состояния. Программирование адаптера. Пример организации последовательного ввода-вывода.
Система прерываний. Организация прерываний в ЭВМ. Программные и аппаратные прерывания. Организация аппаратных прерываний с помощью контроллера прерываний для архитектур семейства IBM РС. Структура контроллера прерываний. Прерывания по запросу (векторное) и по результатами опроса (поллинг). Форматы управляющих слов. Алгоритм обработки запросов на прерывания. Прямой доступ в память - как особый случай режима прерывания. Контроллер прямого доступа в память.
Структурная схема, назначение сигналов и шин. Режимы работы.
Программирование контроллера ПДП. Особенности организации прерываний для 32-разрядных микропроцессоров.
Интерфейсы ЭВМ. Организация системных и локальных шин в ЭВМ.
Характеристики и параметры шин. Система сигналов и шин в электронных вычислительных машинах. Группы и назначение шин. Использование системных шин в качестве канала ввода — вывода. Достоинства и недостатки ЭВМ с шинной организацией. Способы повышения производительности ЭВМ с шинной организацией. Примеры организации системных шин и перспективы их развития. Роль и место локальных шин для повышения производительности ЭВМ. Примеры организации локальных шин.
высокопроизводительных последовательных шин в качестве системных шин.
высокопроизводительные интерфейсы. Назначение, характеристики и параметры интерфейсов. Сигналы и группы шин интерфейсов. Транзакции на шине. Примеры временных диаграмм обмена. Разновидности стандартов.
Способы повышения производительности на шине. Недостатки существующих стандартов перспективы развития. Последовательные высокопроизводительные интерфейсы. Назначение, режимы работы и стандарты. Основные характеристики и параметры. Роль и место интерфейсов в архитектуре современных ЭВМ и периферийных устройств.
Периферийные устройства. Устройства ввода информации в ЭВМ и системах. Устройства ввода информации в ЭВМ. Устройства подготовки данных, клавиатура, манипуляторы. Устройства ввода звуковой (речевой) и видеоинформации. Устройство, режимы работы, и характеристики сканеров.
Цифровые фотоаппараты как устройства ввода текстовой и графической информации. Дигитайзеры - устройства для ввода картографической и аэронавигационной информации. Узлы обработки данных в аналоговой и гибридной формах. Линейные и нелинейные компоненты и устройства для обработки информации в аналоговом и гибридном виде.
Цифро-аналоговые и аналого-цифровые преобразователи информации.
Устройства вывода информации в ЭВМ и системах. Устройства вывода данных из ЭВМ. Устройства, обеспечивающие формирование твердых копий воспроизводимых документов. Принтеры.. Принципы формирования оттисков на носитель. Способы получения цветного изображения. Плоттеры и графопостроители. Устройства визуализации изображения.
Видеомониторы. Типы видеомониторов и принципы воспроизведения цветной графической информации на экране. Аппаратные средства, обеспечивающие вывод информации на экраны мониторов. Графические карты. Архитектура графической карты. Устройства вывода (синтеза) звуковой информации.
Внешние запоминающие устройства ЭВМ и систем. Периферийные устройства для систем хранения. Дисковые накопители. Накопители на гибких магнитных дисках и их разновидности. Накопители на жестких магнитных дисках (винчестеры) и их разновидности. Архитектура контроллеров дисковых накопителей. Флэш – накопители. Оптические и магнитооптические накопители. DVD – диски. Внешняя голографическая память. RAID-массивы. Сети хранения данных.
Программирование Общее понятие алгоритма и исполнителя. Определение вычислительной машины как универсального исполнителя алгоритмов. Программное обеспечение ЭВМ. Машинный язык и языки высокого уровня. Основные этапы решения задач на ЭВМ. Определение алгоритма. Свойства алгоритмов.
Способы конструирования программ. Нисходящее проектирование структурированных программ. Жизненный цикл программ. Основные этапы разработки программного обеспечения. Постановка задачи и спецификация программы. Документирование программного продукта. Критерии качества программ.
Структура программы на языке высокого уровня. Семантика языков программирования. Средства для написания программ: алфавит, лексика, синтаксис языка. Термины языка. Стандартные типы данных. Диапазоны изменения различных типов данных. Константы в языке. Указатели.
Определение переменных. Выражения. Основные операции над простыми типами данных. Совместимость и преобразования типов данных.
Структурное программирование. Представление основных структур:
итерации, ветвления, повторения. Операторы языка: присваивание, условный, цикла. Составной оператор. Ветвление: условный оператор и оператор выбора. Особенности программирования вычислительных операций. Особые ситуации, возникающие при вычислениях, и их обработка. Простейшие циклы: итерации, повторения.
Вычисления с вещественными данными. Точность машинных вычислений. Организация вычислений с заданной точностью.
Разработка простейшего интерфейса. Диалоговые программы. Разработка диалоговых элементов в программе. Функции ввода-вывода.
Среды программирования. Назначение и состав среды программирования.
Работа с меню и настройка среды программирования. Компиляция и запуск программ. Тестирование и отладка программ. Критерии качества программы.
Массив как структура данных. Определение массива. Одномерные и двумерные массивы. Размещение массива в памяти.
Адреса, указатели и ссылки. Адресная арифметика. Выделение динамической памяти. Типы данных, определяемые пользователем:
структуры, файлы. Работа со строками символов. Структуры. Массивы структур. Указатели на структуры.
Организация работы с файлами. Файлы текстовые, типизированные.
Встроенные языковые средства для работы с файлами разных типов.
Последовательный и прямой доступ к компонентам файлов.
Функции и процедуры. Описание функций. Построение и использование функций. Фактические и формальные параметры. Механизм передачи параметров. Локальные и глобальные переменные. Область действия имен.
Массивы и функции. Разработка многомодульной программы. Рекурсивные определения и алгоритмы. Понятие стека вызовов функций.
Программирование рекурсивных алгоритмов. Имя функции как параметр.
Динамические структуры данных. Линейные списки: основные виды и способы реализации. Стеки, очереди, линейные двунаправленные списки, кольцевые списки. Правила использования памяти при работе с динамическими структурами данных. Двоичное дерево поиска. Построение, обход, добавление, удаление узлов, поиск в двоичном дереве.
Основные понятия объектно-ориентированного программирования.
Объекты. Классы. Основные свойства объектно-ориентированного программирования.
Операционные системы Определение операционной системы. Классификация операционных систем. Назначение и функции операционных систем (ОС). Требования, Мультипрограммирование. Монолитные Операционные системы. Модульная структура построения ОС и их переносимость. Многоуровневые операционные системы. Режим разделения времени. Многопользовательский режим работы. Операционные системы клиент-сервер и микроядро. Режим работы и ОС реального времени. Объектно-ориентированные ОС.
Универсальные операционные системы и ОС специального назначения.
Управление процессором. Понятие процесса и ядра. Понятие нити.
Состояния процессов и нитей. Структура контекста процесса. Идентификатор и дескриптор процесса. Иерархия процессов. Алгоритмы планирования процессов. Понятия приоритета и очереди процессов. Вытесняющие и невытесняющие алгоритмы планирования. Способы реализации мультипрограммирования. Диспетчеризация и синхронизация процессов.
Семафоры.
Понятие файловой системы. Кластер, Сектор, Цилиндр и способы адресации информации на внешних носителях.
Организация параллельного и последовательного ввода-вывода.
Классификация способов управления памятью. Способы организации памяти без использования внешних носителей. Виртуальная память. Механизм реализации виртуальной памяти. Защита памяти. Сегментация виртуального адресного пространства процесса. Страничный способ организации памяти.
Стратегия подкачки страниц. Сегментно-страничный способы организации памяти. Совместное использование памяти.
Управление устройствами ввода-вывода. Средства обработки сигналов.
Драйверы. Принципы программного обеспечения ввода-вывода. Понятие прерывания. Понятие событийного программирования. Многопроцессорный режим работы.
Принципы построения и защита от сбоев и несанкционированного доступа. Задачи администрирования. Аудит. Реестр Windows.
Администрирование пользователей и групп пользователей. Предоставление доступа к ресурсам компьютера.
Сети и телекоммуникации Классификация информационно-вычислительных сетей. Способы коммутации. Сети одноранговые и “клиент/сервер”. Трехзвенная архитектура. Понятия «Телекоммуникационная сеть», «Информационная сеть, «Вычислительная сеть». Назначение компьютерных сетей.
Разновидности компьютерных сетей по технологии передачи между узлами, масштабу сети, топологии; их преимущества и недостатки. Понятие коммутации. Выделенные и коммутируемые каналы. Коммутация пакетов в режимах: дейтаграммном, виртуального вызова, установлением виртуального канала и установлением виртуального соединения. Клиент-серверная архитектура; горизонтальное и вертикальное разделение компонент.
Трехзвенная архитектура; одноранговые сети. Эталонная модель ISO/OSI:
причины появления, функции уровней.
Аналоговые каналы передачи данных. Способы модуляции. Модемы.
Определение канала передачи информации; основные характеристики каналов связи: АЧХ, полоса пропускания, затухание, емкость, пропускная способность, достоверность передачи. Понятие модуляции, основные виды и их принципы. Цифровые каналы передачи данных. Разделение каналов по времени и частоте. Основные принципы организации цифровых каналов передачи данных. Методы разделения каналов по времени и частоте.
Характеристики проводных линий связи. Витые пары, коаксиальные кабели, волоконно-оптические линии связи. Спутниковые каналы. Сотовые системы связи. Проводные и кабельные линии связи. Виды и категории витых пар. Устройство и виды коаксиальных кабелей. Волоконно-оптические кабели, их виды, устройство, принципы работы; полное внутреннее отражение и мода сигнала. Передача радиосигнала, особенности связи в различных диапазонах. Передача в видимом световом диапазоне и ИКдиапазоне. Спутниковые системы связи; классификация спутников по высоте орбиты, различия их характеристик. Преимущества и недостатки спутниковых систем связи. Мобильная связь. Поколения и стандарты мобильной связи, общая архитектурные принципы (базовые станции и MSC), повторное использование частот; процедура handoff. Виды конференц – связи.
Кодирование информации. Количество информации и энтропия.
Самосинхронизирующиеся коды. Представление информации при передаче;
синхронный и асинхронный режимы передачи; синхронизация и самосинхронизирующиеся коды; коды NRZ, RZ, Манчестер, AMI, HDB3.
Способы контроля правильности передачи информации. Алгоритмы сжатия данных. Основные методы повышения достоверности передачи. Понятие разрешенного и запрещенного множеств, кратности ошибки, кодового и минимального кодового расстояния. Проверка по четности и код Хемминга.
Представление данных в виде двоичных многочленов; основные операции с двоичными многочленами: сложение, умножение, деление, циклический сдвиг. Общий алгоритм вычисления циклического кода. Алгоритмы сжатия информации; понятие степени сжатия; основные виды алгоритмов:
адаптивные и неадаптивные; с потерями и без потерь. Алгоритмы RLE, разностного кодирования, Хаффмена.
Локальные вычислительные сети. Методы доступа. Множественный доступ с контролем несущей и обнаружением конфликтов. Разновидности сетей Ethernet.
Управление доступом к общей среде передачи. Преимущества и недостатки широковещательных сетей; чистая и дискретная системы ALOHA, варианты протоколов CSMA, отличия протокола CSMA/CD. Сети Ethernet; управление доступом к среде CSMA/CD, формат MAC адреса;
основные поля пакета Ethernet; обозначения сетей Ethernet, причины популярности. Сеть Token Ring, ее основное преимущество в сравнении с Ethernet 10 Base-T; основные поля заголовка; принципы приоритизации. Сети FDDI, принцип двойного кольца FDDI.
Высокоскоростные локальные сети. Организация корпоративных сетей.
Технологии построения современных локальных и корпоративных сетей передачи данных.
Функции сетевого и транспортного уровней. Алгоритмы маршрутизации.
Задачи маршрутизации. Понятие метрики. Отличия статических и динамических алгоритмов, одноуровневой и иерархической маршрутизации.
Дистанционно-векторные алгоритмы и алгоритмы состояния связей.
Протокол RIP, основные принципы, преимущества и недостатки. Протокол OSPF, основные принципы, преимущества и недостатки. Протоколы TCP/IP.
Протоколы управления. Стек протоколов TCP/IP; соответствие протоколов TCP/IP уровням модели ISO/OSI. Протокол IP. Назначение, основные задачи;
фрагментация и сборка пакетов, основные поля заголовка IP. Протоколы ARP и RARP, их назначение; кэш ARP. Протокол ICMP, основные команды.
Протокол TCP. Назначение, основные характеристики и задачи; основные поля пакета; порты TCP и UDP. Механизм установления TCP соединения;
механизм скользящего окна. Протокол UDP. Назначение, характеристики и задачи; уровень модели ISO/OSI.
Адресация в Internet. IP адресация, классы адресов, адреса хоста, сети, широковещательный. Формат адресов IPv6, причины появления IPv6.
Особенности технологий Frame Relay, ATM, SDH. Технология Frame Relay.
Понятия PVC, SVC; адресация во Frame Relay. Управление перегрузками во Frame Relay, биты FECN, BECN, DE; качество обслуживания во Frame Relay:
Committed Burst Rate, Committed Burst Size, Excess Burst Size. Технология ATM. Назначение. Понятие ячейки. Понятие уровня адаптации ATM, классов служб.
Сетевые операционные системы. Технологии распределенных вычислений.
Структура и информационные услуги территориальных сетей. Понятия распределенной и сетевой операционных систем, их типы; средства промежуточного уровня. Микроядро. Мультикомпьютерные и мультипроцессорные операционные системы. Протоколы файлового обмена, электронной почты, дистанционного управления.
Прикладные протоколы TCP/IP, их назначение: FTP, Telnet, SMTP/POP.
Web-технологии. Языки и средства создания Web-приложений. Протокол HTTP, языки HTML и XML.
Базы данных Назначение и основные компоненты системы баз данных. Обзор современных СУБД. Уровни представления баз данных. Модели данных.
Иерархическая и сетевая модели данных Реляционная модель данных. Основные понятия реляционной модели данных. Тип данных, домен, отношение, атрибут, схема отношения, подсхема.
Понятие первичного и внешнего ключа. Правила Кодда. Операции реляционной алгебры.
Концептуальное проектирование. Аномалии и проблемы в отношениях, необходимость нормализации, функциональные и транзитивные зависимости. Декомпозиция отношений, нормальные формы. Основные понятия концептуальной модели данных. Сущность и связь. Степень связи.
Диаграммы в нотациях UML, Чена и SSADT. Получение отношений из диаграмм. Основные приемы концептуального проектирования. Паттерны проектирования баз данных Структурированный язык запросов (SQL). Простые запросы. Группировки и групповые операции. Соединения. Теоретико-множественные операции.
Сортировка. Подзапросы. Кванторы существования и всеобщности в SQL.
Обобщённые табличные выражения. Операторы манипуляции реляционными данными. Определение схемы данных и таблиц в SQL. Представления данных. Примеры Управление транзакциями. Многопользовательский доступ. Проблемы параллельной обработки данных. Блокировки. Проблема тупиков и пути ее разрешения. Уровни изоляции транзакций.
Физическая организация БД. Создание и модификация базы данных.
Физическая модель данных. Хешированные и индексированные файлы.
Доступ по первичному ключу: индексы, В-деревья. Поиск по дереву.
Алгоритмы вставки и удаления. Доступ по вторичному ключу:
инвертированные списки. Оптимизация запросов.
Администрирование баз данных. Защита в БД. Функции и задачи АБД.
Защита баз данных. Распределение прав доступа. Мандатная система защиты.
«