В.Д. Валединский - Программа экзамена по программированию

Программа экзамена по программированиюЛектор — В. Д. ВалединскийIII семестр, 2004-2007 г.1. Билеты к экзамену (2006–2007)1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.Стек, дек, очередь. Непрерывные реализации.Ссылочные реализации списков (одно- и двунаправленного).Бинарное дерево поиска. Реализация; процедуры добавления, удаления, обхода.Произвольное дерево. Реализация; процедуры добавления, удаления, обхода.Сбалансированное бинарное дерево; процедуры добавления, удаления.

Теорема о глубине сбалансированного дерева.Красно-черное дерево; процедуры добавления, удаления. Терема о глубине красно-черного дерева.В-дерево; процедуры добавления, удаления. Трудоемкость операций с В-деревом.Битовая реализация множества.Хеширование. Примеры хеш-функций. Хеш-множество на базе массива списков.Хеш-множество по методу последовательных проб. Оценка среднего количества проб при поиске и добавлении.Совершенная (perfect) хеш-функция; определение, пример построения.Файловая система типа FAT (DOS, Windows).

Атрибуты fat, dir, data. Структура записи в каталоге.Алгоритм доступа к заданной позиции в файле. Особенности и различия версий FAT16, VFAT, FAT32.Файловая система типа EXT (Unix). Разграничение прав доступа к файлам, типы файлов. Областиblock group, superblock, data, INode list, descriptor table. Структура INode, таблица ссылок на блоки. Структура файлов-каталогов. Понятия жесткой и символической ссылок.

Алгоритм доступа к заданнойпозиции в файле.Файловая система типа NTFS (Windows NT, Windows 2000). Файл как набор атрибутов. Файл MFT, назначение, записи о системных метафайлах, записи для пользовательских файлов. Резидентные и нерезидентныеатрибуты. Организация ссылок на кластеры в нерезидентном атрибуте Data.Оценка снизу для трудоемкости сортировки сравнениями.Быстрая сортировка (quicksort); оценка средней трудоемкости.Турнирная (пирамидальная) сортировка (heapsort); оценка трудоемкости.Сортировка подсчетом с «линейной» оценкой трудоемкости.Сортировка с трудоемкостью O(n log2 p) для массива a[i] целых чисел, i = 0, . .

. , n − 1, 0 < a[i] < p.Алгоритм группового кодирования (RLE), байтовый и битовый варианты.Алгоритм Хаффмена (обычный и адаптивный). Теорема об оптимальности кода Хаффмена.Арифметическое кодирование (обычное и адаптивное). Теорема о сжатии данных при арифметическомкодировании.Алгоритм LZW.Формальные грамматики. Нормальная форма Бэкуса – Наура.

Примеры для арифметических к другихвыражений.LR-разборы. Процедура LR(1)-разбора выражений, соответствующих формальной грамматике.Модельный компилятор модельного алгоритмического языка. Разборка входного языка и архитектурымодельного процессора. Реализация модельного компилятора для случая линейных программ.Модельный компилятор. Компиляция условных и безусловных переходов. Реализация вызовов функций.Форма проведения экзамена1.

Письменный ответ на билет с вопросами, относящимися к темам представленной выше программы.2. Практическая задача на реализацию некоторых алгоритмов (или их частей), из лекционного курса.1Структура письменного билета1. Определение понятия, формулировка утверждения.2. Описание интерфейса представления данных на языке C/C++.3-4. Вопросы о сути алгоритмов, доказательств, представлений данных.5-6. Задачи по выполнению или оценке свойств алгоритмов на модельном наборе данных.Пример билета из экзамена 2006–2007Практическая задачаДаны откомпилированные заголовки для заполнения и печати произвольного дерева, в вершинах которогонаходятся буквы. Нужно ввести слово и определить все поддеревья, вершины которых содержат все буквывведенного слова, организовать указатели на корни этих поддеревьев в список и проходом по этому спискураспечатать такие поддеревья.Теоретическая часть1.

Сформулировать теорему о глубине сбалансированного дерева.2. Написать класс вершины красно-черного дерева и пояснить смысл используемых переменных, массивовили функций.3. Описать структуру корневого каталога и других каталогов в файловой системе FAT.4. Пояснить смысл средней трудоемкости в сортировке quicksort и объяснить, как это используется придоказательстве оценки трудоемкости.5. Изначально пустое бинарное сбалансированное дерево последовательно заполняется числами 3, 2, 7, 4, 9,8, 1, 10, 5. Потом удаляются последовательно числа 7 и 9.

Написать деревья, полученные после добавления всехчисел, после удаления 7 и после удаления 9.6. Написать формальную грамматику для прототипов функций.На выполнение письменной части отводится 1 акад. час, на реализацию программы — 2 акад. часа.Последняя компиляция: 3 сентября 2009 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.22. Программа экзамена 2004 года2.1. Структуры представления и хранения данных2.1.1. Непрерывные реализацииСтек, дек, очередь.2.1.2. Ссылочные реализацииСписки. Двунаправленный список. Однонаправленный список.

