«УТВЕРЖДАЮ»
Декан
факультета Кибернетика
___________________
ВОПРОСЫ
К ГОСУДАРСТВЕННОМУ ЭКЗАМЕНУ
ПО СПЕЦИАЛЬНОСТИ
010200 – ПРИКЛАДНАЯ МАТЕМАТИКА
01 апреля 2004 г.
МЕТОДЫ ОПТИМИЗАЦИИ
1. Линейное программирование. Симплекс-метод. Привести числовой пример решения задачи линейного программирования симплекс-методом с использованием симплекс-таблиц.
2. Двойственные задачи линейного программирования. Двойственный симплекс-метод. Привести числовой пример решения задачи линейного программирования двойственным симплекс-методом с использованием симплекс-таблиц.
3. Линейное целочисленное программирование. Алгоритм Гомори. Геометрическая иллюстрация дополнительного ограничения.
Литература
1. Ашманов программирование. М.: Наука, 1981.
2. , Финкельштейн программирование. М.: Мир, 1969.
3. Кузин кибернетики. Т.1. М.: Энергия, 1973.
4. Салмин программирование. Ч. I. М.: МИФИ, 1978.
5. Салмин программирование. Ч. II. М.: МИФИ, 1979.
6. Салмин программирование. Компьютерный учебник. М.: МИФИ, 1998.
ТЕОРИЯ ВЕРОЯТНОСТИ И
МАТЕМАТИЧЕСКАЯ СТАТИСТИКА
1. Условная вероятность события. Формула полной вероятности и формула Байеса. Независимость событий (попарная и в совокупности). Примеры.
2. Одномерные и многомерные случайные величины. Их основные характеристики: функции распределения и плотности распределения, свойства. Функции случайного аргумента в одномерном и двумерном случаях.
3. Ковариационная и корреляционная матрицы и их основные свойства. Связь независимости и некоррелированности. Пример совпадения этих понятий. Преобразование ковариационной матрицы при применении линейного оператора к случайному вектору.
4. Точечные оценки и их свойства: несмещенность, состоятельность и эффективность.
5. Сходимость последовательностей случайных величин по вероятности, в средне-квадратичном, слабая сходимость. Законы больших чисел. Неравенство Чебышева. Теорема Чебышева и связанные с ней обобщения. Связь сходимости в средне-квадратичном и по вероятности.
6. Основные методы получения точечных оценок: метод моментов, метод максимального правдоподобия. Функция правдоподобия в непрерывном и дискретном случаях. Основные свойства получаемых оценок. Примеры.
7. Проверка статистических гипотез. Статистические гипотезы простые и сложные. Основная и альтернативная гипотезы. Ошибки 1-го и 2-го рода. Критическая область. Критерий проверки основной статистической гипотезы и его основное свойство. Примеры проверки статистических гипотез относительно параметров нормального закона в различных случаях.
8. Проверка гипотез о виде закона распределения. Примеры.
Литература
1. . Курс теории вероятностей и математической статистики. М.: Наука, 1982.
2. . Курс теории вероятностей. М.: Наука, 1988.
3. . Вероятность. М.: Наука, 1980.
4. . Курс теории вероятностей. М.: Наука, 1978.
5. , Ю. и. Медведев. Математическая статистика. М.: Высшая школа, 1984 .
6. Сборник задач по математике для втузов. Часть 4. Под общей редакцией и . Издательство Физико-математической литературы, 2003 г.
ЧИСЛЕННЫЕ МЕТОДЫ
1. Основные понятия и определения курса "Численные методы" ( метрического пространства, близости, нормы, сходимости)
2. Методы нахождения корней уравнения: простой итерации, Ньютона, хорд, секущих.
3. Интерполяция функций. Общий подход. Выбор класса приближающих функций, их основные свойства. Построение интерполяционных многочленов Лагранжа и Ньютона. Конечные и разделенные разности.
4. Аппроксимация функций. Постановка задачи. Условия существования и единственности среднеквадратичного приближения. Метод наименьших квадратов (МНК).
Литература
1. | 51 Т89 | Турчак численных методов. М. Наука, 1987. |
|
2. | 519 Б30 | , , Кобельков методы. - М., Наука, 1987. |
|
3. | 519 Б30 | , , Кобельков методы (в задачах и упражнениях). - М., Наука, 2000 |
|
4. | 519 В12 | Волков методы. М., Наука. 1980. |
|
5. | Хемминг методы М., Наука 1972 | ||
БАЗЫ ДАННЫХ
1. Определение модели данных СУБД.
2. Трехуровневая архитектура схем баз данных в СУБД.
3. Независимость программ и данных на физическом уровне и на логическом уровне.
4. Определение и характерные черты баз данных.
5. Функции СУБД
6. Реляционная алгебра.
7. Нормальные формы отношений. 1, 2 и 3 нормальные формы.
8. Представление операций реляционной алгебры.
9. Общий вид оператора SELECT. Типы соединений таблиц.
10. Подзапросы. Применение подзапросов с операторами SELECT, UPDATE, INSERT, DELETE
Литература
1. Введение в системы управления базами данных
www.citforum.ru/database/edu.shtml
2. Кузнецов С, Основы современных баз данных
www.citforum.ru/database/edu.shtml
ИНФОРМАТИКА. ПРАКТИКУМ НА ЭВМ
1. Алгоритм линейного поиска в одномерном массиве. Зависимость затрат на линейный поиск в среднем и в худшем случае от числа элементов массива. Улучшение линейного поиска: поиск с барьером.
2. Алгоритм двоичного поиска в одномерном отсортированном массиве. Зависимость затрат на двоичный поиск в среднем и в худшем случае от числа элементов массива.
3. Последовательная и связанная память. Представление линейных списков в последовательной и связанной памяти. Достоинства и недостатки того и другого представления.
4. Операции, выполняемые со стеком, очередью и деком. Дек с ограниченным выходом и полный дек. Структуры данных, используемые для реализации стека, очереди, дека с ограниченным выходом и полного дека.
5. Алгоритмы обработки односвязного списка в прямом и обратном порядке.
6. Понятие обхода дерева. Виды обходов двоичного дерева. Определение структуры двоичного дерева по двум заданным обходам. Рекурсивные алгоритмы обходов двоичных деревьев.
7. Деревья поиска. Алгоритм построения дерева поиска. Алгоритм поиска заданного значения в дереве поиска. Использование деревьев поиска для сортировки данных. Алгоритм исключения узла из дерева поиска.
Литература
004
1. В52 Алгоритмы и структуры данных. СПб.: Невский диалект, 2001.
004
2. К53 Кнут программирования: Пер. с англ.
М.: Вильямс. Т.1: Основные алгоритмы, 2002.
681.3
3. П16 , Ильинский данных (линейные списки).
М.: МИФИ.
004
4. М27 , Панферов данных (деревья):
Конспект лекций. М.: МИФИ, 2003.
СИСТЕМНОЕ И ПРИКЛАДНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
1. Операционная система. Функции, назначение. Многопользовательские системы. Мультипрограммные системы.
2. Языки управления заданиями (языки команд операционной системы). Процедуры.
3. Средства управления вводом/выводом. Понятия наборов данных и файлов. Операции поддерживаемые на системном уровне.
4. Организация данных на внешних носителях. Связывания программы с наборами данных. Перенаправление стандартных потоков ввода/вывода.
5. Управление данными на внешних носителях. Ограничения доступа к наборам данных.
6. Процессы в операционных системах. Общие понятия. Ресурсы процесса.
7. Процессы в операционных системах. Создание и уничтожение процесса. Наследование свойств.
8. Процессы в операционных системах. Взаимодействие процессов. Сигналы и их обработка.
9. Процессы в операционных системах. Взаимодействие процессов. Сообщения и их обработка.
10. Процессы в операционных системах. Взаимодействие процессов. Семафоры и их обработка.
Литература
1. Кеннет Розан, Ричард Родзинский, Джемс Харбер, Дуглас Хост Введение в UNIX System V Release 4 2-е издание: "ЛОРИ",М,1999.
2. Андрей Робачевский Операционная система UNIX: БХВ, Санкт-Петербург, 1999.
3. Теренс Чан Системное программирование на C++ для UNIX: изд. группа BHV, Киев, 1999.
ДИСКРЕТНАЯ МАТЕМАТИКА
1. Аксиоматика теории множеств. Алгебра множеств, свойства операций объединения, пересечения и дополнения до универсума.
2. Бинарное отношение. Способы задания бинарных отношений. Обратное и дополнительные отношения. Композиция отношений. Ядро отношения.
3. Свойства бинарных отношений. Рефлексивность, симметричность, транзитивность.
4. Классы бинарных отношений. Отношение эквивалентности и отношение порядка, их свойства.
5. Логическое высказывание и его свойства. Логические операции (связки). Формализация логических суждений. Решение логических уравнений.
6. Алгебра логики. Свойства операций алгебры логики. Эквивалентные преобразования алгебраических выражений. Доказательство логических тождеств.
7. Формальное (аксиоматическое) определение исчисления высказываний.
8. Суперпозиция булевых функций. Классы булевых функций. Функционально полные системы функций. Критерий полноты. Базис.
9. Размещения, размещения без повторения, перестановки, сочетания. Их комбинаторные характеристики. Формула включений и исключений.
10. Графы, частичные графы, подграф. Операции над графами.
11. Сильная связность орграфа. Компонента сильной связности орграфа. Алгоритм порождения компонент сильной связности. Конденсат графа.
12. Цикломатика графов. Цикломатическое число. Цикломатический базис. Алгоритм порождения циклов графа.
13. Реберные графы. Критерий реберности графа. Алгоритм порождения образа реберного графа.
14. Задача раскраски графа. Хроматическое число графа и его оценка. Приближенная раскраска графа по Ершову.
15. Машина Тьюринга, ее структура и свойства. Проблема остановки МТ.
Литература
3. , , . Дискретная математика: Учебник для студентов втузов. – М.: АСТ»: , 2003.
4. Дискретная математика для программистов..- СПб.: Питер, 2001.
Согласовано:
Заведующий каф. № 22
Заведующий каф. № 28
Заведующий каф. № 33
Заведующий каф. № 36
