Sergey Khashin's PhD and Master students
Back to the main page

      2012       2011       2010       2009       2008
      2007       2006       2005       2004       2003
      2002       2001       2000       1999       1998       1997

Предлагаемые темы дипломных работ.
(Этот файл - только для студентов математического факультета ИвГУ)
(This file only for students of math.dep. IvGU)

Every year I accept students interested in projects related to Numerical Algorithms, Number Theory, Computer Craphics.
Please contact me by email.

In 1997-2012 I have had 57 Master students, 2 PhD students.

International students

My Russian students

Complete List of My Students Since 1997 (in Russian)

      2012       2011       2010       2009       2008
      2007       2006       2005       2004       2003
      2002       2001       2000       1999       1998       1997

2012 год.

• Виноградова Н.Н. Магистерская диссертация Алгебры Бутчера малых размерностией

  В последние годы для решения уравнений Бутчера появился новый метод, основанный на изучении цепочки подпространств (фильтрации) Lk, Mk в Rn+1 и изучении возникающих при этом алгебраических структур.

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

  Магистерская диссертация Виноградовой Н.Н. посвящена изучению размерностей этих подпространств для исходной матрицы небольшого размера (до 4*4 включительно).
  
  

• Арефьева С.П. Дипломная работа Методы Рунге-Кутты седьмого порядка.

  Дипломная работа Арефьевой С.П. посвящена решению одной конкретной системы полиномиальных уравнений – системе Бутчера для нахождения методов Рунге-Кутта порядка 7. Систем имеет очень большой размер (она полностью приведена в приложении, занимает несколько десятков страниц).

  К сожалению, никакие стандартные методы решения систем полиномиальных уравнений для этой системы не подходят (в основном из-за её размера). Поэтому приходится изобретать какие-то нестандартные подходы. Именно этому и посвящена работа.

  Переменные, от которых зависят уравнения естественным образом разбиваются на все группы: c[2],..c[8] и a[i,j] (28 штук) и b[i] (6 штук).

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

• Абалина Е.А. Дипломная работа Проверка чисел на простоту с помощью метода Лукаса-Лемера

  Дипломная работа Абалиной Е.А. посвящена исследованию одного из методов вероятностной проверки чисел на простоту (метода Лукаса-Лемера). Этот метод используется, например, совместно с методом Миллера-Рабина в стандартной библиотеке языка Java (но, почему-то, лишь для чисел больших 2100).

  Первая задача, стоявшая перед студенткой – разобраться в исходных кодах стандартной библиотеки языка Java, реализующих этот метод и реализовать его для автономной работы (не в составе других методов).

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

  И, наконец, убедиться, что среди всех рассмотренных примеров нет ни одного, на котором ошибались бы оба метода (Лукаса-Лемера и Миллера-Рабина).
  
  

• Зотикова Е.С. Дипломная работа "Симметричные функции в Maple для латинских квадратов".

  В настоящее время существует несколько различных инвариантов латинских квадратов, то есть некоторых объектов, вычисляемых через элементы латинского квадрата и не меняющихся при перестановках строк, столбцов и перенумерации элемнтов.

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

  Инвариант получается достаточно интересным. Например, для среди различных 20-ти неэквивалентных квадратов размера 6*6 для части из них он оказывается равным 0, а для остальных – отличен от нуля.
  
  

• Овчинникова О.В. Дипломная работа "Обработка изображений"

  Дипломная работа Овчинниковой О.В. посвящена разработке и реализации алгоритма удаления темных линий (царапины, провода на фотографии) на изображении.

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

  Практическая часть работы представляет собой попытку реализации рассмотренного алгоритма на языке С++ (Dev C++).
  
  

• Павлычева Е.A. Дипломная работа Проверка чисел на простоту с помощью метода Миллера - Рабина.

  Дипломная работа Павлычевой Е.А. посвящена исследованию наиболее распространенного метода вероятностной проверки чисел на простоту: метода Миллера-Рабина. Этот метод используется, например, в стандартной библиотеке языка Java. Хотя метод достаточно прост с математической точки зрения, нахождение составных чисел, на которых метод ошибается довольно трудоемко.

  Перед студенткой была поставлена задача найти способ нахождения таких "ошибочных" чисел, существенно более быстрый, чем прямой перебор. Вторя задача –убедиться, что среди всех рассмотренных примеров нет ни одного, на котором ошибались бы оба метода (Лукаса-Лемера и Миллера-Рабина).
  
  

2011 год.

• Мартынова Е.А. Магистерская диссертация "Методы Рунге-Кутты порядка 6"

  Методы Рунге-Кутты изучаются давно и вплоть до настоящего времени. Методы порядка 4 получены еще в начале 20 века, методы порядка 5 и 6 – в 60-х годах в основном в работах Дж.Бутчера. Им были найдены некоторые многообразия решений для этих порядков.

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

  Доведение этих алгоритмов до вида, пригодного для реализации на компьютере (и сама реализация) для методов порядка 6 и являлась задачей студентки.
  
  

