Темы (отчетных) докладов и рефератов

[sptsarev]

Здесь обсуждаем темы, предлагаемые для отчетных докладов (рефератов) по курсу, записываемся на конкретную тему и т.п.

[sptsarev]

Предварительный список тем для подготовки докладов для получения зачета по курсу (будет дополняться!):

• Top 10 algorithms of the 20th century
• Проблема 21 века о (не)равенстве классов сложности P и NP (P = NP ?)
• Прогресс в увеличении скорости алгоритмов (Bixby, Bertsimas & King,...)
• Теорема Рэйнгольда о сравнении множеств (Кнут, т. 3, с. 231, задача 23)
• Теорема Байеса в интерпретации результатов экспериментов
• Подборка Ваших примеров парадоксальных и полезных ситуаций в постановках задач и их ответах.

[sptsarev]

По данной теме могут представить отчет 10 слушателей, по одной из тем:

• Metropolis Algorithm for Monte Carlo
• Simplex Method for Linear Programming
• Krylov Subspace Iteration Methods
• The Decompositional Approach to Matrix Computations
• The Fortran Optimizing Compiler
• QR Algorithm for Computing Eigenvalues
• Quicksort Algorithm for Sorting
• Fast Fourier Transform
• Integer Relation Detection
• Fast Multipole Method

Цель: изложить основные идеи, на которых основан соответствующий алгоритм, пояснить его важность.

Начальный материал (2 обзорные статьи) можно взять в облаке
https://cloud.mail.ru/public/hfPP/ZvZBnHeQ9
в поддиректории Lec2-2025-01-16 > Top 10 algorithms XX century

[sptsarev]

Цель: изложить суть проблемы, пояснить ее важность, кратко обрисовать текущее состояние проблемы.

Начальный материал можно взять в Википедии
https://ru.wikipedia.org/wiki/%D0%A0%D0 ... _%D0%B8_NP
и различных обзорных статьях специалистов-математиков последних лет.

[sptsarev]

Разобрать материал по теме, обозначенной в начале второй лекции (оценки ускорения работы новых алгоритмов по сравнению со старыми версиями).

Цель: выяснить методику подсчета ускорения работы алгоритмов в области целочисленного линейного программирования, и по возможности найти сходные оценки для ускорения алгоритмов в других областях прикладной математики.

Начальный материал (статьи Bixby и др. авторов по этой теме + 2 слайда из доклада Нелли Литвак) можно взять в облаке
https://cloud.mail.ru/public/7VPt/zQoV9hMJH
в поддиректории Lec2-2025-01-16 > Нелли Литвак Bixby-et-al
Полезным будет раздел "Математика, обогнавшая компьютер" (с. 41-43) книги Нелли Литвак и Андрея Райгородского "Кому нужна математика? Понятная лекция о том, как устроен цифровой мир" (издательство "Манн, Иванов и Фербер", 2017)

[sptsarev]

В книге
Дональд Э. Кнут "Искусство программирования, том 3. Сортировка и поиск" (2-е изд., 2018)
на с. 231 имеется задача 23, упоминавшаяся на второй лекции:

Knut.png (54.92 КБ) 16172 просмотра

Данный результат формально обосновывает квадратичную сложность задачи сравнения двух множеств при условии использования лишь равенства для сравнения их элементов.
Требуется найти данный результат и пояснить основные идеи доказательства.

[Пашковская Ольга]

Добрый вечер.
Могу ли я взять тему для отчетного реферата:

Simplex Method for Linear Programming

С уважением, О.В. Пашковская

[sptsarev]

Могу ли я взять тему для отчетного реферата:
Simplex Method for Linear Programming

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

[EKarepova]

Здравствуйте!

Напишу реферат на тему "QR Algorithm for Computing Eigenvalues". На сколько я понимаю, пока она свободна.

С уважением, Евгения Карепова

[sptsarev]

QR Algorithm for Computing Eigenvalues

Хорошо, будет за Вами.