713 Тем для обсуждения

6,530 Открытых обсуждений

Математика и computer science. (2) Алгоритм и программа.

mt2 (12 пост(а)) 29.05.2009 14:11

Михаил Трофимов (mt2).

Первый блог я начал с бородатой шутки, этот начну с бородатого анекдота: «Математику нужно вскипятить чайник. Дано: пустой чайник, ведро с водой, горячая плита. Он наполнит чайник из ведра и поставит его на плиту. Ok! Меняем условия задачи: чайник уже заполнен водой, все остальное без изменений. Математик выльет воду из чайника и таким образом придет к предыдущей задаче, которую уже известно как решать.»

Очень неразумно с обывательской точки зрения и очень эффективно с точки зрения математики. А с точки зрения программирования? Как поступит программист? – Если у программиста уже имеется готовая библиотечная функция, требующая на входе пустой чайник, то очевидно программист поступит как и математик, такое решение будет наиболее эффективно с точки зрения минимизации трудозатрат программиста. Но, если это решение окажется достаточно неэффективным с точки зрения трудозатрат компьютера, то программисту придется переделать функцию Вскипятить_Чайник так, чтобы она могла работать с полным чайником. Основанием к такой оптимизации явится результат вычислительного эксперимента: программист попробует применить классический математический метод решения и посмотрит, насколько его скорость удовлетворительна. Даже из столь несерьезного примера  видно, что, наряду с математическими подходами к решению задач, computer science использует подходы специфические не для теоретических, как математика, а для экспериментальных (как физика, химия и т.д.) наук. В книгах как по теоретитической, так и по практической computer science особо подчеркивается, что до запуска и тестирования программы на компьютере никто не может гарантировать, что программа будет работать в соответствии со спецификацией (к сожалению, нередко и после тестирования, полной уверенности тоже не бывает ). В этом, по-видимому, одно из принципиальных отличий программы от реализуемого ею алгоритма: алгоритм – объект математической природы, основными методами доказательства его корректности и оценки его эффективности принято считать классические математические методы бумажного доказательства. Человечество знало алгоритмы (Евклида, решето Эратосфена и другие) задолго до появления компьютеров. Стройность картины портят так называемые эвристические алгоритмы, базирующиеся в лучшем случае на гипотезах, при этом доказательство корректности и теоретический анализ вычислительной сложности могут отсутствовать. Единственным обоснованием использования таких алгоритмов может служить только эксперимент.

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

При нынешней распространенной практике анонимного рецензирования научных журналов, докладов на симпозиумах и т.д. процедура отсева “неправильных” алгоритмов предельно упрощена – двум анонимным (т.е. фактически безответственным) рецензентам достаточно выразить сомнения в доказательстве или просто заявить, что они не поняли, что делает данный алгоритм, или сказать, что им кажется, что для него существует контр-пример, при этом обосновывать они ничего не должны, поскольку бремя доказательства лежит на доказующем, а в переписку по вопросам отклоненных публикаций/докладов редакции журналов и орг.комитеты симпозиумов обычно не вступают. Для полноты картины стоит отметить, что процесс рецензирования в ведущих научных журналах занимает сегодня в среднем 5-8 месяцев, а иногда растягивается и до двух лет! С другой стороны, в рамках того же формально-классического подхода реализации нового алгоритма в виде программы при его публикации обычно не требуется. И если лет пятнадцать назад еще и существовала практика публикации листингов, то многие сегодняшние издания от этой практики отошли. Можно утверждать, что выложить исходный код в сеть синхронно с выходом публикации – это сейчас, как правило, всецело авторская инициатива.

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

С точки зрения философско-психологической феномен существования эвристических алгоритмов труднообъясним: действительно, ни с того ни с сего некий программист «с потолка» пишет программу, которая решает во многих случаях неразрешимую другими методами задачу! Не иначе как мистическое откровение С точки зрения практической во многих случаях эвристического алгоритма достаточно. Наиболее очевидный пример – игровая индустрия: если в игре в 99.9% случаев боты будут выбирать оптимальную стратегию, то они будут казаться непобедимыми С точки зрения планирования мат.исследований: не надо искать и выдумывать, чем бы заняться, берите зарекомендовавшие себя недоказанные алгоритмы, каковых куча – исследуйте, доказывайте! Не исключено, что у многих найдется, может даже тривиальное доказательство, авторы по незнанию или по лени или просто за недостатком времени не потрудились его сделать. Доказанный алгоритм, конечно же, лучше, чем недоказанный, хотя бы теоретически понятно, что от него ждать, кроме того, из доказательства часто становятся видны пути для дальнейших усовершенстваний алгоритма. Но, к сожалению, математика сдерживается многими математиками в искусственных рамках, отмеченных в цитате из книги Клайна, с которой я начал первый блог

Категории: Intel Software Network, Разработка софта
Метки: математика

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

Комментарии (8)

31.05.2009 15:40 mt2 Всего баллов: 13,459 Зарегистрированный пользователь

В личной переписке, где я указал ссылку на этот блог, мне заметили, что в блоге следовало дать ссылку на начальный блог - исправляюсь: привожу ссылку на начальный блог (а в том укажу ссылку на продолжение): http://software.intel.com/ru-ru/blogs/2009/05/22/computer-science-1/

01.06.2009 05:26 Dmitry Oganezov (Intel) Всего баллов: 25,473 Community Manager