• Бадалов А.Н. Магистерская диссертация "Сегментация изображения"

  Работа посвящена разработке алгоритма сегментации, основанного на яркости точек изображения.

  Сегментация изображений – важная задача компьютерной графики. Ей посвящено много статей. Разработано много различных алгоритмов. Однако реализация практически всех из них недоступна. Поэтому самостоятельная реализация студентом даже не очень сложного алгоритма представляем значительный интерес.

  Студентом разработана и отлажена программа на языке С++ (Visual Studio Express - 2010) сегментирующая любое заданное изображение по описанному им алгоритму. Проведено численное сравнение качества этого алгоритма с другими алгоритмами сегментации.
  
  

• Белкин Д.О. Магистерская диссертация "Классификация ортогональных латинских квадратов порядка 7х7"

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

  Количество латинских квадратов (и, тем более пар) быстро растет с ростом их размера. Количество классов эквивалентности тоже растет, но гораздо медленнее.

  Классы эквивалентности хорошо изучены при n <= 6. При n=7 и более имеются лишь частичные результаты.

  В работе делается попытка изучить некоторый новый инвариант (по отношению эквивалентности) латинских квадратов, найти его свойства, проверить, насколько точно он описывает классы эквивалентности.
  
  

• Крюченкова Т.С. Дипломная работа "Исследование множества Мандельброта с расширенной точностью"

  Множество Мандельброта – хорошо известный в компьютерной графике объект. Десятки, а может быть и сотни тысяч людей во всем мире реализовывали программы, рисующие эти картинки. Имеются реализации на всевозможных языках, однако, практически все они используют для расчетов встроенные типы плавающих чисел: float, double, extended. Задача является вычислительно очень громоздкой, требует очень большого объема вычислений. Поэтому даже со встроенными плавающими числами время построения одной картинки – секунды или десятки секунд. Но если мы попытаемся рассмотреть достаточно глубокие подробности, то точности обеспечиваемой встроенными числами будет недостаточно. Разумеется, мы можем обратиться к числам большой точности, реализованным программно (BigDecimal in Java, библиотека GMP в C++ и многие другие). Но скорость вычислений при этом радикально падает: время ожидание очередной картинки будет уже измеряться часами, что совершенно неприемлемо для интерактивной программы.

  Можно уверенно предполагать, что большинство программистов, строивших множество Мандельброта (а это – тысячи людей!) хотели бы построить его с большой точностью за приемлемое время, но никто не смог. А мы смогли!
  
  

2010 год.

• Зуева В.Ю. Магистерская диссертация "Обработка и кодирование черно-белых изображений"

  Зуевой В.Ю. была предложена для работы довольно сложная тема: разработка алгоритма сжатия двуцветных изображений. Общая цель – достигнуть, а если удастся, то и превзойти по уровню сжатия формат «CCITT Fax 4», применяемый, например, в стандарте TIFF.

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

  Программа может выдавать сжатый файл как в текстовом виде, так и в двоичном, так и путем сжатия с помощью библиотеки bzip2.

  К сожалению, набранная статистика не позволяет однозначно сравнить рассматриваемый алгоритм с наилучшим на сегодняшний день в этой области: «CCITT Fax 4».
  
  

• Логинова М.Ф. Магистерская диссертация "Поиск кратчайшей кривой фиксированного порядка, проходящей через данные точки." В работе рассмотрены с математической точки зрения и реализованы на языке С++ три различных алгоритма:

  - Нахождение дуги гладкой кривой,
  - Нахождение семейства кривых, проходящих через данные точки,
  - Минимизация функции.
  

  Реализован удобный графический интерфейс.
  
  

• Пелевина С.С. Магистерская диссертация "Многомерный метод секущих"

  Для численного решения систем уравнений обычно применяется метод Ньютона. Однако, в одномерном случае можно воспользоваться и методом секущих. В многомерном случае этот метод практически не используется. Причина – в его неустойчивости.

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

  В работе построена такая стабилизация, и проверены ее свойства на нескольких примерах. Для этого написана программа (на языке Паскаль), находящая решения системы двух уравнений от двух переменных модифицированным методом секущих.
  
  

• Погодаева Е.В. Магистерская диссертация "Исследование вырожденности систем уравнений для нахождения методов Рунге-Кутты высоких порядков".

  При численном нахождении методов Рунге-Кутта высокого порядка возникает проблема, связанная с плохой и очень плохой сходимостью метода Ньютона для системы полиномиальных уравнений. Очевидно, причиной такой плохой сходимости является вырожденность искомых решений. В целом, понятно, что так должно быть, но так ли это на самом деле – пока не проверено.

  Перед студенткой была поставлена задача проверить вырожденность (или невырожденность) некоторых известных семейств методов Рунге-Кутта.

  До конца, в общем виде, это удалось проверить лишь для методов 4-го порядка, а в остальных случаях – лишь на примерах.

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

