vesnat.ru страница 1
скачать файл
Краткая аннотация дисциплины по выбору

«Сложность алгоритмов»

Автор: К.Н. Эминян



Каждый алгоритм А характеризуется тем, что на его вход могут поступать различные входные данные x, которые он преобразует в некоторые выходные данные y. При этом процесс работы А на входных данных х можно охарактеризовать некоторыми сложностными харак­теристиками LA(x) (число шагов алгоритма, объем используемой па­мяти и др.). Однако дать явное представление функции LA(x) для всех х обычно не представляется возможным. Даже поведение LA(x) как функции от х обычно трудно описать. Поэтому при анализе сложности алгоритмов часто рассматривают более грубые характеристики. Наи­более распространенным является следующий подход. Входные данные характеризуются некоторым натуральным параметром n их сложнос­ти (чаще всего n — длина представления входных данных некоторым заданным способом). Далее изучается функция LA(n), определяемая как максимум LA(x) по всем х с параметром п (сложность в худшем случае) или как некоторое среднее LA(x) по всем х с параметром п (средняя сложность). В этих случаях уже удается получать интерес­ные результаты.
скачать файл



Смотрите также:
«Сложность алгоритмов»
9.79kb.
4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность»
69.64kb.
1. Арифметическая сложность алгоритмов. Алгоритм Евклида, оценка его сложности (теорема Ламе). Квадратичные сравнения. Малая теорема Ферма. Символ Лежандра и его свойства. Вычисление символа Лежандра. Символ Якоби
16.76kb.
Информатика История Культурология Литературоведение Языкознание Информатика Библиотека алгоритмов
558.75kb.
Показать сложность понятия «время» иего влияние на жителей Земли. Сформировать понятия: «поясное время», «местное время», «часовой пояс», «линия перемены дат»
40.42kb.
Аутентификация. Способы аутентификации
36.27kb.
Примерный перечень тем
25.42kb.
Глубоков Александр Владимирович, к т. н. Мгту
223.34kb.
Зав кафедрой Тумковский С. Р
162.67kb.
Исследование свойств форматов и алгоритмов сжатия данных
54.37kb.
Профессиональная программа для создания dvd-video
9.47kb.
Проблема классификации речевых приемов, образуемых на основе принципа противоречия, остается не изученной. Исследователи лишь указывают на сложность классификации противоречия [Ганеев 2004: 80; Максимова 2005: 39-40]
34.05kb.