- •Постановка задачи.
- •Моделирование.
- •Построение алгоритма.
- •Программирование.
- •Отладка и тестирование программы.
- •Анализ результатов. Уточнение модели.
- •1_4. Анализ алгоритмов
- •§2. Размещения с повторениями
- •§3. Размещения без повторений
- •§4. Сочетания
- •Оценка алгоритма сортировки
- •Грамматика языков программирования
- •1_7. Из лекций.
- •1_11. Разработка объектно-ориентированного по
- •Поколения эвм
- •Архитектура процессора
- •Команды
- •Форматы команд
- •Понятие ассемблера
- •Система прерываний
- •Порты ввода/вывода
- •Устройства памяти эвм
- •Реляционная алгебра
- •Этапы разработки базы данных
- •Критерии оценки качества логической модели данных
- •Адекватность базы данных предметной области
- •Легкость разработки и сопровождения базы данных
- •Скорость операций обновления данных (вставка, обновление, удаление)
- •Скорость операций выборки данных
- •Функциональные зависимости отношений и математическое понятие функциональной зависимости
- •1Нф (Первая Нормальная Форма)
- •3Нф (Третья Нормальная Форма)
- •Типы параллелизма Параллелизм на уровне битов
- •Параллелизм на уровне инструкций
- •Стандарты mpi
- •Ключевые элементы
- •1.1 Основные понятия искусственного интеллекта.
- •1.2 История развития искусственного интеллекта
- •1.3 Задачи искусственного интеллекта
- •Направления исследований Символьное моделирование мыслительных процессов
- •Работа с естественными языками
- •Накопление и использование знаний
- •Биологическое моделирование
- •Робототехника
- •Машинное творчество
- •Другие области исследований
- •1.4 Экспертные системы - направление исследований по искусственному интеллекту
- •2.1 Типовая структура экспертных систем
- •2.2 Интерфейс пользователя.
- •2.6 Механизм логического вывода
- •2.7 Объяснение решений
- •3.2 Модели представления знаний.
- •23. Нейронные сети. Виды нейронных сетей. Алгоритмы обучения нейронных сетей. Применение нейронных сетей для задач распознавания образов.
- •24. Администрирование операционных систем Windows и Unix. Установка и настройка. Типовые задачи администрирования. Язык командного интерпретатора. Сетевые возможности Windows и Unix.
- •Установка и начальная настройка системы
- •Выбор режима установки
- •Выбор носителя дистрибутива системы
- •Командные языки и командные интерпретаторы
- •Базовые возможности семейства командных интерпретаторов
- •11. Протоколы прикладного уровня http, ftp, почтовые протоколы (smtp, pop3, imap-4), telnet .
- •Гипертекстовый документ
1_4. Анализ алгоритмов
Цели
Оценить качество алгоритмов с помощью количественных критериев
Сравнить различные алгоритмы для решения заданной алгоритмической задачи
Алгоритм - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели.
Алгоритм имеет исходные данные (вход алгоритма) и выдает некоторый результат
Алгоритмическая задача.
входные данные
необходимый результат.
Алгоритм называют правильным, если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи.
Сложность алгоритмов
Временная сложность алгоритма — количество элементарных шагов, которые он выполняет.
Объемная сложность алгоритма — количество оперативной памяти, необходимой для его выполнения.
Классы сложности алгоритмов
Труднорешаемые задачи
Не найден полиномиальный алгоритм.
Класс NP– задачи, проверяемые за полиномиальное время.
P=NP?
NP-полные задачи
Задача факторизации целого числа не является NP-полной
Примеры труднорешаемых задач
Задача о рюкзаке
Задан набор nпредметов с массамиmiи стоимостямиci. Максимальная масса рюкзакаM. Выбрать подмножество предметов так, чтобы
Σ mi≤MиΣ сi→max.
Задача коммивояжера
Имеется nгородов,nxnматрицаA= (aij) содержит попарные расстояния между городами. Найти замкнутый маршрут, содержащий все города по одному разу, и имеющий минимальную длину.
Методы анализа рекуррентных алгоритмов
Метод подстановки
Метод итераций
Анализ дерева рекурсии
Применение общей теоремы
Пример: сортировка слиянием
Под слиянием понимается объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.
Алгоритм сортировки
Сначала разделим массив пополам,
Отсортируем обе половины с помощью рекурсивного вызова
Выполним слияние отсортированных половин в один массив
Оценка сложности сортировки слиянием
T(n) = 2T(n/2) +n.
Предположим T(n) =O(nlogn).
T(n)≤cnlogn. Пусть оценка верна дляn/2.
T(n)≤ 2c(n/2)log(n/2)+n≤cnlog(n/2) +n≤cnlogn–cnlog2+n≤cnlogn
Теорема о рекуррентных соотношениях
a≥0,b>1 – константы,f(n) – функция,
T(n)=aT(n/b)+f(n), тогда
1)если f(n)=O(nlogba-ε) для некоторогоε>0, тоT(n) = Ө(nlogba)
2)если f(n)= Ө(nlogba), тоT(n) = Ө(nlogbalogn)
3)если f(n)=Ω(nlogba+ε) для некоторогоε>0 и еслиaf(n/b)<cf(n) для некоторого с<1 иn>n0, тоT(n) = Ө(f(n))
1_4 «Генерация комбинаторных объектов»
При решении практических задач часто приходится выбирать из некоторого конечного множества объектов подмножество элементов, обладающих теми или иными свойствами, размещать элементы множеств в определенном порядке и т. д. Эти задачи принято называть комбинаторными задачами.
Многие из комбинаторных задач решаются с помощью двух основных правил — суммы и произведения.
Правило сложения. Если удается разбить множество объектов на классы и каждый объект входит в один и только один класс, то общее число объектов равно сумме числа объектов во всех классах.
Правило умножения. Даны два произвольных конечных множества объектовАиВ. Количество объектов вА равноN, вВ —М. Составляются упорядоченные пары, где (а принадлежитА) и. Количество таких пар (объектов) равноN*M. Правило обобщается и на большее количество множеств объектов.
Определение:Перестановкойчисел от 1 доназывается последовательность длины, в котором они встречаются только один раз.
Например, рассмотрим все перестановки при .
123
132
321
312
213
231 Всего
Один из самых известных примеров использования генерирования перестановок является задача коммивояжера.
Задача коммивояжера. ИмеетсяNгородов. Известны расстояния между городами, записанные при помощи квадратной матрицы, где— расстояние отдогорода. Найти маршрут, проходящий через все города один раз, и вернуться с минимальной длиной.
|
12345678 75643218 34526718 … |
Для решения такой задачи необходимо найти перестановки чисел от 1 до . Для каждой такой перестановки считается длина и затем находится минимальная.
Задачу можно решить, перебрав все перестановки. Полиномиального алгоритма не придумано.