• Забанова Е.В. Дипломная работа "Вложенные формулы Рунге-Кутты".

  В дипломной работе рассматривается важный класс методов Рунге-Кутты, а именно – вложенные формулы, позволяющие контролировать погрешность вычислений на текущем шаге. Полные вложенные формулы, позволяющие найти текущую погрешность с хорошей точностью удается построить в редких случаях. В настоящей же работе строятся примеры «ослабленных» вложенных формул для порядков 4 и 5, которые дают погрешность лишь «с точностью до умножения на константу». Однако, с точки зрения вычислений, и такие «ослабленные» формулы могут иметь практический смысл.

  Формулы 4-го порядка были найдены еще на 4-м курсе и являются известными. Формулы же для метода 5-го порядка в таком виде в литературе не встречаются (хотя имеются некоторые их аналоги). К сожалению, не удалось получить формулы в общем виде, а найден лишь один конкретный пример, доведенный до конца и еще один пример, законченный лишь «в основном».

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

• Косоурова Ю.А. Дипломная работа "Достаточные условия отсутствия минимумов биквадратичной функции на единичном квадрате".

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

  Поскольку задача – массовая (для одного изображения ее требуется решать сотни тысяч раз), и в подавляющем большинстве случаев ответ – отрицаетльный (нет минимумов) то проблема не только в поиске самих минимумов, но и в получении достаточно эффективных критериев их отсутствия.

  Заслугой студентки является не только доказательство, но и точна формулировка самих критериев.

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

• Прохорова Н.Ю. Дипломная работа "Двумерный метод секущих".

  Для численного решения систем уравнений обычно применяется метод Ньютона. Однако, в одномерном случае можно воспользоваться и методом секущих. В многомерном случае этот метод практически не используется. Причина – в его неустойчивости.

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

  В дипломной работе изучен двумерный метод секущих, разработан алгоритм и на его основе написана программа (на языке Паскаль), находящая решения системы двух уравнений от двух переменных.

  Исследована сходимость метода в окрестности простого и вырожденного решений.

  Разработанная программа наглядно демонстрирует недостаточную устойчивость метода.
  
  

• Шмыглёв П.В. Дипломная работа "Линейные подсистемы систем уравнений".
  При нахождении методов Рунге-Кутта высокого порядка, требуется решать систему уравнений Бутчера. Это система из нескольких десятков и даже сотен полиномиальных уравнений от нескольких десятков переменных. Разумеется, решать такую систему трудно, как аналитически, так и численно.
  Эта системы уравнений (и многие другие) имеют важную особенность: очень многие переменные входят в отдельные уравнения лишь линейно. То есть их можно выразить через остальные и это выражение подставить в другие уравнения. Формализация этого алгоритма, применение его к ситуации, когда уравнения заданы не аналитически, а лишь в виде некоторых функций, и составила предмет данной работы.
  Результатом является работающая программа (на языке Паскаль), находящая максимальную линейную подсистему (или подсистемы, если их много) данной системы уравнений.
  

2009 год.

• Великодный В.В. Магистерская диссертация "Исследование существования нулей бикубической функции на единичном квадрате".

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

  Перед студентом была поставлена задача: найти легко проверяемый критерий отсутствия нулей бикубической функции на единичном квадрате.

2008 год.

• Куриземба А.А. Дипломная работа "Оценка погрешности методов Рунге - Кутта".

  Данная работа посвящена нахождению «вложенных» методов Рунге-Кутта для численного решения обыкновенных дифференциальных уравнений. Их отличие от обычных состоит в том, что они позволяют на каждом шагу контролировать текущую погрешность, что, в свою очередь позволяет оперативно управлять величиной шага. В реальных ситуациях величина шага может изменяться по ходу вычислений в десятки и даже сотни раз, что дает соответствующий выигрыш в объеме вычислений.

  В этом направлении удалось сделать лишь самый первый шаг, а именно, для классических 4-х стадийных методов порядка 4 найти вложенную формулу, позволяющую оценить погрешность вычислений. К сожалению, оказалось, что порядок вложенной формулы не может быть 5 и даже 4, а только 3. Это несколько снижает точность оценки погрешности, но тем не менее полученные формулы можно использовать для автоматической коррекции величины шага по ходу расчетов.
  
  

• Куваев П.Е. Дипломная работа "Разработка системы управления сайтом (CMS)".

  Представленная дипломная работа посвящена очень интересной и практически важной теме – разработке систем построения сайтов.

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

• Осина С.Г. Магистерская диссертация "Нестандартные методы Рунге-Кутты порядка 5".

  Магистерская диссертация Осиной С.Г. состоит из двух частей. В первой аналитически находится некоторое семейство методов Рунге-Кутты порядка 5. Совместная статья опубликована в журнале «Математика и ее приложения».

  Во второй производится сравнение эффективности различных методов из одного семейства. Для этого была написана Паскаль-программа, находящая среднюю погрешность каждого метода на некотором, достаточно большом наборе примеров систем уравнений (несколько сотен примеров).
  
  

