Запись доказательства для алгоритма
Привет парни я пытаюсь сравнить 2 алгоритма и думал, что могу попытаться записать доказательство для них!!! (моя математика сосет так следовательно вопрос),
Обычно на нашем математическом уроке в прошлом году нам дали бы вопрос как
докажите: (2r + 3) = n (n + 4)
затем я сделал бы необходимые 4 этапа и получил бы ответ в конце
То, где я застреваю, доказывает начала и Kruskals - как я могу вложить эти алгоритмы к форме как mathmatical один выше, таким образом, я могу продолжить доказывать
примечание: я не прошу, чтобы люди ответили, что это для меня - просто помогает мне вложить его к форме, где я могу делать попытку сам
спасибо
5 ответов
Чтобы доказать правильность алгоритма, вы обычно должны показать (а), что он завершается, и (б) что его результат соответствует спецификации того, что вы пытаетесь сделать. Эти два доказательства будут сильно отличаться от алгебраических доказательств, упомянутых вами в своем вопросе. Ключевое понятие, которое вам нужно, - это математическая индукция . (Это рекурсия для доказательств.)
Возьмем в качестве примера quicksort .
Чтобы доказать, что быстрая сортировка всегда завершается, вы сначала должны показать, что она завершается для ввода длины 1. (Это тривиально верно.) Затем покажите, что если он завершается для ввода длины до n , то он завершается для ввода длины n + 1 . Благодаря индукции этого достаточно, чтобы доказать, что алгоритм завершается для всех входных данных.
Чтобы доказать, что быстрая сортировка верна, вы должны преобразовать спецификацию сравнительной сортировки на точный математический язык. Мы хотим, чтобы на выходе была перестановка входа так, что если i ≤ j , то a i ≤ a j . Доказать, что вывод быстрой сортировки представляет собой перестановку ввода, легко, поскольку она начинается с ввода и просто меняет местами элементы. Доказать второе свойство немного сложнее, но опять же вы можете использовать индукцию.
Доказать, что вывод быстрой сортировки является перестановкой ввода, легко, поскольку он начинается с ввода и просто меняет местами элементы. Доказать второе свойство немного сложнее, но опять же вы можете использовать индукцию. Доказать, что вывод быстрой сортировки представляет собой перестановку ввода, легко, поскольку она начинается с ввода и просто меняет местами элементы. Доказать второе свойство немного сложнее, но опять же вы можете использовать индукцию.Вы не даете много подробностей, но есть сообщество математиков («Управление математическими знаниями MKM»), которые разработали инструменты для поддержки компьютерных доказательств математики. См., Например:
и последнюю конференцию
В большинстве случаев доказательство зависит от проблемы, которую вы держите в руках. Простого аргумента иногда может быть достаточно, в некоторых случаях вам может потребоваться строгое доказательство . Однажды я использовал следствие и доказательство уже доказанной теоремы, чтобы оправдать мой алгоритм. Но это для проекта колледжа.
Там, где я застрял, доказывают примы и Крускалы - как я могу привести эти алгоритмы в форму, подобную математической выше, чтобы я мог перейти к доказательству
, я не думаю, что вы можете прямо. Вместо этого, докажите, что оба генерируют MST, а затем докажите, что любые два MST равны (или эквивалентны, так как вы можете иметь более одного MST для некоторых графов). Если оба алгоритма генерируют MST, которые показаны как эквивалентные, то алгоритмы эквивалентны.
Из моих математических классов в Uni I (смутно) вспоминаю доказательство алгоритмов Примс и Крускалс - и не атакуешь его, написав в математической форме. Вместо этого вы берете проверенные теории для графиков и комбинируете их, например http://en.wikipedia.org/wiki/Prim%27s_algorithm#Proof_of_correctness, чтобы построить доказательство.
Если вы хотите доказать сложность, то просто по работе алгоритма это O(n^2). Есть несколько оптимизаций для особого случая, когда граф разрежен, что может уменьшить его до O(nlogn).
.