Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Для проведения запроса котировок приказом начальника УНО Администрации Вавожского района от 03.03.2009 № 35-ОД «Об утверждении состава котировочной к...полностью>>
'Реферат'
В контексте предстоящего в сентябре 2002 г. в Иоганнесбурге Всемирного саммита по устойчивому развитию («Рио+10») обсуждены новейшие данные об основны...полностью>>
'Документ'
По данным, предоставленным Министерством сельского хозяйства и продовольствия Республики Бурятия, производство алкогольной продукции в отчетном перио...полностью>>
'Документ'
Методы окисления в химической технологии БАВ 9.1. Общие положения Практическое значение реакций окисления чрезвычайно велико. В промышленности органи...полностью>>

Программа курса для студентов специальностей 1-31 03 06

Главная > Программа курса
Сохрани ссылку в одной из сетей:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

ГРОДНЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯНКИ КУПАЛЫ

УТВЕРЖДАЮ

Ректор _______________С.А.Маскевич

(подпись)

«___ » ____________________ 200 __г.

ТЕОРИЯ АЛГОРИТМОВ

ПРОГРАММА КУРСА

ДЛЯ СТУДЕНТОВ СПЕЦИАЛЬНОСТЕЙ

1-31 03 06 Экономическая кибернетика

1-31 03 03 –02 Прикладная математика

Гродно 2004

АВТОР: Статкевич С.Э., преподаватель кафедры ТФФАВ и ПМ, ГрГУ

РЕЦЕНЗЕНТЫ:

научный сотрудник ИМ НАН РБ, канд. физ.-мат. наук, Ковалевская Э.И.

канд.физ.-мат. наук, ст. преподаватель кафедры ДУ и ОУ Гончарова М.Н.

Рекомендована к утверждению кафедрой теории функций, функционального анализа, вероятностей и прикладной математики

Протокол № _10_ от «_26_» _мая_ 2004 г.

Рекомендована к утверждению методической комиссией по специальности __________

Протокол № _____ от «___» ________________________ 200__ г.

Рекомендована к утверждению Советом математического факультета

Протокол № 9 от «29 » _ июня 2004 г.

Рекомендована к утверждению Советом университета

Протокол № _____ от «___» ________________________ 200__ г.


Предисловие

Курс Теория алгоритмов читается на 2 курсе для студентов специальностей Экономическая кибернетика и Прикладная математика Цель курса:

  • ознакомить с классической теорией алгоритмов;

  • дать знания по основам теории алгоритмов, представлении данных, теории сложности;

  • обеспечить навыки в построении алгоритмов и анализе их эффективности.

Введение

Курс Теория алгоритмов содержит лекционные и лабораторные занятия. На лекциях излагаются классические вопросы теории алгоритмов, современные подходы в теории сложности, приемы построения эффективных алгоритмов. Устанавливается связь с курсами ЭВМ и программирование, Матричный анализ, Вычислительные методы алгебры, Методы численного анализа. Особое внимание уделяется практическим методам вычисления сложности алгоритмов и построению эффективных алгоритмов. На лабораторных занятиях студенты получают практические навыки по представлению данных в программе, по применению методов поиска информации.

Конструирование более мощных вычислительных систем, использующих как внутренние, так и внешние ресурсы во многих случаях позволяет обрабатывать данные простейшими подходами. Однако эффективные алгоритмы значительно экономят все вычислительные ресурсы, в том числе и время. Курс направлен на воспитание культуры применения вычислительной техники.

Содержание курса

Введение. Понятие алгоритмы. Различные модели вычислений, машина Тьюринга, машина Поста, рекурсивные функции. Уточнение понятия алгоритма и пять его параметров. Область применимости алгоритма. Конструктивные объекты. Примитивно рекурсивные функции. Операция минимизации. Нумерация n-ок. Примитивная рекурсивность сумм, произведений, оператора ограниченной рекурсии. Частично рекурсивные и общерекурсивные функции. Функция Аккермана. Диагонализация. Машина Тьюринга. Эквивалентность общерекурсивных функций и вычислений на машине Тьюринга. Примитивно рекурсивные и рекурсивные множества. Проблема останова. Основные результаты теории алгоритмов.

Понятие трудоемкости алгоритма, асимптотическая оценка роста числа операций. Вычисление оценок роста в худшем случае и в среднем. Полиномиальные и полиномиально-полные задачи. NP-трудные задачи. Примеры алгоритмов с полиномиальными и экспоненциальными оценками.

Процесс разработки алгоритма, итерация, применение рекурсии. Алгоритмы сортировки, их сложность. Дерево поиска, балансировка дерева. Динамическое программирование. Способы представления данных, зависимость сложности алгоритма от представления данных.

Алгоритмы на графах. Примеры алгоритмов с различными оценками сложности. Приближенные алгоритмы, точность, оценки сложности. Различные типы алгоритмов: точные, приближенные вероятностные, эвристические, алгоритмы реального времени.

Литература

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М:Мир, 1979.- 536 с.

Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. М:Наука, 1988.- 384 с.

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

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

Липский В. Комбинаторика для программистов. М.:Мир, 1988.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.:Мир, 1980.

Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высш. шк., 1976.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

Лекции по теории графов. В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. М.: Наука, 1990.



Скачать документ

Похожие документы:

  1. Программа курса для студентов специальности экономическая кибернетика I 31 03 06

    Программа
    В современном понимании под методами финансово-экономического управления обычно подразумеваются методы оптимизации, хотя в повседневной практике бизнес- планирования и инвестиционного проектирования часто используются понятия рациональных,
  2. Базовая учебная программа дисциплины «основы математической кибернетики» для студентов специальности 1-31 03 01 «Математика» Минск

    Программа дисциплины
    Кибернетика – наука об основных закономерностях процессов управления в сложных динамических системах способах получения, хранения, передачи и обработки информации.
  3. Программа курса для студентов По специальности 030501- "Юриспруденция"

    Программа
    Нормотворческая деятельность субъектов российской федерации : Программа курса для студентов по специальности 030501 – «Юриспруденция» / Составитель. Александрова.
  4. Программа спецкурса для специальности 1-31 03 06 «Экономическая кибернетика»

    Программа
    Курс «Применение теории массового обслуживания в экономике» предназначен для студентов 4 курса математического факультета, обучающихся по специальности «Экономическая кибернетика»
  5. Методические указания по изучению курса для студентов специальностей: 080301 «Коммерция (торговое дело)»

    Методические указания
    Финансовое право [Текст]: Методические указания по изучению курса для студентов специальностей: 080301-Коммерция (торговое дело), 080401-Товароведение и экспертиза товаров, 080 -Маркетинг, 080507-Менеджмент организации, 080505-Управление

Другие похожие документы..