4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
4. Перечень экзаменационных тем Дисциплина «Современные научные концепции... 1 111.13kb.
4. Перечень экзаменационных тем Дисциплина «Актуальные проблемы современной... 1 161.21kb.
4. Перечень экзаменационных тем I. Фундаментальные проблемы Отечественной... 1 240.61kb.
Перечень экзаменационных вопросов 1 16.4kb.
Перечень экзаменационных вопросов по дисциплине «Электронная техника» 1 24.39kb.
Зам директора цикловой комиссии специальности 1 25.63kb.
Перечень экзаменационных вопросов 1 101.88kb.
Программа предназначена для подготовки к сдаче вступительного экзамена... 5 921.97kb.
Перечень экзаменационных вопросов по дисциплине «Человеко-машинное... 1 24.36kb.
Лекция модели и их роль в создании систем. Объектная модель 1 179.36kb.
Перечень экзаменационных вопросов по уголовному процессу 1 158.96kb.
Рассмотрение подходов к реализации симулятора квантовых вычислений... 1 82.71kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность» - страница №1/1

4. Перечень экзаменационных тем
Дисциплина «Алгоритмы и их сложность»

  1. Понятие алгоритма на интуитивном уровне. Интуитивное, понятие алгоритма и его свойства. Меры эффективности алгоритма. Классы алгоритмов. Полиномиальные и экспоненциальные алгоритмы. Принципы разработки алгоритмов. Реализация и эмпирический анализ.

  2. Анализ алгоритмов. Современные методы программирования. Технологии разработки программ и их реализация. Алгоритмическая модель машины Тьюринга. Вычисление функций на машине Тьюринга. Суперпозиция машин. Соединение машин. Ветвление машин. Реализация цикла. Машины произвольного доступа (МПД) и вычислимые функции. Алгоритмическая модель МПД. Вычисление функций на МПД. Тезис Черча.

  3. Принципы построения дискретных моделей. Выбор алгоритма решения задач. Анализ устойчивости по фон Нейману. Базисные функций. Тезис Черча для частично рекурсивных функций. Вычислимость на МПД частично рекурсивных функций. Вычислимость рекурсии. Вычислимость минимизации.

  4. Особенности моделирования конвективного и диффузионного переносов. Реализация явных и неявных алгоритмов.

  5. Алгоритмически слоэюные проблемы. Построение алгоритма совместного решения системы уравнений. Особенности программирования.

  6. Характеристики сложмости вычислений. Алгоритмы решения системы уравнений .Функции временной и емкостной сложности.

  7. Нижние оценки временной сложности вычислений на машинах Тьюринга. Классы сложности и NP и их взаимосвязь. Подмножества множеств. Генерирование подмножества множеств. NP - полные задачи. Теорема Кука. Основные NP полные задачи. Сильная NP полнота. Класс co-NP. Структура классов NP и co-NP. Применение теории NP-полноты к разработке приближенных алгоритмов. Диаграмма классов сложности.

  8. Сложность алгоритмов, использующих рекурсию. Моделирование и реализация алгоритма решения двумерных задач Рекурсивный алгоритм обращения матрицы

  9. Особенности построения алгоритмов для прикладных задач фильтрации нефти.

  10. Особенности построения алгоритмов для задач с неизвестной верхней границей. Реализация алгоритмов при использовании неравномерной разностной сетки.

  11. Оптимальность вычислений. Способы оптимизации вычислений.


Список рекомендуемой литературы Основная:

  1. Кормен Томас. Алгоритмы: построение и анализ. М.: Вильяме, 2005.

  1. Computer Science for advanced level. Ray Bradley. Stansley T. publishers Ltd, 1999.

  2. M.T. Goodrich, R.Tamassia. Data structures and Algorithms in Java., Prentice Hall. 2005. - 695 p.

  3. Р.Сейджвик. Фундаментальные алгоритмы на С- СПб: ООО "ДиаСофтЮп", 2003.- 1136 с.

  4. S. Baase. Computer Algorithms. Introduction to Design and Analysis. 2n edition, Prentice Hall. 2001

  5. R. L. Graham, D.E. Knuth, O.Patashnik Concrete Mathematics, ADD- WESLEY PUBLISH. COMP., 1988

  1. J. Hastad Notes for the course advanced algorithms

  2. Абрамов С.А. Лекции о сложности алгоритмов, - М.: МЦНМО, 2009.

  1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений, -М.: МФТИ, 2007.

  2. .Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.:Мир, 1981.