2006 год.

• Конопелько Е.А. Магистерская диссертация "Минимум биквадратичной функции двух переменных".

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

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

  Доказывается (теорема на стр.9), что количество локальных минимумов не превышает 3. На самом деле доказывается несколько более сильное утверждение, в котором количество локальных минимумов и максимумов ограничивается более точно, в зависимости от определенных соотношений между коэффициентами.

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

• Корникова А.А. Магистерская диссертация "Интерполирование функции двух переменных с учётом границ объекта".

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

  Для построения нелинейных формул требуется разбить исходное изображение некоторыми линиями («границами») на отдельные области. При интерполяции должны учитываться не все точки из выбранной окрестности, а лишь те, что не выходят за границы области. Поэтому первая цель при построении интерполяционной формулы – определение границ объектов на изображении. На самом деле, границы у нас должны состоять не из отдельных точек («дискретная граница»), а быть непрерывными линиями.

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

  Центральным результатом работы является построение линейной 16-точечной интерполяционной формулы, дающей результат класса C2, то функция имеет непрерывные вторые производные (§5). Благодаря этому, оказалось возможным определить понятие «границы» в виде непрерывной линии.
  
  

• Колесова Н.Г. Дипломная работа "Определение границ объектов на изображении".

  В прошлом году была защищена магистерская диссертация (Ремизовой Е.А.) на родственную тему.

  В диссертации Ремизовой были рассмотрены различные методы преобразования серого текста к черно-белому виду. Но некоторые подходы остались не исследованными. Дипломная работа Колесовой Н.В. как раз и исследует возможности одного их этих подходов, а именно – метод, основанный на выделении границ на изображении.

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

  Программа, описанная в работе реализована в системе программирования Delphi.

  Работа выполнена самостоятельно. При реализации данной работы студентке пришлось не только освоить систему Delphi, но и некоторые пакеты работы с компьютерной графикой.
  
  

• Шастин В.Н. Дипломная работа "Оптимизация восстановления изображения".

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

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

  Перед студентом была поставлена задача – исследовать устойчивость введенного таким образом показателя качества алгоритма на максимальном широком классе изображений.

  Работа выполнена с использованием среды программирования Delphi.

  Основными результаты, полученные в работе следующие.

  1. Предложен свой алгоритм увеличения изображения: комбинация базового алгоритма с некоторым вариантом фильтра повышения резкости, качество алгоритма = 90.59±1.46%. Хотя в чистом виде он вряд ли сможет конкури-ровать с наиболее сложными алгоритмами, но методы, в нем применен-ные могут служить хорошим дополнением к другим алгоритмам.

  2. На основе проведенных экспериментов сделан вывод, что качество алгоритма может быть измерено с точность 1..1.5%.

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

  Не все предложенные методы оказались эффективными. Например, алгоритма, названный автором «secondStep» оказался даже заметно хуже базового. Но отрицательный результат – то же результат.
  
  

2005 год.

