Дискретная математика для первокурсников: опыт преподавателя

Сегодня у меня необычный текст, совершенно не связанный с машинным обучением (для новых читателей: этот текст – часть блога компании Surfingbird ^[1], в котором я в течение последнего года рассказывал о разных аппаратах машинного обучения в приложении к рекомендательным системам). В этом посте математической части практически будет, а будет описание очень простой программки, которую я написал для своих студентов. Вряд ли кто-то узнает для себя из этого поста много содержательно нового, но мне кажется, что некоторую ценность представляет сама идея – многие люди просто не задумываются о том, что «и так можно». Итак…

Постановка задачи

В этом семестре у меня началась несколько непривычная деятельность: я преподаю дискретную математику для первокурсников ^[2] в петербургском филиале Высшей Школы Экономики; преподаю я давно, но, кажется, раньше никогда у меня не было студентов младше четвёртого-пятого курса. По ссылке можно найти краткое содержание курса, да и то неполное (курс ещё идёт), но речь не совсем об этом.

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

В качестве одной из форм отчётности я выбрал «большое домашнее задание»: несколько как раз таких практических примеров, которые надо решать. У такой формы много плюсов: студенты работают в удобном им темпе, я тоже проверять могу сколько нужно, всё в письменном виде происходит, что всегда удобно. Но есть и минусы; главный минус прост – трудно сделать и проверить пятьдесят вариантов на пятьдесят студентов (на потоке их примерно столько и есть). А если дать один вариант на большую группу, понятно, что на выходе получишь красиво переписанные правильные ответы, особенно учитывая, что в такой базовой дискретной математике «ход решения» нередко просто отсутствует (как построить СДНФ – ну как, посмотреть на таблицу истинности да записать...).

Чтобы обойти эту проблему, я решил написать простую программку, которая будет генерировать индивидуальное домашнее задание для каждого студента случайным образом. Идея чрезвычайно простая, но почему-то ни в свою бытность студентом, ни в более позднем преподавательском опыте я её ни разу не встречал – собственно, поэтому и пишу этот пост. Я приведу минимальный работающий пример, а потом покажу, что у меня в результате получилось.

Шаблоны в .tex и boost::format

Базовая технология понятна – нужно сделать LaTeX-заготовку, в которую вставлять конкретные задания для каждого студента. Совершенно всё равно, на каком языке это делать, мне исторически привычнее писать небольшие программки на C++, поэтому я и тут буду его использовать. Самый простой способ сделать это в C++, который я знаю, – это boost::format ^[3]: достаточно сделать заготовки с плейсхолдерами вроде %1%, %2%, и потом можно вставлять туда что угодно (у boost::format есть и другие возможности, но нам они сейчас не понадобятся).

Итак, делаем шаблоны. Сначала общий шаблон «абстрактного LaTeX-документа»:

documentclass[a4paper]{article}

usepackage[utf8]{inputenc}
usepackage{amsthm,amsmath,amsfonts, amssymb}
usepackage[english,russian]{babel}

usepackage{concrete}
usepackage{enumerate}
usepackage{euler}
usepackage{fullpage}

pagestyle{empty}
selectlanguage{russian}

begin{document}

selectlanguage{russian}

%1%

end{document}

Потом конкретный шаблон собственно задания – его мы будем подставлять вместо %1%. Я здесь, как и обещал, привожу минимальный пример. Мы будем генерировать только одну задачку: по заданной булевской формуле перевести её в несколько других форм.

Дискретная математика hfill %1%

весна $2013$ hfill группа %2%

section*{Домашнее задание}

begin{enumerate}
item Для формулы пропозициональной логики
$$ varphi = %3%: $$
begin{enumerate}[(i)]
	item постройте таблицу истинности;
	item переведите $varphi$ в совершенную конъюнктивную и совершенную дизъюнктивную нормальные формы;
	item выразите $varphi$ в виде полинома Жегалкина;
	item $[ast]$ выразите $varphi$ при помощи штриха Шеффера $xmid y = lnot(xland y)$.
end{enumerate}

pagebreak

И теперь нам просто нужно сгенерировать, чем заполнить %3% (вместо %1% и %2% будут подставляться имя студента и номер группы). Для этого нужно научиться генерировать формулы. Сразу предупреждаю, что я плохой программист, и код ниже наверняка напоминает спагетти – в принципе, он работает, если кто-нибудь посоветует изящный рефакторинг, скажу спасибо.

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