П.Шурыгин В.А. Сложностный метод теории алгоритмов. - М.: ЛИБРОКОМ, 2009.

Дополнительная:

  1. Б.Я. Советов, С.А. Яковлев Моделирование систем. М.Высшая школа, 2007.

  1. Д.Андерсон, Дж.Таннехилл, Р.Плетчер Вычислительная гидромеханика и теплообмен, Мир, том 1,21990.

  1. Самарский А.А. Численные методы.М.,Мир, 1991.

  2. Мальцев А.И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.


Дисциплина «Теория распределенных систем»

1.Модели вычислений. Особенности обработки в системах с масштабируемой архитектурой. Масштабируемые параллельные системы. Общая характеристика и типы. Мультикомпыотеры. Кластеры. Вычисления и обмен данными в масштабируемых системах. Модель обмена сообщениями. Управление ресурсами в распределенных средах. Планирование вычислений в среде Grid.

2.Событийные и потоковые модели обмена сообщениями. Процессы, события, сообщения. Таксономия систем взаимодействующих процессов. Однозначность и семантика вычислений в модели обмена сообщениями. Потоковые модели распределенных вычислений.

3.Модели распределения ресурсов. Выбор целевой архитектуры. Отображение программы на ресурсы. Спецификация программы и ее представление целевой архитектурой. Критерий существования целевой архитектуры. Схема поиска частичного описания архитектуры. Начальное разбиение спецификации. Критерий существования описания архитектуры.

4.Масштабирование ресурсов и распределение вычислений. Модели планирования и распределения вычислений. Основные компоненты моделей масштабирования. Стратегии планирования процессов и распределения ресурсов. Модельные примеры поиска оптимальных стратегий вычислений.

5.Программирование с разделяемыми переменными. Процессы и синхронизация. Распределенное программирование. Передача сообщений. Удаленный вызов процедур и рандеву. Модели взаимодействия процессов. Реализация языковых механизмов. Синхронное параллельное программирование. Языки, компиляторы, библиотеки и инструментальные средства.



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

  2. Примеры технологии распределенных вычислений. Особенности технологий СОМ, ACTIVEX, DCOM, CORBA. и др. Локальные и глобальные информационные сети. Интеллектуальные сети. Мультиагентные системы. Информационная образовательная сеть

