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

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

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

,
где x лежит в диапазоне от 0 до 4, а y – от 0 до 2. Сколько (примерно) решений имеет уравнение?
Подчеркну еще раз, что входом для задачи является произвольное уравнение.
2. Дан двудольный связный граф; множество вершин первой доли обозначается через

, второй – через

. Каждая вершина

графа из

имеет положительную стоимость

. Требуется построить ориентированное дерево

из вершин

и назначить каждую вершину из

на связанную с ней вершину из

таким образом, чтобы
* смежные вершины в

имели бы в исходном графе общие смежные вершины в

* корень дерева имел бы минимальную меру
Мера для каждой вершины

дерева

вычисляется по формуле:

здесь

– «входящие» в

вершины в

,

– назначенные на

вершины
Применение этих задач следующее. Многие дискретные/комбинаторные задачи могут быть описаны в виде системы алгебраических уравнений. Часто для них неизвестен хороший метод решения и поэтому применяется перебор. С помощью задачи 1 можно оценить «жесткость» ограничений, а помощью задачи 2 – построить схему перебора, минимизирующую количество шагов. Множества

– это ограничения, множество

– переменные;

– количество допустимых значений переменной; мера

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