class Globals {
public:
    size_t TypesNo;
    size_t VarType;
    vector<string> TypesLatex;
    vector<size_t> TypesArity;
    boost::random::uniform_int_distribution<> RandomNodeType;
    boost::random::uniform_int_distribution<> RandomNodeNoVar;
    boost::random::uniform_int_distribution<> RandomNodeBinary;

    size_t VarsNo;
    vector<string> VarNames;
    boost::random::uniform_int_distribution<> RandomVarType;
    size_t current_varnum;

    Globals(size_t types_num, vector<string> types_latex, vector<size_t> types_arity, size_t var_num, vector<string> var_names) :
        TypesNo(types_num), VarType(types_num - 1), TypesLatex(types_latex), TypesArity(types_arity),
        RandomNodeType(0, types_num - 1), RandomNodeNoVar(0, types_num - 2), RandomNodeBinary(0, types_num - 3),
        VarsNo(var_num), VarNames(var_names), RandomVarType(0, var_num - 1), current_varnum(var_num - 1) {}

    size_t get_next_var() {
        current_varnum++;
        if (current_varnum == VarsNo) current_varnum = 0;
        return current_varnum;
    }
};

Globals GBoolean(7,
				{ "\land", "\lor", "\rightarrow", "\oplus", "\equiv", "\lnot", "\var" },
				{ 2, 2, 2, 2, 2, 1, 0 },
				4,
				{ "x", "y", "z", "t" });

Здесь мы создали «язык булевских формул», у которого пять бинарных связок (конъюнкция, дизъюнкция, импликация, XOR и эквивалентность) и одна унарная (отрицание). Седьмой тип узла – это переменная, у неё арность 0. В домашнем задании я ограничился формулами из четырёх переменных: меньше маловато, а больше становится слишком громоздко. Сюда же удобно записать генераторы случайного типа узла, случайной переменной, случайной бинарной связки (я пользовался распределениями из boost::random ^[4] – опять же, очень удобно; хоть там и не так уж много чего реализовано, но нам сейчас много и не надо).

Такую структуру легко будет переиспользовать для формул алгебры множеств (это просто для сравнения, дальше GSet использоваться не будет):

Globals GSet(5,
			{ "\cap", "\cup", "\triangle", "\overline", "\var" },
			{ 2, 2, 2, 1, 0 },
			3,
			{ "A", "B", "C" });

Теперь создаём класс формулы. Булевская формула – это дерево, листьями которого служат переменные, а внутренними вершинами – логические связки. Мы хотим уметь генерировать формулы заданной глубины, поэтому в конструктор будем передавать, не пора ли сделать этот узел листом или, наоборот, обязательно бинарной связкой. Если нужно создать случайный узел, будем передавать тип g->TypesNo. Если узел оказался листом, ему нужно сгенерировать переменную (чтобы с большой вероятностью переменные попали все, мы просто берём их по кругу – формулы, конечно, не совсем случайные получаются, но это не страшно).

class BNode {
public:
    Globals *glob;
    size_t type;
    size_t varnum;
    BNode * left;
    BNode * right;

    BNode(Globals *g, size_t t, bool must_be_leaf = false, bool must_not_be_leaf = false, bool must_be_binary = false) : glob(g), type(t), left(NULL), right(NULL) {
        if (t == g->TypesNo) { // this means we want a random node
            type = must_be_leaf ? g->VarType
                : (must_be_binary ? g->RandomNodeBinary(gen)
                    : (must_not_be_leaf ? g->RandomNodeNoVar(gen)
                        : g->RandomNodeType(gen) ));
        }
        varnum = (type == g->VarType) ? g->get_next_var() : 0;
    }

    ~BNode() {
        if (left != NULL) delete left;
        if (right != NULL) delete right;
    }
};

Теперь начинаем заполнять класс BNode. Главное для нас – чтобы формула успешно печаталась в LaTeX:

    string TypeString() const {
        if (type == glob->VarType) return glob->VarNames[varnum];
        return glob->TypesLatex[type];
    }

    string ToString() const {
        if (glob->TypesArity[type] == 0) return TypeString();
        if (glob->TypesArity[type] == 1) return TypeString() + "{" + left->ToString() + "}";
        return "(" + left->ToString() + " " + TypeString() + " " + right->ToString() + ")";
    }

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

    bool get_truth_value(const vector<bool> & vals) {
        switch(type) {
            case 0: return left->get_truth_value(vals) && right->get_truth_value(vals); break;
            case 1: return left->get_truth_value(vals) || right->get_truth_value(vals); break;
            case 2: return (!left->get_truth_value(vals)) || right->get_truth_value(vals); break;
            case 3: return left->get_truth_value(vals) != right->get_truth_value(vals); break;
            case 4: return left->get_truth_value(vals) == right->get_truth_value(vals); break;
            case 5: return !left->get_truth_value(vals); break;
            case 6: return vals[varnum]; break;
            default: return false; break;
        }
    }