Прочитав этот пост еще неделю назад, я все это время размышлял о разнице в подходах классической науки и программирования. В начале апреля я послушал несколько секций конференции ПаВТ 2009 (Параллельные Вычислительные Технологии, http://agora.guru.ru/display.php?conf=pavt2009). Ощущения у меня сложились двоякие: что является несомненным плюсом, так это строгий регламент и четкое следование расписанию. Однако, как мне лично показалось, есть и серьезный минус: 5-10 минут на вопросы после часового доклада явно недостаточно, чтобы обсудить достаточно сложные, как с точки зрения математики, так и с точки зрения программирования, задачи и способы их решения. В результате мероприятие выглядит как конференция «для галочки», да простят меня организаторы. Конечно, особо активные собирались в фойе и что-то там обсуждали, но позвольте: если уж презентация все равно происходит, то почему бы не обсудить вопросы «по ходу»? Если вы не успели вклинить свой вопрос в 5 минут, и не успели в фойе, то шансов пообщаться с докладчиком у вас нет: далеко не все доклады можно найти на сайте конференции. Желающие могут попробовать. Я, например, не нашел докладов Андрея Карпова и Юрия Сердюка, которые, BTW, давно и успешно публикуют свои материалы на ISN. Плюс, даже если вы найдете интересующий вас доклад – он будет в формате PDF. В наше-то время не иметь возможности базовой коммуникации в Интернете по-моему как-то… несолидно. Или наоборот, это мы тут несолидные, а солидно – это как раз собираться для общения раз в году, а остальное время тихонечко сидеть в своих песочницах и давать рецензии? Кстати о рецензиях: я нисколько не удивляюсь типичными отзывами представителей HPC индустрии о работах друг друга: «Да, мы ***** знаем. Они тоже перемножают матрицы, но делают это неправильно. Мы перемножаем матрицы гораздо лучше» (цитата близко к тексту). Как пример обратного подхода я бы привел ту же конференцию КРИ. Просто сходите по этой ссылке: http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=��РИ+2009&btnG=Search+Blogs

01.06.2009 07:39 Dmitry Oganezov (Intel) Всего баллов: 25,473 Community Manager

И, раз уж начал, немного о строгих vs эмпирических доказательствах. В институте у нас был такой предмет – «Динамическое программирование». Ну, вы знаете, - все эти графы, транспортные задачи, рекурсия и так далее. Надо отметить, что о Интернете в те времена речи не было, но это еще полбеды. У нас было штук 10 экземпляров книги «Алгоритмы и структуры данных» на поток. Буквально занимали за ней очередь в библиотеках… Так вот, одному моему другу книги категорически не досталось. В результате он за две ночи написал алгоритм то ли обхода то ли поиска кратчайшего пути то ли в направленном, то ли в ненаправленном графе. Причем этот алгоритм был на четверть быстрее книжного. Помню, пришлось приложить массу усилий, чтобы вывести теоретическое обоснования алгоритма: в эмпирические оценки преподаватель верить не хотел ни в какую, и курсовую не принимал :)

01.06.2009 13:11 mt2 Всего баллов: 13,459 Зарегистрированный пользователь

Дмитрий, думаю, что на месте препода Вашего друга я поступил бы так же из чисто педагогических соображений. Более того - настоял бы, чтобы в лит.обзоре (к курсовой ведь требовался лит.обзор? - когда я учился в МГУ, с нас требовали) были бы описаны известные алгоритмы, применение оригинального одобрил бы, но с теоретическим доказательством корректности и со сравнением с книжными. В случае наличия доказательства вычислительной сложности для наихудшего случая поставил бы 5 и отметил бы в лучших работах, без такового наличия поставил бы 4 :) ИМХО, в данном случае тут все определяет педагогика, где жесткие правила игры - я хочу сказать, что для учебных задач правила, как правило, более жесткие, чем для задач реальных ;) Например, не знаю, учат ли теперь школьников вычислениям в уме и на бумаге, но на мой взгляд в школе должны учить полезным вещам - например, как выйти из леса по компасу и без компаса, как развести костер, как водить автомобиль, как вслепую "давить клаву" десятью пальцами и как умножить 49 на 53 без калькулятора - что и сейчас умножение на бумаге стоит знать, смогли убедиться участники проходящего конкурса на вычисление числа пи :) Так вот - на уроке по бумажным вычислениям все калькуляторы должны быть убраны - таковы правила игры. При том, что заставлять школьников всегда считать только на бумаге было бы сейчас величайшей глупостью :) Может быть, беда математики в том, что многие редактора многих мат.журналов по совместительству профессора университетов и переносят правила обучения студентов на авторов статей в эти журналы? ;)

01.06.2009 13:45 Dmitry Oganezov (Intel) Всего баллов: 25,473 Community Manager

Для обоснований и доказательств у нас были отдельные предметы ;) А все предметы с приставкой "программирование" - чисто на практику. Их было что-то около 15. Впрочем, я учился в сугубо прикладном ВУЗе.

01.06.2009 14:04 mt2 Всего баллов: 13,459 Зарегистрированный пользователь

И для каждого из 15-ти по курсовой?!- полный кошмар! ИМХО, за курс каждый студент должен сделать одну курсовую, используя знания, которые он получил за курс по всем предметам. Точно так же, как, окончив обучение, каждый должен сделать только 1 диплом, использовав все необходимые знания, полученные за все время обучения.

02.06.2009 08:28 Dmitry Oganezov (Intel) Всего баллов: 25,473 Community Manager

Ну да, примерно так и было - некоторые курсовые требовали зниний по другим предметам. Нас пытались накачать языками типа GPSS и RTRAN, но это, конечно, другая история...

02.06.2009 11:45 mt2 Всего баллов: 13,459 Зарегистрированный пользователь

Да, Дмитрий, тяжелая у нас судьба :) Язык GPSS в Википедии нашел, а про RTRAN, похоже, никто уже и не помнит...

Обратная ссылка (1)

• Блоги Intel® Software Network » Немного о мотивации… или Social Media вам не поможет
  15.06.2009 07:03

Оставить комментарий