«Применение ит при оценке времени работы алгоритмов»

Скачать 208.64 Kb.

Название	«Применение ит при оценке времени работы алгоритмов»
страница	1/5
Дата публикации	26.04.2015
Размер	208.64 Kb.
Тип	Реферат

100-bal.ru > Информатика > Реферат

1 2 3 4 5

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по
«Основам информационных технологий»

Магистрант

кафедры дискретной математики

и алгоритмики

Ефимов Олег Валерьевич

Руководители:

доцент Сарванов Владимир Иванович,

ст. преп. Кожич Павел Павлович

Минск – 2008 г.

Список обозначений ко всей выпускной работе

P – класс полиномиально-разрешимых задач

NP – класс трудноразрешимых задач

SUN SPARC – архитектура компьютера компании SUN

C# – язык программирования на платформе .NET

Ruby – мультипарадигменный (объектно-ориентированный и функциональный) язык программирования

Java – язык программирования с собственной кросс-платформенной средой выполнения

C++ – язык программирования с возможностями реализации объектно ориентированных моделей

Оглавление

Список обозначений ко всей выпускной работе 2

Реферат на тему «Применение ИТ при оценке времени работы алгоритмов» 4

Введение 4

Глава 1. Обзор литературы 5

Глава 3. Оценка времени работы генетического алгоритма 7

Глава 4. Оценка времени работы алгоритма табуированного поиска 8

Глава 5. Результаты собственного исследования 9

Список литературы к реферату 10

Предметный указатель к реферату 12

Интернет ресурсы в предметной области исследования 13

Граф научных интересов 16

Презентация магистерской диссертации 16

Приложение А. Выдачи презентации 18

Реферат на тему «Применение ИТ при оценке времени работы алгоритмов»

Введение

В рамках данной статьи раскрывается значимость оценивания времени работы алгоритмов и рассматриваются некоторые практические случаи замеров времени работы на различных архитектурах компьютеров.

Как известно, в теории сложностей существует проблема определения сложностного статуса задачи, а именно, определение класса, к которому она принадлежит. Два основных класса это P и NP. Если задача принадлежит классу P, значит, существует эффективный (полиномиальный) алгоритм её решения. Если же задача принадлежит классу NP, то в предположении, что

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

Огромное множество задач, с которыми приходится иметь дело прикладной математике, не являются искусственно придуманными лишь для того, чтобы удовлетворить научный интерес исследователя, а приходят из различных производственно-экономических отраслей. Таким образом, производственно-экономический сектор является для прикладной математики основным потребителем результатов и одновременно основным поставщиком задач. Стоит ли упоминать, что время, за которое на производстве необходимо получать результаты, нередко сильно ограничено. Заказчики требуют решения задач за минимально возможное время, а если задача является трудноразрешимой (например, принадлежит классу NP), то можно пойти на компромисс: иногда получение решения достаточно быстро является важнее оптимальности полученного решения, т.е. субоптимальные решения, полученные приближёнными или эвристическими алгоритмами, могут оказаться вполне пригодными для практических нужд.

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

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

Немалое значение имеет также выбор компилятора языка программирования. Столь популярным в последнее время Ruby, Java и C# нередко достаточно сложно конкурировать по времени с тем же C++ в алгоритмах, требующих трудоёмких вычислений, хоть и отнюдь необязательно, что они будут производить эти вычисления дольше. Например, тому же C# требуется больше времени лишь при первой попытке вызова некоторого участка кода, потому что он тратит время на компиляцию этого участка на язык, понятный процессору, а далее запоминает скомпилированный код в памяти. Однако плюс в том, что в отличии от C++, компиляция происходит во время работы программы, а соответственно компилятор среды выполнения знает, на каком процессоре сейчас будет данный код выполнен, поэтому имеет возможность оптимизировать командные инструкции под данный процессор.

В настоящее время используются различные типы архитектур, такие как Intel, AMD, Sun SPARC и проч. Архитектуры разнятся типами используемых устройств компьютера, организацией памяти, связями основных логических узлов компьютера.

1 2 3 4 5

Добавить документ в свой блог или на сайт

Похожие:

	Применение ит при оценке мультипликативного эффекта экспортно-импортных... Реферат на тему «Применение ит при оценке мультипликативного эффекта экспортно-импортных потоков на основании сетевой модели» 6		Конспект урока определение и свойства алгоритма фио (полностью) Гайфулина... Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека
	Конспект по теме «Алгоритмы» Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека		Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
	Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов... ...		Фио группа Правильных ответов Тест №2 по «Оценке собственности» Вопрос... Экономика и бухгалтерский учет, 080112. 51 Маркетинг, 080501. 51 Менеджмент, 080108. 51 Банковское дело, 080504. 51 Государственное...
	Конспект урока по теме: "Способы записи алгоритмов". Фио (полностью)... Цель урока: Создание условий для формирования целостного представления и навыка работы по способам записи алгоритмов		На уроках русского языка необходимо вводить следующие этапы работы При этом речь идет не о заучивании простых алгоритмов, а о подлинной фундаментализации школьного образования, при которой акцент...
	Утверждается на заседании методического объединения. В процессе работы... Требования, устанавливаемые настоящим Положением, основаны на Уставе Учреждения и направлены на урегулирование отношений, возникающих...		Свойства степени с натуральным показателем Закрепить знание свойств степени с натуральным показателем, способствовать отработке алгоритмов умножения и деления степеней, возведение...
	Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые...		Реферат Марсианская техника в романе Герберта Уэллса «Война миров» ...
	Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	План-конспект урока алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Преподавание алгебры в 7 классе ведётся по умк «Алгебра 7 класс» под редакцией А. Г. Мордковича. Учебное пособие для изучения курса...		ПРИМЕНЕНИЕ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ ПРИ ПОДГОТОВКЕ К Экзаменам ДОКЛАД “ПРИМЕНЕНИЕ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ ПРИ ПОДГОТОВКЕ К ЕГЭ ФИЗИКЕ” Подготовил учитель физики Кюкяйской СОШ

Школьные материалы