• Галанина Е.Е. Магистерская диссертация "Распознавание тематики текста".

  Основная цель, поставленная перед студенткой – исследование различных эвристических алгоритмов распознавания тематики текста. Базовый метод – сравнение со словарем, построенным в процессе обучения системы. То, что метод «базовый», предполагает, что у него имеется большое число модификаций, влияющих на его работу и конечный результат. Работа как раз и должна была показать эффективность (или неэффективность) различных модификаций.

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

  В процессе работы Галаниной Е.Е. пришлось изучить общие прин-ципы работы нейронных сетей а так же некоторые конкретный алгоритмы родственной тематики (проект «проекта SemLP», диссертация на тему «Модель структурного представления текстовой информации и метод ее тематического анализа на основе частотно-контекстной классификации» (С.-Пб. Ун-т),.а также дипломную работу Корольковой Е.В. (ИвГУ, 2003 г.).

  Для сравнение различных модификаций алгоритма, была предложена количественная оценка качества его работы. Результаты оказались довольно неожиданными, многие из предложенных ранее улучшений и модификаций алгоритма себя не оправдали. Некоторые обнаруженные статистические закономерности в частотном словаре показали возмож-ность значительного сокращения его объема (сейчас размер словаря составляет десятки мегабайт).
  
  

• Ремизова Е.В. Магистерская диссертация "Преобразование изображений в черно-белый вид".

  Преобразование из изображения из 24-битного цвета в 1-битовый формат – часто встречающаяся задача. Разумеется, применять ее надо не к произвольным изображениям а, чаще всего, - к отсканированным (или сфотографированным) текстам.

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

  В магистерской диссертации предложен алгоритм, успешно справляющийся с этими проблемами. Кроме того, рассмотрены (и решены) некоторые чисто математические проблемы, появляющиеся при по-строении алгоритма (теорема о несуществовании интерполяционной формулы определенного вида, и теорема о свойствах другой интерполяционной формулы.
  
  

• Митрофанова М.К. Дипломная работа "Каноническая форма биквадратного многочлена".

  При решении некоторых задач компьютерной графики возникает задача минимизации функции, являющейся биквадратичной по своим аргументам (x,y). Полностью аналитического решения эта задача не имеет. Для эффективного численного решения требуется более детальное исследование минимизируемой функции, в частности приведение ее к простейшему виду путем подходящего выбора системы координат. Эта задача и была решена дипломницей.

  Одной из существенных проблем, с которой пришлось столкнуться – большое количество различных частных случаев (свыше 20). Многие из них сравнительно простые, однако для полного, строго решения поставленной задачи их так же необходимо было рассмотрет.

2004 год.

• АССЮЙ Куасси Ришар. Диссертация на соискание ученой степени кандидата физико-математических наук "Исследование и сравнение методов Рунге-Кутта высокого порядка"

  Сейчас он - профессор математики в Университете в Кот-д’Ивуаре (Prof. ASSUI Kouassi Richard Maitre de Conferences Departement Mathematiques et Informatique Institut National Polytechnique FHB BP 1093 Yamoussoukro, COTE D'IVOIRE)

  Цель работы построение методов типа Рунге-Кутта высоких (6, 7, 8) порядков. Разработка как аналитических, так и численных методов их получения. Исследование точности найденных методов, сравнение различных методов между собой, нахождение локальной размерности многообразия решений.

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

  Для проведения численных расчетов разработана программа, позволяющая численно находить методы Рунге-Кутта. Хотя для нахождения методов высоких порядков она требует много процессорного времени (часы и даже десятки часов), она позволила получить интересные результаты.

• Тараканова Е.М. Магистерская диссертация " Аналитическое исследование алгоритма Лукаса-Канады".

  Представленная магистерская диссертация состоит из теоретической и практической частей. В теоретической части описываются алгоритм Лукаса-Канады, предназначенный для нахождения векторного поля движения между двумя похожими кадрами.

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

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

  В п.3.9 работы доказывается теорема, в принципе, позволяющая аналитически находить поле движения в единичном квадрате, точнее говоря сводящая задачу к решению уравнения 5-й степени от одной переменной.
  
  

• Петрова К.В. Магистерская диссертация "Семишаговые методы Рунге-Кутта порядка 6".

  Магистерская диссертация Петровой К.В. состоит из введения, трех глав, заключения и приложений. В первой главе приводятся основные сведения о методах Рунге-Кутта, вводятся обозначения. Во второй главе рассматриваются уравнения Бутчера для коэффициентов метода Рунге-Кутта. Наконец, в третьей главе рассматривается «каркас» уравнений Бутчера как в общем виде, так и для 7-стадийных методов 6-го порядка.

  Основные результаты, полученные в работе изложены в §3.4. «Выбор свободных переменных для решения каркасной системы». Здесь рассматривается несколько вариантов выбора свободных переменных для данной системы, часть из них оказывается неудобной для получения аналитического решения. Среди нескольких оставшихся вариантов один обладает дополнительной симметрией, он и признается оптимальным.
  
  

• Корхов А.А. Магистерская диссертация "Нахождение оптимальной коррекции цвета".

  В магистерской диссертации Корхова А.Е. решается задача коррекции цвета изображения. Соответствующие функции имеются в каждом графическом редакторе, но, судя по всему, их недостаточно. В рецензи-руемой работе предлагается другой подход к этой проблеме.

  В главе 2 «Решение», предлагаются 10 различных методов цветовой коррекции. Среди них есть и совсем простые (растяжение или сдвиг), и более сложные, типа метода, основанного на интерполяционных многочленах Лагранжа или на кусочно-аффинных преобразованиях. В главе 3 (одна страница) еще раз перечисляются эти методы и делается попытка охарактеризовать их качество.

  В главе 4 делается попытка математически обосновать применимость метода наименьших квадратов для «ограниченно-линейных» функций. Доказывается, что в некотором классе задач стандартный метод наименьших квадратов применим и к рассматриваемой задаче.
  
  

• Устинова С.В. Дипломная работа "Сравнение методов Рунге-Кутта".

  На сегодняшний день известно большое количество методов Рунге-Кутта, полученных как аналитически, то есть точно, и численно, то есть приближенно. Их практическая ценность весьма различна. В дипломной работе Устиновой С.В. предпринята попытка сравнить между собой эффективность различных методов.

  Дипломницей была реализована программа решения системы диф-ференциальных уравнений методом Рунге-Кутта. Основное отличие от других аналогичных программ состоит в том, что используемый метод не является частью программы, а берется из внешнего (текстового) файла. Таким образом, эту программу можно использовать для сравнения между собой эффективности различных методов Рунге-Кутта, что и про-делано в дипломной работе.
  
  

• Мухина А.Г. Дипломная работа "Сходимость метода Ньютона в окрестности вырожденной точки".

  Невырожденные корни как одного уравнения, так и системы уравнений с помощью метода Ньютона находятся сравнительно просто, ко-личество требуемых шагов минимально: 2-3 шага после попадания в окрестность корня. Переход от точного значения производной к приближенному практически ничего не меняет – процесс сходится так же быстро.

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

  Целью дипломной работы и являлось проверка сходимости метода в этом случае.
  
  

• Плохотнюк Н.А. Дипломная работа "Исследование методов проверки числа на простоту".

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

  Для реализации поставленной задачи пришлось не только изучить язык Java и написать на нем программу, но и разобраться в достаточно сложных математических методах, используемых для проверки чисел на простоту. Кроме этого, пришлось разработать эффективный способ получения чисел Кармайка размером до 25-27 десятичных знаков.
  
  

2003 год.

• Шашина О.А. Магистерская диссертация "Псевдопростые числа, не являющиеся простыми".

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

  Перед Шашиной О.А. была поставлена задача - найти минимальные числа, на которых некоторые алгоритмы проверки числа на простоту дают ошибочный ответ.

  В процессе работы были получены определенные продвижения в этом направлении, хотя и не все поставленные цели достигнуты.
  
  

• Халистова О.В. Магистерская диссертация "Нахождение длины дуги гладкой кривой".

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

  В тоже время кривые Безье имеют и некоторые недостатки, один из которых - через чур большая степень получающейся кривой.

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

• Ларионова Е.А. Магистерская диссертация "Неклассические методы Рунге-Кутта порядка 6".

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

  В диссертации Ларионовой Е.А находится для некоторых наиболее важных случаев решение "каркаса" системы Бутчера для методов Рунге-Кутта порядка 6. Решению системы Бутчера для этого порядка посвящено много работ. Поэтому решения, найденные в дипломной работе могут быть проверены с разных точек зрения, а так же использованы для нахождения решений полной системы Бутчера.

  В процессе подготовки работы автору пришлось освоить не только способы нахождения методов Рунге-Кутта, но и систему компьютерной алгебры Maple.
  
  

• Щетникова Е.С. Дипломная работа "Справочные материалы по элементарной математике для оn-line тестов на сайте Математического факультета".

  В дипломной работе Щетниковой Е.С. сделана попытка разработать справочную систему по некоторым разделам по элементарной математики. Система предназначалась для включения в on-line тесты, расположенные на сайте факультета.

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

• Смирнова С.М. Дипломная работа "Каркас методов Рунге-Кутта порядка 7"

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

  В диссертации Смирновой С.М. исследуется в отдельных случаях каркас системы уравнений Бутчера для методов Рунге-Кутта порядка 7. А именно, предполагается, что как можно большее количество коэффициентов среди bi равно 0. Оказывается, что двух ненулевых коэффициентов недостаточно, для того, чтобы каркас системы имел решение. Трех же ненулевых коэффициентов уже достаточно.

  Таким образом, основным содержанием работы является решение каркаса системы Бутчера для методов Рунге-Кутта порядка 7, в случае трех ненулевых коэффициентов bi. Аналитически решение удалось продвинуть довольно далеко, но не до самого конца. Однако, окончательные решения удалось все-таки получить приближенно (с любым количеством знаков после запятой).
  
  

• Королькова Е.В. Дипломная работа "Автоматическое определение тематики текста".

  Учитывая все возрастающий поток поступающей к нам информации, ее систематизация становится все более актуальной задачей. Обычно такая процедура выполняется вручную — мы просто смотрим каждый имеющийся текст и сами определяем, в какой каталог его положить. Конечно, обработать 2-3 или даже 10-15 текстов не так уж сложно. Но разложить по каталогам 10-15 тысяч различных файлов уже не просто. Естественно, хотелось бы автоматизировать этот процесс.

  В полном объеме это, разумеется, не возможно, но в отдельных ситуациях можно надеяться на успех.

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

  В качестве обучающего материала были взяты тексты известной коллекции "Библиотека в кармане" 15 выпуск — свыше 10 тысяч текстов общим объемом почти 1.5Г байт.
  
  

• Виноградова И.В. Дипломная работа "Неклассические методы Рунге-Кутта порядка 5".

  Задача нахождения методов Рунге-Кутта высокого порядка до сих пор не имеет удовлетворительного решения, даже в численном виде. В связи с этим можно попытаться найти решение системы уравнений Бутчера в двух (или более) ступенчатом виде, а именно - выделить некоторую часть переменных и уравнений ("каркас" системы) и на первом этапе решить эту упрощенную систему уравнений.

  В дипломной работе Виноградовой И. эта задача полностью решена для случая методов Рунге-Кутта порядка 5. Основным результатом работы является установление того факта, что каждому решению каркасной системы соответствует ровно одно решение полной системы уравнений Бутчера, что служит подтверждением обоснованности введения понятия "каркаса".
  
  

2002 год.

• Пустакова Н.А. Дипломная работа "Интерполяционные формулы от 2-х переменных".

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

  На сегодняшний день для двух переменных используются в основном "прямоугольные" интерполяционные формулы, то есть декартово произведение интерполяционных формул от 1-й переменной - билинейная, биквадратная и бикубическая интерполяция. В литературе можно найти упоминание "треугольных" интерполяционных формул.

  Есть основания полагать, что оба этих типа интерполяционных формул не являются оптимальными при использовании в компьютерной графике. Дипломная работа Пустаковой Н.А. посвящена нахождению трех новых интерполяционных формул, построенных на 12, 16 и 24 точках.
  
  

• Малышева И.В. Дипломная работа "Оценка качества интерполяционных формул от 2-х переменных".

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

  На сегодняшний день существует довольно много таких формул. Выбор той или иной формулы в каждом конкретном случае основывается на общих соображениях (более высокий порядок формулы обеспечивает большую точность, но черезчур высокий порядок лишь ухудшает результат) и вкусах разработчика. В дипломной работе делается попытка найти объективные критерии сравнения различных интерполяционных формул для таблично заданных функций от двух переменных.

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

2001 год.

• Коровкина Н.В. Магистерская диссертация "Эвристическое сравнение текстов".

  Эвристическими называются алгоритмы, не имеющие законченной формулировки, чаще всего даже сама цель не может быть сформулирована в точном математическом смысле. В данной работе как раз и рассматривается такой алгоритм. Наша цель - проверить, не содержат ли два файла один и тот же текст, различающийся лишь несущественными деталями.

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

• Сергеева С.Н. Дипломная работа "5-мерное семейство 6-ти шаговых методов Рунге-Кутта порядка 5".

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

  Нахождение конкретных методов РК сводится к решению большой системы полиномиальных уравнений, решить которую в общем виде не удается до сих пор.

  6-ти шаговые методы Рунге-Кутта порядка 5 полностью описаны в "общем виде" то есть выбраны некоторые "свободные" переменные и имеется способ выразить все остальные через них. В "общем виде" означает, что этот спсоб работает не для всех возможных значений свободных переменных для для некоторых "вырожденных" комбинаций свободных переменных он неприменим. Дипломная работа Сергеевой С.Н. как раз и посвящена изучению одного из таких "вырожденных" случаев (c3=1).

  Основным результатом работы является нахождение нового 5-мерного семейства методов РК.

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

• Замыслова С.В. Дипломная работа "Размерности пространств Бутчера для 6-ти шаговых методов Рунге-Кутта порядка 5".

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

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

  К такой информации относятся сведения о так называемых "пространствах Бутчера" и особенно об их размерности. Следует отметить, что объяснение роли этих пространств выходит далеко за рамки данной дипломной работы. В классическом случае 4-х шаговых методов 4-го порядка эти размерности для всех методов одинаковы. Поэтому первым нетривиальным случаем как раз и являются методы порядка 5.

  Основным результатом работы (глава IV) является нахождение размерности пространства Бутчера L3. Как оказалось, в общем случае она равна 4 и для некоторых специальных случаев (найдены примеры) размерность может быть равна 3.
  
  

• Дюкова С.А. Дипломная работа "Некоторые 7-ми шаговые методы Рунге-Кутты порядка 6".

  Весьма интересный результат. Несколько лет назад была написана программа для численного нахождения методов Рунге-Кутта. В результате довольно долгих расчетов были найдено несколько десятков методов порядка 6. У части из них значения сразу трех коэффициентов b2, b3, b4 оказались очень близкими к 0 (10^(-10)..10^(-13)). Посколькку вычисления были приближенными, естественно было бы предположить, что в точном решении все три коэффициента обратятся в 0. Другими словами, должно существовать семейство методов РК, удовлетворяющее условию b2=b3=b4=0.

  Была предпринята попытка найти такое семейство решений аналитически. Она оказалась удачной. В представленной дипломной работе как раз и описываются основные этапы решения задачи.

  Некоторые громоздкие вычисления были проделаны с помощью системы компьютерной алгебры "Maple".
  
  

• Хаммуд Гияс Мухаммед Диссертация на соискание ученой степени кандидата физико-математических наук Пакет программ моделирования уравнений Бутчера для поиска методов Рунге-Кутта высокого порядка,

  Целью работы является построение методов типа Рунге-Кутта высоких (6, 7, 8) порядков, разработка как аналитических, так и численных методов их получения, исследование найденных методов, в частности нахождение локальной размерности многообразия решений.

  Аналитические решения уравнений Батчера (Butcher) находятся путем максимально полного применения так называемых "упрощающих предположений".

  Для численного решения используется многомерная версия метода Ньютона. Основной проблемой при этом является большая размерность решаемых систем линейных уравнений (до 200 уравнений и до более, чем 100 переменных).

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

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

2000 год.

• Арюшина О.Н. Дипломная работа "Решение уравнений для коэффициентов методов Рунге-Кутты порядка 4".

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

  Естественно, хотелось бы как можно более сократить объем вычислений. Для этого надо применить методы возможно более высокого порядка (высокой точности). Нахождение таких методов сводится к решению большой системы нелинейных полиномиальных уравнений на коэффициенты метода. Явно решить эту систему удается только для методов порядка не выше 6. Для методов более высокого порядка приходится искать другие подходы.

  Один из таких подходов связан с переходом в новую систему координат (нелинейно связанную с исходной).

  В дипломной работе Арюшиной О.Н. проделан полный цикл вычислений по этой схеме для методов 4-го порядка (8 уравнений от 10 переменных):

  - выписаны формулы, связывающие исходные и новые координаты,

  - выписана система уравнений в новых координатах,

  - получено ее решение (2 свободные переменные v34, v44),

  - выведены формулы, выражающие исходные переменные, через свободные.

  Все громоздкие вычисления были проделаны с помощью системы компьютерной алгебры "Maple". Уровень сложности рассматриваемых систем уравнений не позволил просто использовать команду "Solve" (решить). Поэтому пришлось проявить изобретальность для получения решения в явном виде.
  
  

• Захарова Е.А. Магистерская диссертация "Улучшение сходимости метода Ньютона для многомерных систем уравнений"

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

  Естественно, хотелось бы как можно более сократить объем вычислений. Для этого надо применить методы возможно более высокого порядка (высокой точности). Нахождение таких методов сводится к решению большой системы нелинейных полиномиальных уравнений на коэффициенты метода. Явно решить эту систему удается только для методов порядка не выше 6. Для методов более высокого порядка приходится искать другие подходы.

  Один из таких подходов связан с численным решением полученной системы уравнений. Естественно попытаться применить для решения задачи метод Ньютона (многомерный). Оказывается, однако, что в наиболее интересных случаях (порядок >=7) метод практически перестает сходится. Связано это с сильной вырожденностью исходной системы уравнений.

  Каким же образом можно улучшить его сходимость? Все известные универсальные методы не дают никакого эффекта. Возможно, стоит попробовать использовать какие-то особенности исходной системы полиномиальных уравнений. Сразу видно, что относительно многих переменных система является линейной. Но из-за большого количества уравнений и переменных (более 100 в интересных случаях) использовать полностью это особенность не так-то просто.

  Решению этой проблемы и посвящена диссертация Захаровой Е.А.
  
  

1999 год.

• Тимошенко Е.Н. Магистерская диссертация "Коды над алфавитом из 10 элементов максимальной мощности"

  Получены новые математические результаты. Наиболее существенные из них - построение кода над алфавитом из 10 элементов исправляющий одну ошибку длины 5<=n<=12 мощности 0.82*10^(n-2). Причем при n=12 построенный код оказался совершенным, то есть его мощность достигает предела, заданного границей Хемминга. По всей видимости это первый пример совершенного нелинейного кода.
  
  

1998 год.

• Тихомирова Е.А. Магистерская диссертация "Разложение дзета-функции Римана в расходящийся ряд"

  Дзета-функция Римана является одной из наиболее интересных и сложных функций в математике. Поэтому, естественно, хочется иметь алгоритм ее вычисления в комплексной области с любой наперед заданной точностью. В процессе работы над литературой подобного алгоритма обнаружить не удалось. Все имеющиеся алгоритмы сходятся черезчур медленно: за приемлемое время (секунды или даже минуты) получить результат с хорошей точностью (хотя бы 10-12 знаков) при Re(z)=1/2 оказывалось совершенно невозможно.

  Автором был предложен свой метод вычисления дзета-функции. Суть его сводится к тому, что мы вычисляем первые N членов исходного ряда непосредственно, а для вычисления остатка находим первые M членов некоторого другого ряда [формула (10), стр.9]. Основная трудность состоит в том, что второй ряд расходится: члены его сначала убывают, а начиная с некоторого места начинают расти. Однако в диссертации Тихомировой Е.А. доказано, что при достаточно большом N (зависящем от аргумента z) и подходящем M частичная сумма ряда сколь угодно точно приближает дзета-функцию. При этом предложенный алгоритм достаточно эффективен: в самом сложном случае (Re z = 1/2) при не слишком большом |z| ( < 1000) для получения точности 1e-15 достаточно взять несколько десятков членов первого ряда и не более 20 - второго.

  Полученный алгоритм, оформленный в виде модуля на языке Turbo Pascal будет включен в разрабатываемую математическую библиотеку. В настоящее время она уже содержит набор функций теории вероятности, разработанный Тихомировой Е.А. в качестве дипломной работы,набор основных математических функций (гамма, бета, Si, Ci и др.) (Волкова В.Б.) и пакет современных высокоэффективных численных методов решения ОДУ (Балабанов Н.Б.) и некоторые другие алгоритмы.