Основная и дополнительная литература

  1. Аветисян Р.Д., Аветисян Д.Д., Теоретические основы информатики. - М.: Наука, 1997.

  2. Топорков В. В. Модели распределенных вычислений. — М. ФИЗМАТЛИТ, 2004. — 320 с, - ISBN 5-9221-0495-0.

  1. Эндрюс ГР. Основы многопоточного, параллельного и распределенного программирования. Пер. с англ. — М.: Издательский дом "Вильяме", 2003. — 512 с: ил. — Парал. тит. англ.

  2. Фуфаев Э.В., Фуфаев Д.Э. Разработка и эксплуатация удаленных баз данных: учебник для студ. сред., проф. Образования - М.Издательский цетр «Академия», 2008г. -256с.

  3. Э. Таненбаум, М.ван Стен. - СПб.: Питер, 2003. - 877с: - (Серия «Классика computer science»).

  4. Дж. Причард, "СОМ и CORBA. Просто и доступно". Изд - Лори, 2001г. -384с.

  5. Камерон Хыоз, Трейси Хьюз. Параллельное и распределенное программирование с использованием C++. Пер. с англ. — М.: Издательский дом "Вильяме", 2004. — 672 с: ил.—Парал. тит. англ.

  6. Коваленко В., Коваленко Е., Корягин Д. и др. Управлениями в распределенной вычислительной среде // Открытые системы.-2001.- №5-6.

  7. Коноваловы., Крюкова В. Параллельные программы для вычислительных кластеров и сетей. // Открытые системы. - 2002. - №12-18.

  8. Фостер Я., Кессельман К., ТьюксС. Grid - службы для интеграции распределенных систем // Открытые системы. - 2003. - №1.

  9. Барский А.Б. Параллельные процессы в вычислительных системах . Планирование и организация. - М.:Радио и связь, 1990. - 256с.

  10. Бочаров Н.В. Технология и техника параллельного программирования // Программирование. - 2003. -№1.

  11. Понамарев В. СОМ и ACTIVEX в Delphi. - СПб.: БХВ-Петербург, 2001

  12. Елманова Н. Delphi. COM - технология - Спб.: Питер, 2002

  13. Воеводин В.В., Воеводин Вл.В. Параллельный вычисления. - СПб.:БХВ-Петербург, 2002. -606с.

  14. Шураков В.В. Надежность программного обеспечения систем обработки данных: Учеб.-2-е изд., перераб. и доп.-М.: Финансы и статистика, 1987.

  15. Фостер Дж. Автоматический синтаксический анализ: Пер. с англ,-М. Мир, 1975.

  16. Хоггер К. Введение в логическое программирование: Пер. с англ,-М.:Мир,1988.

  17. Вирт Н. Алгоритмы+структуры данных = программы, -М.: Мир, 1985.


Дисциплина «Технологии разработки программного обеспечения»

1. Процесс разработки программного обеспечения. Обзор современных технологий разработки программного обеспечения. Организация процесса разработки программного обеспечения. Управление проектом. Выявление и уменьшение рисков. Инструментальные средства разработки и поддержки.

2. Требования и архитектура программного обеспечения. Анализ требований. Описание требований. Добавление детальных требований. Архитектура программного обеспечения. Типы архитектур и их модели.

3. Проектирование программных систем. Основы проектирования программных систем. Особенности процесса синтеза программных систем. Особенности этапа проектирования. Классические методы проектирования.

4. Тестирование программного обеспечния. Принципы тестирования программного обеспечения. Структурное тестирование программного обеспечения. Функциональное тестирование программного обеспечения. Организация процесса тестирования программного обеспечения. Методика тестирования программных систем. Системное тестирование.

5. Объектно-ориентированные программные системы. Разработка пользовательского интерфейса различных программных систем и требования к проектированию интерфейса. Основы объектно-ориентированного представления программных систем. Базис языка визуального моделирования. Статические модели объектно-ориентированных программных систем. Динамические модели объектно-ориентированных программных систем. Модели реализации объектно-ориентированных программных систем. Метрики объектно-ориентированных программных систем. Унифицированный процесс разработки объектно-ориентированных программных систем.


Список рекомендуемой литературы

Основная литература:

  1. Орлов С.А. Технологии разработки программного обеспечения. СПб.: Питер, 2002. 464с.

  2. Кокарева Е.В.. Гагарина Л.Г., Виснадул Б.Д, Технологии разработки программного обеспечения. ИНФРА-М, издательский дом Форум, 2008г.

  3. Брауде Э. Технологии разработки программного обеспечения. СПб.: Питер, 2004.

  4. Сергушичева А.П. Технология разработки программного обеспечения: Методические указания к выполнению лабораторной работы №4 «Применение CASE-средст при разработке программного обеспечения». - Вологда: ВоГТУ, 2007.

Дополнительная литература:

  1. Орлов С.А. Принципы объектно-ориентированного и параллельного программирования на языке Ада95. Рига: TSI, 2001.

  2. Ambler S.W. The object Primer. 2nd ed. Cambrige University Press, 2001.

  3. Beck K., Fowler M. Planning Extreme Programmong. Addison-Wesley, 2001.

  4. Bohm D.W. etal. Software Cost Estimation with Cocomo II. Prentice Hall, 2001.

  5. Cockburn A. Agile Software Development. Addison-Wesley, 2001.

  6. Fowler M. The new Methodology http://www.martinfowler.com, 2001.