Доказательство корректности алгоритма и вычисление его сложности — как в этом разобраться?
Всем привет,
Мне предстоит решить/написать работу по теме "Алгоритмы для реорганизации и оптимизации вебсайтов".
И если например с понимаем сути работы алгоритма у меня более-менее нормально идет, то с математической частью не очень.
Например есть алгоритм, описанный словесно и математически в научной публикации:
Имеется большой сайт - тысячи страниц, они каким-то образом неоптимально перелинкованы друг с другом, пользователям нужно сделать большое кол-во переходов чтобы найти нужную страницу, поиск нужного контента происходит медленно.
Создается модель перелинковки сайта в виде, например, кладограммы (либо дерева или графа), а затем предлагается по определенному алгоритму эту перелинковку реорганизовать для оптимизации нахождения нужной информации на сайте в соответствии с определенным параметром, например частотностью посещения страницы по ссылке пользователями.
Вычисляется сложность (O), выводится математическое/логическое доказательство корректности алгоритма (завершается, выдает правильный вывод). Затем все это реализовать в псевдокоде/блоксхеме.
Трудность у меня возникает именно с математической частью и доказательством корректности, поэтому буду благодарен за рекомендации что почитать/посмотреть именно на эту тему
Также если у кого есть какие-то идеи о том, какие еще алгоритмы можно использовать при оптимизации сайтов/интернет ресурсов - прошу поделиться.
Если кто-то хорошо разбирается именно в математической стороне работы алгоритмов и может объяснить/консультировать по этому профилю - буду рад пообщаться.
если больше по части программирования, то корректность подкрепляется набором тестов
если по части компьютер сайнс, то посмотри на язык Coq для доказательства теорем, часто используется в длинных выкладках и сильно снижает риск ошибок, которые так легко допустить на бумаге
для доказательств и практики в этом существует огромный раздел, так и называется теория доказательств
ссылки даю на Вики, чтобы максимально просто было описано, если будет желание дальше уже сам нагуглишь, информации море. И напоследок для общего развития есть хорошая книга Маклейна "Теория категорий для работающего математика", читать рекомендуется всем и прикладникам и теоретикам
вы решаете оптимизационную задачу, вам нужно доказывать "оптимальность" (ну или близкую к оптимальному) решение, а не какую-то корректность (любая перелинковка может быть корректной, но не оптимальной).
Критерий оптимальности вы вводите самостоятельноо, по нему же и оцениваете свой алгоритм.
Можете например ввести понятия "стоимости перехода", и ценности отдельных "страниц" и потом расчитать для разных вариантов перелинковок эту стоимость, потом ее оптимизировать, показать что в среднем, например ваш вариант будет более выгодным и тд.
Спасибо за отклик :) Корректность - имеется ввиду, что алгоритм завершает работу и выводит корректный ответ. Корректный не по существу а по форме - выдает имеено тот тип результата, который от него ожидается, безотносительно оптимальности.
Aleksandr, Для проверки алгоритмов для которих лень писать большое количество разнообразных юнит тестов. Вам нужно проверять тогда определенные свойства которые соответствую алгоритму.
Например если вам надо найти один единственный "корректный ответ", тот тут все просто, одни и теже данные должны давать один и тотже результат, тоесть можете как угодно перемешивать одни и теже входящие данные, выбирать разную очередность входящих данных но в итоге, алгоритм должен выдавать один и тотже результат, можете сверить это свойство, если оно сохраняется для большого количества перемешиваний, значит алгоритм корректен.
Средний
