Нижегородский государственный университет им. Н.И. Лобачевского Факультет вычислительной математики и кибернетики Учебно-исследовательская лаборатория «Информационные технологии» Анализ и разработка алгоритмов Таланов В.А., доц., к.ф.-м.н., кафедра МЛиВА ВМК ННГУ

Цели и задачи образовательного комплекса Изложение в едином комплексе наиболее важных теоретических и прикладных вопросов теории алгоритмов, методов анализа сложности алгоритмов и приемов и методов их эффективизации Изложение в едином комплексе наиболее важных теоретических и прикладных вопросов теории алгоритмов, методов анализа сложности алгоритмов и приемов и методов их эффективизации Знакомство с основными теоретическими моделями вычислений: словарными, числовыми, логическими Знакомство с основными теоретическими моделями вычислений: словарными, числовыми, логическими Изучение структур данных общего назначения, методов их реализации в адресуемой памяти компьютера Изучение структур данных общего назначения, методов их реализации в адресуемой памяти компьютера Анализ сложности основных операций со структурами данных общего назначения, включая математические результаты, полученные в мире в последние годы и не вошедшие в учебную литературу Анализ сложности основных операций со структурами данных общего назначения, включая математические результаты, полученные в мире в последние годы и не вошедшие в учебную литературу Знакомство с методами решения широко используемых математических задач, решаемых на основе теории графов Знакомство с методами решения широко используемых математических задач, решаемых на основе теории графов

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

Учебный материал (продолжение) Формальные языки и регулярные множества Формальные языки и регулярные множества Основы логического программирования Основы логического программирования Нетрадиционные системы счисления Нетрадиционные системы счисления Переборные алгоритмы Переборные алгоритмы Задачи, имеющие эффективные алгоритмы решения Задачи, имеющие эффективные алгоритмы решения Методы обхода графов Методы обхода графов Динамическое программирование Динамическое программирование Потоковые алгоритмы Потоковые алгоритмы

Замечание При рассмотрении вопросов связанных со структурами данных основное внимание обращается на их комбинаторные свойства и как следствие на сложность операций При рассмотрении вопросов связанных со структурами данных основное внимание обращается на их комбинаторные свойства и как следствие на сложность операций В основном рассматриваются асимптотические верхние оценки, оценки в среднем и амортизационные В основном рассматриваются асимптотические верхние оценки, оценки в среднем и амортизационные Изучаются методы получения амортизационных оценок Изучаются методы получения амортизационных оценок

Лабораторный практикум Примеры тем для лабораторных работ: Примеры тем для лабораторных работ: Нахождение кратчайших путей в графе с неотрицательными весами ребер Нахождение кратчайших путей в графе с неотрицательными весами ребер Нахождение кратчайших путей в графе методом Форда, Беллмана Нахождение кратчайших путей в графе методом Форда, Беллмана Стратегии построения остовных деревьев в графе Стратегии построения остовных деревьев в графе Пирамидальная сортировка Пирамидальная сортировка

Требования к описанию лабораторных работ Описание лабораторных работ должно содержать: Описание лабораторных работ должно содержать: Математическую постановку задачи Математическую постановку задачи Ссылки на теоретический материал, необходимый для решения поставленной задачи Ссылки на теоретический материал, необходимый для решения поставленной задачи Ссылки на необходимый инструментарий Ссылки на необходимый инструментарий Требования к предоставляемому отчету Требования к предоставляемому отчету Требования к тестированию созданного во время выполнения работы программному обеспечению Требования к тестированию созданного во время выполнения работы программному обеспечению

Требования к описанию лабораторных работ Рекомендации по проведению экспериментов и исследований. Рекомендации по проведению экспериментов и исследований. Требования к описанию выполненных экспериментальных и исследовательских работ. Требования к описанию выполненных экспериментальных и исследовательских работ. При работе со сложными исходными объектами необходимо указывать источники исходных данных или способы их генерирования При работе со сложными исходными объектами необходимо указывать источники исходных данных или способы их генерирования

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

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

Контакты Нижегородский университет Факультет вычислительной математики и кибернетики , Нижний Новгород, пр. Гагарина, 23,