- •1.(30) Основные понятия мЛиТа
- •2. История развития теории алгоритмов.
- •3. Роль алгоритма в науке и технике.
- •4. Понятие алгоритма.
- •5. Алгоритмический процесс.
- •6. Основные вопросы теории алгоритмов.
- •7. Классификация алгоритмов.
- •8. Свойства алгоритмов.
- •9. Понятие предиката
- •10. Интерпретация. Модель
- •12. Нормальные алгорифмы Маркова.
- •13. Гипотеза Черча.
- •14. Машина Тьюринга.
- •15. Рекурсивные функции.
- •2) Тождественные функции любого числа независимых
- •16. Алгоритмически неразрешимые проблемы
- •17. Понятие о сложности
- •18. Временная и вычислительная сложность алгоритмов.
- •19. Понятие р- и np-задач.
- •21. Темпоральные логики. Нечеткая и модальные логики.
- •22. Примеры задач np-класса.
- •24. Дедуктивные теории
- •25. Свойства дедуктивных теорий
- •26. Формальные аксиоматические теории
- •27. Свойства выводимости
- •31.(38) Логические функции
- •34. Кванторы
- •39. Алгоритм Сортировка слиянием.
- •40. Алгоритм Пузырьковая сортировка.
- •41. Алгоритм Сортировка вставками.
- •42. Алгоритм Сортировка Шейкером.
- •43. Алгоритм Быстрая сортировка.
- •44. Алгоритм Сортировка подсчетом.
- •47. Логика высказываний.
- •48. Булева алгебра и основные логические тождества.
- •49. Пропозициональные буквы, связки и формы (формулы логики
- •50. Исчисление высказываний (теория l)
3. Роль алгоритма в науке и технике.
Было выявлено, что если удается получить алгоритм решения какой-либо
задачи, то эту задачу можно решать автоматически с помощью технических
устройств.
Таким образом, алгоритмы являются:
o формой изложения научных результатов;
o руководством к действию при решении уже изученных проблем;
o средством автоматического решения задач;
o инструментом, используемым при исследовании и решении новых
проблем;
o средством обоснования в математике;
o одним из средств описания сложных процессов.
Хотя алгоритмы важны для практики, практическая потребность не
является первичной при изучении и разработке алгоритмов. Часто они
разрабатываются для решения задач, которые не имеют пока практического
применения. Однако многие научные результаты, полученные без практики,
рано или поздно находят свое практическое применение.
4
4. Понятие алгоритма.
Существует два основных понятия алгоритма:
1 – интуитивное определение;
2 – формальное определение.
1. Алгоритм в интуитивном смысле – это точное предписание о
выполнении в определенном порядке некоторой последовательности
операций для решения всех задач некоторого заданного типа.
Содержание алгоритма, удобного для решения какой-либо задачи,
позволяет использовать его даже человеку-непрофессионалу. Кроме того, его
можно техническим устройством, выполняющим алгоритм автоматически
(ЭВМ по заданной программе).
Формализация понятия алгоритма не должна учитывать ограниченность
ресурсов, необходимых для его реализации, но требовать конечности этих
ресурсов, т. е. возможной реализации как таковой.
2. Формальное определение алгоритма дается на основе
математических методов и основывается либо на других понятиях, имеющих
математическое определение, либо на понятиях-аксиомах, не требующих
доказательства.
На основе свойств алгоритма можно сформулировать формальное
определение. Алгоритм – это правило, сформулированное на некотором
языке и определяющее процесс преобразования исходных данных в искомые
результаты (алгоритмический процесс). При этом допустимые исходные
данные представлены как предложения на языке исходных данных.
Алгоритм характеризуется:
понятностью для исполнителя;
массовостью, то есть допустимостью для него всех предложений на
языке описания исходных данных;
детерминированностью и другими свойствами.
Неточность интуитивного понятия заключается в неточности тех
терминов, через которые оно выражается, а именно:
язык;
понятность;
точность
интуитивные понятия,
смысл которых ясен, а научные
определения не составлены.
5
5. Алгоритмический процесс.
Алгоритмический процесс – это процесс последовательного
преобразования конструктивных объектов, происходящий дискретно.
Конструктивные объекты – это слова, числа, предложения, которые
описывают исходные данные, промежуточные результаты и конечные
данные.
Алгоритмический процесс состоит из конечного числа шагов, каждый из
которых является простым и выполняется за конечное время. Число шагов
алгоритмического процесса связано с количеством времени S(t),
затрачиваемого на их выполнение, а в ряде случаев и расходом других
ресурсов.
6