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

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

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

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

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

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

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

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

Базовая технология понятна – нужно сделать LaTeX-заготовку, в которую вставлять конкретные задания для каждого студента. Совершенно всё равно, на каком языке это делать, мне исторически привычнее писать небольшие программки на C++, поэтому я и тут буду его использовать. Самый простой способ сделать это в C++, который я знаю, – это boost::format: достаточно сделать заготовки с плейсхолдерами вроде %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 – опять же, очень удобно; хоть там и не так уж много чего реализовано, но нам сейчас много и не надо).

Такую структуру легко будет переиспользовать для формул алгебры множеств (это просто для сравнения, дальше 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, скомпилированного из такого файла).

Решения

Скептически настроенный читатель на этом месте разумно возразит: ну конечно, ты можешь сгенерировать 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;
}

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

Заключение

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

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

Автор: snikolenko

Источник