Кольцевой список.2.1.3. ДеревьяБинарное дерево поиска. Произвольное дерево. Процедуры обходов, поиска, добавления, удаления. Сбалансированное бинарное дерево; процедуры добавления, удаления. Теорема о глубине сбалансированного дерева.Красно-черное дерево; процедуры добавления, удаления. Теорема о глубине красно-черного дерева. В-дерево;процедуры добавления, удаления. Трудоемкость операций с В-деревом.2.1.4. МножестваБитовая реализация множества. Хеширование. Построение хеш-множества на базе массива списков. Хешмножество на базе последовательных проб. Оценка среднего количества проб при поиске и добавлении. Примерыхеш-функций.

Совершенная (perfect) хеш-функция, определения, пример построения.2.1.5. КонтейнерыКонтейнер для элементов фиксированного размера. Контейнер для произвольных элементов без операцииудаления. Идеи реализации управления памятью в общем случае (функции malloc и free).2.1.6. Файловые контейнеры: хранение данных в файловых системахФайловая система FAT (DOS, Windows). Атрибуты файлов.

Области BOOT, FAT, DIR, DATA. Структура записив каталоге. Алгоритмы для основных файловых операций: захват и освобождение кластера, доступ к требуемойпозиции в файле.Файловая система EXT (Unix). Области BOOT, SUPERBLOCK, INODELIST, DATA. Разграничение прав доступа кфайлам, типы файлов. Структура INode, таблица ссылок на блоки. Структура файлов-каталогов. Алгоритмыдля основных файловых операций: захват и освобождение блока, поиск свободного индекса, поиск требуемойпозиции в файле.Файловая система NTFS (Windows NT, Windows 2000). Файл как набор атрибутов. Файл MFT, назначение,записи о системных метафайлах, записи для пользовательских файлов.

Резидентные и нерезидентные атрибуты.Организация ссылок на кластеры в нерезидентном атрибуте Data; случаи разреженного и сжатого файлов.2.2. Некоторые алгоритмы обработки и преобразования данных2.2.1. Эффективные сортировкиОценка снизу для трудоемкости сортировки. Быстрая сортировка (quicksort); оценка средней трудоемкости.Турнирная (пирамидальная) сортировка (heapsort); оценка трудоемкости. Сортировка подсчётом с линейнойоценкой трудоёмкости.

Сортировка массива ai ∈ [1, . . . , p] из n элементов.2.2.2. Сжатие данныхАлгоритм группового кодирования RLE, байтовый и битовый варианты. Алгоритм Хаффмана (обычный иадаптивный). Теорема об оптимальности кода Хаффмана. Арифметическое кодирование (обычное и адаптивное). Теорема о сжатии данных при арифметическом кодировании.

Алгоритм LZW.2.2.3. КомпиляцияФормальные грамматики. Нормальная форма Бэкуса – Наура. Примеры для арифметических и других выражений. Рекурсивная процедура построения дерева разбора. Понятие о грамматических LR разборах. ПроцедураLR(1) разбора выражения, соответствующего формальной грамматике.Модельный компилятор модельного алгоритмического языка. Разработка входного языка и архитектурымодельного процессора.

Реализация модельного компилятора в случае линейных программ. Модельный компилятор. Компиляция условных и безусловных переходов. Компиляция вызовов функций. Передача параметровфункций через стек.32.2.4. Разделы из программы прошлого года, не вошедшие в программу этого годаЕщё немного о компиляторах Отображение результатов синтаксического разбора на другие архитектуры процессоров. Команды с одним, двумя, тремя операндами.Общая архитектура вычислительной системы Общая шина и ее составные части. Тактовый генератор и таймер.Интерфейсы внешних устройств и памяти.

Адресное пространство. Процесс обмена данными с памятью и дисками.Арбитраж шины.Общая архитектура процессора Основные устройства (управления, очередь команд, регистры, интерфейс шиныи пр.) Использование регистров, режимы адресации, разнообразные архитектуры и системы команд. Процесс обработкии выполнения команды в процессоре.Основные принципы работы операционной системы Система прерываний. Обработка сигнала прерыванияпроцессором. Управление памятью. Страничная организация виртуальной памяти. Структура таблицы страниц. Процесспреобразования виртуального адреса в реальный. Стратегии загрузки и замещения страниц.Кеш-память. Прямое отображение. Ассоциативное отображение.Состав билета для экзамена1. Письменный ответ на вопросы, относящиеся к темам представленной выше программы.2.

Практическая задача на реализацию алгоритмов (или их частей), рассматриваемых в лекционном курсе.3. Практическая задача на использование разных структур представления данных (списки, деревья, множества и пр.) при наличии откомпилированных заготовок.На выполнение письменной части отводится 1 академический час, на подготовку программ —2 академических часа.Структура письменного билета1.2.3.4.Определение понятия, формулировка утверждения.Описание интерфейса представления данных на языке C/C++.Вопросы о сути алгоритмов, доказательств представлений данных.Задача по выполнению или оценке свойств алгоритмов на модельном наборе данных.Пример из прошлогодних билетов1.

Сжатие данных. Арифметическое кодирование (обычное и адаптивное).2. Пусть массив int fat[1024] моделирует таблицу FAT32. Реализуйте функцию, которая возвращает дисковый номер k-го кластера файла по значению k и номеру стартового кластера. Функция должна правильнообрабатывать возможные некорректные ситуации.3. Даны откомпилированные функции для заполнения бинарного дерева поиска целыми числами. Реализовать функцию, вычисляющую значение суммы элементов дерева, лежащих на k-м уровне.Последняя компиляция: 3 сентября 2009 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.4.