Дискретная математика
Давно хотел написать про университетскую математику (ну и другие предметы). Я уже давно подозреваю, что эти курсы были перегружены ненужными деталями (и наоборот, многое важное там отсутствовало). Попробую объяснить почему.
Математика после университета бывает полезна в трех областях: в научном изучении самой математики и ее объектов; в науке, непосредственно с математикой не связанной - как инструмента; ну и в обычной жизни - эпизодически. Обычно под "полезностью" того или иного курса понимается применимость его в последних двух случаях, иначе всё стало бы полезным.
В этот раз начнем с дискретной математики. Что же у нас было в ее составе, как это объяснялось и зачем все это нужно?
Булевы функции и их свойства. Начинается всё с нуля и единицы, а заканчивается полными системами. Это, с одной стороны, основы. С другой стороны - настоящие основы - это только сами функции, в чем нетрудно убедиться сравнивая разные учебники (в том числе иностранные). Зачем же полные и неполные системы, всякие там самодвойственные и монотонные функции? На самом деле всё, что требуется знать - это что все функции представимы полиномами. В качестве бонуса - что представимы через КНФ (то есть через наложение друг на друга функций равных единице в одной единственной точке). Всё остальное - наследие того факта, что отцы-основатели дискретной математики в СССР днем и ночью занимались полнотой систем функций. Так как в остальном мире все этим переболели в начале 20 века, попутно решив все возможные задачи в булевой логике, отцы-основатели перешли в многозначную логику, где, как показали годы геморроя, этим можно заниматься всю жизнь. Даже сейчас невозможно без слез взглянуть на отдельные сборники тезисов с российских конференций; а ведь авторы этих тезисов искренне думают что они занимаются делом.
Сложность алгоритмов. На первом курсе дается в простейшем виде: сложность сложения и умножения чисел. Замысел понятен: дать студентам понять, из чего складывается длительность выполнения программ и откуда берутся требования к памяти. Впоследствии все это пригодится при оптимизации. Однако у меня есть большие сомнения, что эта задача хотя бы очерчивается таким довольно куцым курсом. Более того, связь его с реальным программированием весьма слабая; зато, как всегда, большие возможности для ресерча в собственно теории сложности, опять же правда в её почвеннической интерпретации.
Графы. Изучение графов в курсе дискры безгранично. Возможно, этому способствует перевод многочисленных книг по теории графов в 60-е-70-е годы, а может и еще что-то. Важно другое. Графы - это даже не инструмент, это структура данных. Графы возникают там, где есть хаотичные связи одних объектов с другими, которые плохо представимы в виде таблиц. Знатоки матриц смежности могут идти лесом - любой программист знает, что графы обычно далеко не полные, а хранить разреженную матрицу - ну, вы понимаете. Главное, таким образом, при изучении графов - это их удобство для тех или иных алгоритмов. Никого не волнует, сколько графов такой-то формы. Гораздо важнее, сколько работает алгоритм Дейкстры при поиске пути от западного побережья США до восточного на гуглмапсе (а работает он чуть ли не полминуты). Почему хороши деревья - потому что в них циклов нет, то есть алгоритмы для них намного проще. В Таненбауме по компьютерным сетям есть наглядные примеры. Итог - большей части теории графов в университетском курсе место в библиотеке. Это также касается терии планарности, которая выглядит как детская игрушка, вроде штриха Шеффера.
Автоматы. Прекрасная вещь. Находит себе применение везде - от компиляторов до криптоанализа. Однако, как всегда, важного-то там немного - применимость и правила разбора выражений. Эквивалентность? Определения? Не смешите. Кто в последний раз проверял эквивалентность одного автомата другому? Да запустите на тысяче случайных входов и узнаете.
Теория кодирования. Здесь такое впечатление, что изучаешь учебник начала 20 века. Зачем нужны коды? Для описания пространств в булевом кубе. Где-то простых, вроде шаров единичного радиуса, где-то посложнее. Ключевой момент - исправление ошибок, причем быстрое. Далеко не всякий код может. Какой может, а какой - нет, это и есть те вопросы, на которые нужно давать ответы в этом курсе. Почему на сидюках код Рида-Соломона? Уже и производители забыли, наверное. Ну, хоть код Хэмминга в курсе есть, и то славно.
Комбинаторика. Это было не у всех. Здесь, конечно, жаловаться не на что - можно было и больше курс сделать, все равно бы пригодился. Другое дело, что далеко не у всех голова комбинаторно работает. Я бы даже рискнул сказать, что очень у немногих. Вот для них это хорошо как спецкурс, а остальным надо уметь работать со справочниками или со студентами первого типа.
Что там осталось? Сложность схем, машины Тьюринга, и еще какая-то лабуда, проходящая под обшим названием "Основы кибернетики". Здесь у меня нет цензурных слов для комментирования, хотя они и были когда я только начинал писать текст. Воистину, знание о том, что любое вычисление можно произвести на одной из десятков эквивалентных конструкций не стоит пары месяцев потерянного времени. Где это нужно? Да нигде. Мало ли на свете эквивалентных конструкций? Что с того, что они эквивалентны? Вон, суперкомпьютеры и ноутбуки тоже эквивалентны, но как-то никто не спешит заменять одно другим. Сложность схем? Схемы строятся методом каскадов - вот и всё.
Математика после университета бывает полезна в трех областях: в научном изучении самой математики и ее объектов; в науке, непосредственно с математикой не связанной - как инструмента; ну и в обычной жизни - эпизодически. Обычно под "полезностью" того или иного курса понимается применимость его в последних двух случаях, иначе всё стало бы полезным.
В этот раз начнем с дискретной математики. Что же у нас было в ее составе, как это объяснялось и зачем все это нужно?
Булевы функции и их свойства. Начинается всё с нуля и единицы, а заканчивается полными системами. Это, с одной стороны, основы. С другой стороны - настоящие основы - это только сами функции, в чем нетрудно убедиться сравнивая разные учебники (в том числе иностранные). Зачем же полные и неполные системы, всякие там самодвойственные и монотонные функции? На самом деле всё, что требуется знать - это что все функции представимы полиномами. В качестве бонуса - что представимы через КНФ (то есть через наложение друг на друга функций равных единице в одной единственной точке). Всё остальное - наследие того факта, что отцы-основатели дискретной математики в СССР днем и ночью занимались полнотой систем функций. Так как в остальном мире все этим переболели в начале 20 века, попутно решив все возможные задачи в булевой логике, отцы-основатели перешли в многозначную логику, где, как показали годы геморроя, этим можно заниматься всю жизнь. Даже сейчас невозможно без слез взглянуть на отдельные сборники тезисов с российских конференций; а ведь авторы этих тезисов искренне думают что они занимаются делом.
Сложность алгоритмов. На первом курсе дается в простейшем виде: сложность сложения и умножения чисел. Замысел понятен: дать студентам понять, из чего складывается длительность выполнения программ и откуда берутся требования к памяти. Впоследствии все это пригодится при оптимизации. Однако у меня есть большие сомнения, что эта задача хотя бы очерчивается таким довольно куцым курсом. Более того, связь его с реальным программированием весьма слабая; зато, как всегда, большие возможности для ресерча в собственно теории сложности, опять же правда в её почвеннической интерпретации.
Графы. Изучение графов в курсе дискры безгранично. Возможно, этому способствует перевод многочисленных книг по теории графов в 60-е-70-е годы, а может и еще что-то. Важно другое. Графы - это даже не инструмент, это структура данных. Графы возникают там, где есть хаотичные связи одних объектов с другими, которые плохо представимы в виде таблиц. Знатоки матриц смежности могут идти лесом - любой программист знает, что графы обычно далеко не полные, а хранить разреженную матрицу - ну, вы понимаете. Главное, таким образом, при изучении графов - это их удобство для тех или иных алгоритмов. Никого не волнует, сколько графов такой-то формы. Гораздо важнее, сколько работает алгоритм Дейкстры при поиске пути от западного побережья США до восточного на гуглмапсе (а работает он чуть ли не полминуты). Почему хороши деревья - потому что в них циклов нет, то есть алгоритмы для них намного проще. В Таненбауме по компьютерным сетям есть наглядные примеры. Итог - большей части теории графов в университетском курсе место в библиотеке. Это также касается терии планарности, которая выглядит как детская игрушка, вроде штриха Шеффера.
Автоматы. Прекрасная вещь. Находит себе применение везде - от компиляторов до криптоанализа. Однако, как всегда, важного-то там немного - применимость и правила разбора выражений. Эквивалентность? Определения? Не смешите. Кто в последний раз проверял эквивалентность одного автомата другому? Да запустите на тысяче случайных входов и узнаете.
Теория кодирования. Здесь такое впечатление, что изучаешь учебник начала 20 века. Зачем нужны коды? Для описания пространств в булевом кубе. Где-то простых, вроде шаров единичного радиуса, где-то посложнее. Ключевой момент - исправление ошибок, причем быстрое. Далеко не всякий код может. Какой может, а какой - нет, это и есть те вопросы, на которые нужно давать ответы в этом курсе. Почему на сидюках код Рида-Соломона? Уже и производители забыли, наверное. Ну, хоть код Хэмминга в курсе есть, и то славно.
Комбинаторика. Это было не у всех. Здесь, конечно, жаловаться не на что - можно было и больше курс сделать, все равно бы пригодился. Другое дело, что далеко не у всех голова комбинаторно работает. Я бы даже рискнул сказать, что очень у немногих. Вот для них это хорошо как спецкурс, а остальным надо уметь работать со справочниками или со студентами первого типа.
Что там осталось? Сложность схем, машины Тьюринга, и еще какая-то лабуда, проходящая под обшим названием "Основы кибернетики". Здесь у меня нет цензурных слов для комментирования, хотя они и были когда я только начинал писать текст. Воистину, знание о том, что любое вычисление можно произвести на одной из десятков эквивалентных конструкций не стоит пары месяцев потерянного времени. Где это нужно? Да нигде. Мало ли на свете эквивалентных конструкций? Что с того, что они эквивалентны? Вон, суперкомпьютеры и ноутбуки тоже эквивалентны, но как-то никто не спешит заменять одно другим. Сложность схем? Схемы строятся методом каскадов - вот и всё.