Оставим пока класс BNode (мы к нему ещё вернёмся); теперь мы можем написать генератор случайной формулы. Будем генерировать формулу с заданной минимальной и максимальной глубиной (для поддержки минимальной глубины мы добавляли раньше в конструктор поле must_not_be_leaf):

BNode *generate_tree(Globals & g, size_t min_depth, size_t max_depth, bool must_be_binary = false) {
    if (max_depth == 0) return NULL;
    BNode *node = new BNode(&g, g.TypesNo, max_depth == 1, min_depth > 0, must_be_binary);
    if (g.TypesArity[node->type] == 1) {
        node->left = generate_tree(g, min_depth, max_depth, true);
    }
    if (g.TypesArity[node->type] == 2) {
        node->left = generate_tree(g, min_depth - 1, max_depth - 1);
        node->right = generate_tree(g, min_depth - 1, max_depth - 1);
    }
    return node;
}

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

И можно писать обработчик файла со списком студентов:

void process_one_student_file_boolean(string dir, string fname,
        boost::format & general_tmpl, boost::format & problem_tmpl, boost::format & solution_tmpl) {
    BNode *node_bool;

    ostringstream s;
    vector<string> students = readAllLinesFromFile(dir + "/" + fname + ".txt");
    cout << "tГруппа " << fname << endl;
    for (size_t i=0; i<students.size(); ++i) {
        if (students[i].size() == 0) continue; // empty line
        cout << "tt[ " << students[i] << " ]" << endl;
        node_bool = generate_tree(GBoolean, 2, 4);
        string group_string = "$" + fname + "$";
        s << problem_tmpl % students[i] % group_string
                          % node_bool->ToString();
        delete node_bool;
    }
    ofstream ofs(dir + "/" + fname + ".tex");
    ofs << general_tmpl % s.str() << endl;
    ofs.close();
}

а затем и main, который читает файлы с форматами и процессит файлы со списками студентов:

string students_dir = "2013";
vector<string> students_files = { "BoTR" };

int main(int argc, char *argv[]) {
    boost::format boolean_tpml( read_file_as_string("boolean_problem_minimal.tex") );
    boost::format general_tmpl( read_file_as_string("general_template.tex") );

    for (size_t i = 0; i < students_files.size(); ++i) {
        process_one_student_file_boolean(students_dir, students_files[i], general_tmpl, boolean_tpml);
    }

    return 0;
}

Но постойте, слышу я голос внимательного читателя. Будет же ерунда получаться – небось, добрая половина так сгенерированных случайных формул окажутся тривиальными! Что верно, то верно – про половину не знаю, но даже одна случайно сгенерированная формула вида varphi = x изрядно подмочит репутацию нашего метода. Давайте мы научимся это проверять. Для этого мы просто подсчитаем, сколько в формуле встречается связок и разных переменных, и потребуем, чтобы переменные встречались все, а связки – хотя бы две разные. Добавляем в BNode обход формулы:

    void depth_first(function<void (const BNode * n)> do_with_node) {
        do_with_node(this);
        if (left != NULL) left->depth_first(do_with_node);
        if (right != NULL) right->depth_first(do_with_node);
    }

и вписываем проверку формулы на разумность:

bool sanity_check(BNode * node) {
    vector<bool> vars_present(node->glob->VarsNo, false);
    vector<bool> connectors_present(node->glob->TypesNo, false);
    node->depth_first([&] (const BNode * n) {
        if (n->type == n->glob->VarType) {
            vars_present[ n->varnum ] = true;
        } else {
            connectors_present[ n->type ] = true;
        }
    });
    return all_of( vars_present.begin(), vars_present.end(), [](bool b) {return b;} ) &&
           (accumulate(connectors_present.begin(), connectors_present.end(), 0) > 2);
}

Можно ещё захотеть проверить, не является ли формула, скажем, всегда истинной, но я этого сознательно решил не делать – если сложная на вид формула вдруг окажется тождественно истинной, тем интереснее будет это задание для студента. А очевидные подформулы типа «x или не x» в нашем генераторе не будут получаться, потому что переменные перебираются по очереди, а не случайно.

