Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе




НазваниеУральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе
Дата03.02.2016
Размер4,5 Kb.
ТипПрограмма
Уральский государственный университет им. А.М. Горького

Математико-механический факультет

Программа государственного экзамена по магистерской программе

(010301) Математические основы компьютерных наук


Дисретная математика и теория алгоритмов


Классы вычислительной сложности. Полные проблемы. Сводимости. P, NP, co-NP, NLogSpace, LogSpace, PSpace, ExpTime. Вероятностные вычисления. Класс IP. Доказательство с нулевым разглашением. Теорема Кука. Вычислительная сложность проблемы "2SAT". Вычислительная сложность проблемы "MAX2SAT". Вычислительная сложность проблемы "Гамильтонов путь". Задача о трех красках. Задача о покрытии 3-множествами. Укладка ранца. Параметрическая сложность. Псевдополиномиальные алгоритмы. Функциональные проблемы. FNP: SAT, TSP(D). TSP(D), ExactTSP, TSPCost, TSP. Класс DP. SAT-UNSAT. Классы PNP и FPNP. MAX OUTPUT. MAX-Weight SAT. Алгоритмическая неразрешимость.


Управление информацией


1. Реляционная алгебра и реляционное исчисление.

Отображение концептуальной схемы в реляционную схему. Реализация запросов в

реляционной алгебре и в реляционном исчислении кортежей. Функциональная

зависимость и нормальные формы, денормализация реляционных схем. Влияние

нормализации на эффективность операций с базой данных, особенно на

оптимизацию запросов.

2. Оптимизация физической структуры базы данных.

Индексированные файлы и B-деревья. Файлы с плотными индексами. Файлы с

записями переменной длины. Связь между хешированием, сжатием и эффективным

поиском в базе данных. Влияние физической структуры базы данных на

эффективность транзакций. Оптимизация индексов.

3. Технологии доступа к данным в гомогенных и гетерогенных системах.

Использование стандартов ODBC, OLE DB, DAO, ADO, ADO.NET, BDE, IBX.

Взаимодействие с базами данных посредством языка Java, пакеты JDBC.

COM-объекты и современные механизмы доступа к неоднородным данным.

4. Обработка транзакций в распределенных системах.

Воздействие уровней изоляции на механизмы параллелизма. Распределенные

хранилища данных, фрагментация и репликация. Обработка распределенных

запросов, выбора стратегии, минимизирующей количество пересылаемых данных.

Модель распределенных транзакций, протокол двухфазного завершения Управление

параллелизмом на основании методов выделенной копии и метода голосования.


Комбинаторные методы сжатия данных


Информация. Количество информации. Энтропия и ее свойства. Информационный источник. Марковский источник и его энтропия.

Кодирование. Префиксное кодирование. Неравенство Крафта-Макмиллана. Коды Хаффмана, их оптимальность. Динамический алгоритм Хаффмана. Арифметическое кодирование, реализация в целочисленной арифметике.

Моделирование. Статистические (контекстные) методы сжатия. Метод PPM, его основные характеристики. Словарные методы сжатия. Семейство методов Лемпеля-Зива. Преобразование Барроуза-Уилера (BWT). Преобразование MTF. Кодирование повторов (RLE, ZLE) и расстояний (DC). Схемы сжатия данных, основанные на BWT.


Литература


  1. Ильин В. А., Позняк Э. Г. Основы математического анализа. Т. 2. М.: Наука, 1973.

  2. Натансон И. П. Теория функций вещественной переменной. М.: Наука, 1974.

  3. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: ФИЗМАТЛИТ, 2004.

  4. Стейн И., Вейс Г. Введение в гармонический анализ на евклидовых пространствах. М.: Мир, 1974.

  5. М.Гэри, Д.Джонсон. Вычислительные машины и труднорешаемые задачи. М: «Мир», 1982.

  6. C. H. Papadimitriou.  Computational complexity. Addison-Wesley Publishing Company, Reading/Menlo Park, New York, 1994.

  7. R. Niedermeier, R. Grohe. Parameterized and Exact Computation. Springer-Verlag,  New York, 2008.

  8. В.В. Семенюк. Экономное кодирование дискретной информации. СПб., изд-во СПбИТМО, 2002.

  9. Ватолин, Ратушняк, Смирнов, Юкин. Методы сжатия данных. М., Диалог-МИФИ, 2002.

  10. M. Crochemore, T. Lecroq, Text data compression algorithms. In: J.Atallah ed. Algorithms and theory of computation handbook, CRC Press, New York, 1999, Ch.12.

Похожие:

Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconУральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе
Линейные, нормированные, банаховы и гильбертовы пространства. Компактность в конкретных пространствах. Ряды Фурье, полнота, замкнутость...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconУральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе
Линейные, нормированные, банаховы и гильбертовы пространства. Компактность в конкретных пространствах. Ряды Фурье, полнота, замкнутость...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconПрограмма междисциплинарного государственного экзамена по магистерской программе
Целью экзамена является контроль выполнения требований к уровню подготовки магистрантов, завершивших обучение по магистерской программе...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconПрограмма государственного экзамена по специальности 010503 «Математическое обеспечение и администрирование информационных систем»
Гоу впо “Уральский государственный технический университет – упи” Радиотехнический институт-РтФ
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconФедеральное государственное бюджетное образовательное учреждение высшего профессионального образования «южно-уральский государственный университет» (национальный исследовательский университет)
«Южно-Уральский государственный университет» (национальный исследовательский университет) и его подразделения (далее по тексту –...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconРоссийской Федерации Государственное образовательное учреждение высшего профессионального образования «Южно-Уральский государственный университет»
Программа вступительного экзамена в магистратуру по направлению 100400. 68 – «Туризм» составлена на основе требований государственного...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconГносеологический ряд как форма взаимосвязи истины и заблуждения в индивидуальном и коллективном познании
Диссертационная работа выполнена на кафедре философии и культурологии Института по переподготовке и повышению квалификации преподавателей...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconСаратовский государственный технический университет имени Гагарина Ю. А. Современные европейские методы обучения и их применение в магистерской программе
Современные европейские методы обучения и их применение в магистерской программе «Промышленная экология» (со специализацией для Волго-Каспийского...
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconФгбоу впо «Южно-Уральский государственный университет» (национальный исследовательский университет) Юридический факультет
Регистрация будет проходить 29 марта 2013 г по адресу: г. Челябинск, Главный корпус юурГУ, пр. Ленина, 76, 2 этаж с 0900 − 1000
Уральский государственный университет им. А. М. Горького Математико-механический факультет Программа государственного экзамена по магистерской программе iconПрограмма вступительного экзамена по магистерской программе
Цели и задачи вступительного испытания: вступительное испытание проводится с целью выявления готовности абитуриентов к обучению по...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница