Алгоритмы - Сложные системы и ИИ

I. Написание и моделирование алгоритма

Анализ:

II. Парадигмы и стратегии программирования

III. Алгоритмические парадигмы

IV. Мультиагентное программирование

Содержимое спойлера

V. Упражнения и учебные пособия

VI. Краткое содержание курса

Контенус

Алгоритмический

Алгоритмика существовала всегда, это мыслительный процесс, описанный логически. Хотя эта система кажется нам сегодня существенной для многих наук, систематизация алгоритмического письма развивалась с течением времени и технологий. Оно началось еще во времена вавилонян, пока не было конкретно установлено Рене Декартом в общем методе, предложенном Беседа о методе в 1637 году.

Современная алгоритмика, включая так называемый «программный» язык, дебютировала вскоре после этого в 1677 году. Термин «алгоритм», которым мы пользуемся сегодня, появился два века спустя.

Алгоритм ХХ^е а также XXI^е века часто основывается на формализмах, таких как машины Тьюринга, которые обеспечивают научную основу для изучения свойств алгоритмов.

Наряду с компьютерами во второй половине XX века активно развивались алгоритмы. ХХ^е века и Дональд Кнут, автор трактата Искусство компьютерного программирования заложил основы математика строг в своем анализе.

Было разработано множество формальных или теоретических инструментов для описания алгоритмов, их изучения, выражения их качеств, возможности их сравнения:

алгоритмические структуры: управляющие структуры и структуры данных.
понятия правильности, полноты и прекращение.
теория сложность.

Структура управления и структура данных

Структура управления — это команда, которая управляет порядком выполнения различных инструкций алгоритма или компьютерной программы. Процессор отвечает за запоминание адреса следующей выполняемой инструкции, блоков (циклов, if и т. д.) или подпрограмм.

Эта последовательность инструкций также называется потоком выполнения программы, и ее можно представить с помощью график потока управления или автомат. Определенная парадигма программирования, обращающаяся к нескольким процессорам, затем подвергается проблеме распределения задач в процессорах.

Структура данных — это логическая структура, предназначенная для хранения данных, чтобы придать им организацию, позволяющую упростить их обработку. Существует много типов структур данных в зависимости от действий, которые над ними будут выполняться, мы не будем больше задерживаться на этом предмете.

Каждый компьютерный язык имеет тип структуры управления и структуры данных. Написание алгоритма очень часто основано на очень распространенных языках, таких как C, java и т. д.

Понятия прекращения, исправления, полноты

Завершение — это гарантия того, что алгоритм завершится за конечное время. Доказательства завершения обычно включают строго убывающую положительную целочисленную функцию на каждом шаге/итерации алгоритма.

Учитывая гарантию того, что алгоритм завершится, доказательство правильности должно обеспечивать уверенность в том, что если алгоритм завершается, давая предложенное решение, то это решение является правильным (в том смысле, что оно отвечает поставленной задаче).

Доказательство полноты гарантирует, что для данного проблемного пространства алгоритм, если он завершится, даст решение для каждого из элементов алгоритма.

Прекращение : алгоритм имеет временную сложность.

Коррекция : любой рассчитанный ответ алгоритма является решением задачи.

Полнота : алгоритм может вычислить ответ для любого экземпляра задачи.

Алгоритмическая сложность

Сложность алгоритма — это оценка стоимости выполнения алгоритма с точки зрения времени (временная сложность) или объема памяти (пространственная сложность). Таким образом, эффективность алгоритма зависит от этих двух критериев, которые мы постараемся свести к минимуму.

Алгоритмическая сложность позволяет узнать о внутренней эффективности
алгоритм: «естественная» производительность алгоритма вне среды, в которой он будет реализован.

Существует несколько типов анализа производительности алгоритма:

Оптимистический анализ (анализ в наиболее благоприятном случае или анализ в лучшем случае).
Усредненный анализ часто зависит от используемой парадигмы программирования.
Пессимистический анализ (анализ наихудшего случая или анализ наихудшего случая).

Классы сложности — это наборы задач, которые имеют свойство иметь одинаковую сложность по определенному критерию. Самые известные классы — это классы, определенные на машинах Тьюринга (детерминированных или недетерминированных — см. курс по автоматам) с ограничениями по времени и пространству. Существует связь между сложностью алгоритма и затратами энергии на его работу, называемая принципом Ландауэра.

Вот список наиболее часто встречающихся сложностей:

Рейтинг	Тип сложности
$О(1)$	постоянная сложность: задание, элементарный расчет и т.д.
$О (\ журнал (п))$	логарифмическая сложность: дихотомия, дерево
$Мы)$	линейная сложность: один цикл
$О (п \ лог (п))$	квазилинейная сложность: разделяй и властвуй, дерево
$О (п ^ {2})$	квадратичная сложность: вложение двух циклов
$О (п ^ {3})$	кубическая сложность: вложение трех петель
$О (п ^ р)$	полиномиальная сложность: вложение циклов без знания состояний
$О (п ^ {\ журнал (п)})$	квазиполиномиальная сложность: разделяй и властвуй
$О (2 ^ {п})$	экспоненциальная сложность: дерево, перебор
$Мы!)$	факторная сложность: наивный комбинаторный подход к перечислению