Запуская получившуюся программку на файле со списком студентов, получаем .tex файл со вполне адекватно оформленными заданиями (вот пример pdf, скомпилированного из такого файла ^[5]).

Решения

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

Заводим другой LaTeX-шаблон для документа с ответами:

{footnotesize
subsection*{%1%, группа %2%}

Таблица истинности для формулы $%3%$:
$$ %4% $$

}
pagebreak 

Я, опять же, ограничусь минимальным примером – давайте просто выведем таблицу истинности. Для этого нужно пройтись по всем возможным значениям переменных, посчитать истинностное значение формулы и красиво оформить результат в TeX'е. Добавляем два метода в класс BNode:

    bool increment_counter(vector<bool> & v) {
        for (int i=v.size()-1; i>=0; --i) {
            if (!v[i]) {
                v[i] = true;
                for (size_t j=i+1; j<v.size(); ++j) v[j] = false;
                return true;
            }
        }
        return false;
    }

    string latex_truthtable() {
        ostringstream os;
        vector<bool> counter(glob->VarsNo, false);
        os << "\begin{array}{";
        for(size_t i=0; i<counter.size(); ++i) os << 'c';
        os << "|c}n";
        for(size_t i=0; i<counter.size(); ++i) os << glob->VarNames[i] << " & ";
        os << " \\\hlinen";
        do {
            for(size_t i=0; i<counter.size(); ++i) os << counter[i] << " & ";
            os << get_truth_value(counter) << "\\n";
        } while (increment_counter(counter));
        os << "\end{array}n";
        return os.str();
    }

а затем добавляем это в process_one_student_file_boolean:

void process_one_student_file_boolean(string dir, string fname,
        boost::format & general_tmpl, boost::format & problem_tmpl, boost::format & solution_tmpl) {
    BNode *node_bool;

    ostringstream s, ssolution;
    vector<string> students = readAllLinesFromFile(dir + "/" + fname + ".txt");
    cout << "tГруппа " << fname << endl;
    for (size_t i=0; i<students.size(); ++i) {
        if (students[i].size() == 0) continue; // empty line
        cout << "tt[ " << students[i] << " ]" << endl;
        do {
            node_bool = generate_tree(GBoolean, 2, 4);
        } while (!sanity_check(node_bool));
        string group_string = "$" + fname + "$";
        s << problem_tmpl % students[i] % group_string
                          % node_bool->ToString();
        ssolution << solution_tmpl % students[i] % group_string
                          % node_bool->ToString() % node_bool->latex_truthtable();
        delete node_bool;
    }
    ofstream ofs;
    open_for_writing(dir + "/" + fname + ".tex", ofs);
    ofs << general_tmpl % s.str() << endl;
    ofs.close();
    
    open_for_writing(dir + "/" + fname + ".sol.tex", ofs);
    ofs << general_tmpl % ssolution.str() << endl;
    ofs.close();
}

string students_dir = "2013";
vector<string> students_files = { "BoTR" };

int main(int argc, char *argv[]) {
    boost::format boolean_tpml( read_file_as_string("boolean_problem_minimal.tex") );
    boost::format solution_tpml( read_file_as_string("boolean_solution_minimal.tex") );
    boost::format general_tmpl( read_file_as_string("general_template.tex") );

    for (size_t i = 0; i < students_files.size(); ++i) {
        process_one_student_file_boolean(students_dir, students_files[i], general_tmpl, boolean_tpml, solution_tpml);
    }

    return 0;
}

В результате в пару к файлу заданий (пример ^[5]) получается соответствующий ему файл решений (тот же пример, решения ^[6]), по которому проверять становится гораздо проще.

Заключение

И вот результат – полдня работы, а на выходе сколько угодно заданий с готовыми ответами, всё красиво оформлено и готово к выдаче студентам. Если интересно, каким получилось реальное задание, вот пример окончательного результата ^[7]. Файл с ответами выкладывать не буду, чтобы лишний раз не подсказывать студентам – они сейчас как раз решают это домашнее задание. Думаю, если моё преподавание в ГУ-ВШЭ будет продолжаться, эта программка мне ещё не раз послужит; ближайший шанс её применить – билеты для письменного экзамена в тех же группах.

P.S. Когда я готовил статью на хабр, я нашёл небольшой баг в своём генераторе формул; но исправлять не стал. Упражнение для внимательного читателя: какие формулы, в которых в принципе ничего плохого нету, мой генератор никогда не сможет породить? (помимо замечания о переборе переменных по порядку, которое я уже делал выше)

Автор: snikolenko

Источник ^[8]