- •1. Определение алгоритма и способы их записей.
- •2. Принятые обозначения при описании алгоритмов.
- •3. Пошаговое описание алгоритмов.
- •4. Описание алгоритмов в виде блок-схем.
- •5. Свойства алгоритмов.
- •6. Критерии эффективности и сложность алгоритмов.
- •7. Классификация задач по степени сложности.
- •8. Сущность метода математической индукции (ми).
- •9. Построение доказательства по методу ми.
- •10. Примеры доказательств с использованием метода ми.
- •11. Использование метода ми для исследования алгоритмов (на примере обобщенного алгоритма Евклида).
- •12. Недетерминированные и детерминированные алгоритмы.
- •13. Разделы математической логики, представление операций булевой логики через множества и их отображение с помощью диаграмм Эйлера-Венна.
- •14. Объединение множеств и переход от предметной переменной х к логическим переменным х1 и х2 .
- •15. Пересечение множеств, тавтология, противоречие, дополнение и области взаимодействия двух множеств на диаграмме Эйлера-Венна.
- •16. Таблицы истинности для дизъюнкции и конъюнкции.
- •17. Операции стрелка Пирса и штрих Шеффера.
- •18. Операции разности и импликации.
- •19. Операции симметрической разности и эквивалентности.
- •20. Формы представления булевых функций (сднф, скнф, спнф).
- •21. Двойственность в булевой логике.
- •22. Различия отображения логических функций в сднф. Скнф и спнф. Переход из сднф в спнф.
- •23. Минимальные нормальные формы логических функций.
- •24. Принцип суперпозиции в булевой логике и приоритеты логических операций.
- •25. Классы элементарных логических функций.
- •26. Законы логики Буля.
- •27. Применение закона поглощения для нескольких переменных.
- •28. Аксиоматический подход к доказательству логических выражений в булевой
- •29. Доказательство логических выражений с помощью диаграмм Эйлера-Венна.
- •30. Доказательство логических выражений с использованием таблиц истинности.
- •31. Способы доказательства логических выражений с использованием специальных приемов.
- •32. Логика высказываний и операции логики высказываний.
- •33. Таблицы истинности операций логики высказываний.
- •34. Различия логики Буля и логики высказываний.
- •35. Метаязык логики высказываний и переход от импликативной формы к высказываниям на метаязыке.
- •36. Аксиомы, противоречия и тавтологии в логике высказываний.
- •37. Конструктивный подход к доказательству логических выражений в логике высказываний.
- •38. Минимальная нормальная форма, минимальное и трансверсальные покрытия в логике высказываний.
- •39. Доказательство логических высказываний с помощью метода резолюций.
- •40. Логика предикатов.
- •41. Минимизация логических выражений методом Куайна (Квайна).
- •42. Минимизация логических выражений в логике Буля путем склеивания в сднф и скнф. Показать, в чем различие склеивания в этих двух формах.
- •43. Асимптотические представления и анализ алгоритмов.
42. Минимизация логических выражений в логике Буля путем склеивания в сднф и скнф. Показать, в чем различие склеивания в этих двух формах.
Законы склеивания:
(минимизированная дизъюнктивная нормированная форма)=
(минимизированная конъюнктивная нормированная форма)=
В процессе минимизации некоторые аргументы пропадают. Импликанты получаются в результате склейки смежных констит-в отличных друг от друга всего одним тербом (переменной). В СДНФ склеиваются закрашенные смежные области, а в СКНФ - незакрашенные.
43. Асимптотические представления и анализ алгоритмов.
Очень часто для сравнения величин достаточно знать их приближенные значения. Для примера приведем гармонический ряд Hn=1+1/2+1/3+…+1/n=Σ1/k.
Hn→∞ очень медленно и всегда больше любого заданного числа. Точное значение можно вычислить только для конечного n.
H≈ln(n)+γ+1/2n-1/12n^2+1/120n^3-1/252n^4+… , где γ=0.5772156 – постоянная Эйлера
Из этого следует, что Hn близко к ln(n) при больших n.
Для анализа алгоритмов по времени выполнения используют обозначение O(f(n)), введенное в 1892 году П.Бахманом, которое позволяет заменять знак “≈” на “=”. Такое обозначение можно использовать всегда, когда n - целое и точное значение f(n) неизвестно.
Hn = ln(n)+y+O(1/n)
12 + 22 + 32 + … + n2 = (1/3)n(n+1/2)(n+1)=(1/3)n3 + (1/2)n2 + (1/6)n
1 + 22 + 32 + … + n2 = O(n3) или более точно (1/3)n3 + O(n2)
Таким образом, O помогает в работе с асимптотическими числами, т.к. позволяет кратко записать основной момент, отбросив незначительную информацию.
С некоторой осторожностью с этим символом можно оперировать по обычным арифметическим правилам.
Есть важное различие в односторонности равенства с символом О.
О(n2)=(1/2)n2 + n не имеет смысла, т.к. левая часть несет меньше смысла, чем правая.
Символ О часто используется для оценки времени выполнения алгоритма или количества итераций.
С символом О можно проводить операции:
f(n) = O(fn)
c*O(fn)=O(fn), где с = const
O(fn)+O(fn)=O(fn)
O(O(fn))=O(fn)
O(fn)*O(gn)=O(fn*gn)=fn*O(gn)