Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1716


Аннотация

Валентина Павловна Хиценко,

Татьяна Александровна Шапошникова

 

практикум на эвм

 

Алгоритмы

 

Учебное пособие

 

Редактор Т. П. Петроченко

Технический редактор Г. Е. Телятникова

Компьютерная верстка В.Ф. Ноздрева

Подписано в печать 29.04.2004.  Формат  60´84 1/16.  Бумага  офсетная.  Тираж 200 экз.  Уч.-изд. л. 6,75.  Печ. л. 7,0.  Изд. №  346.  Заказ №        .   Цена договорная.

 

 
Отпечатано в типографии

Новосибирского государственного технического университета

630092, г. Новосибирск, пр. К. Маркса, 20

 

 

Министерство образования Российской Федерации

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

 

Практикум на эвм

 

АЛГОРИТМЫ

 

Утверждено Редакционно-издательским советом университета

в качестве учебного пособия

для студентов I курса ФПМиИ

(направление 510200 – Прикладная математика

и информатика, специальность 351500 –

Математическое обеспечение и администрирование

информационных систем) дневной формы обучения

 

Новосибирск

2004

УДК 004.421+519.1](075.8)

         П 691

 

Авторы:   В. П. Хиценко, ст. преподаватель,

      Т. А. Шапошникова, ст. преподаватель

 

Рецензенты:  С.Х. Рояк, канд. техн. наук, доц.,

      Л.В. Тюнина, канд. техн. наук, доц.

 

Работа подготовлена на кафедре прикладной математики

 

          Практикум на ЭВМ. Алгоритмы

П 691    Учебное пособие / В.П. Хиценко, Т.А. Шапошникова. – Новосибирск: Изд-во НГТУ, 2004. – 112 с.

 

Рассмотрены основные алгоритмы, изучаемые в курсе «Практикум на ЭВМ»: алгоритмы на графах, комбинаторные алгоритмы, алгоритмы полного перебора. Разобрано много примеров, иллюстрирующих теоретический материал.

 

УДК 004.421+519.1](075.8)

 

 

 

 
© Новосибирский государственный

технический университет, 2004   

 

оглавление

Курс «Практикум на ЭВМ» является первой базовой дисциплиной среди программистских дисциплин. Нельзя овладеть программированием без знания важнейших и известнейших алгоритмов. В данном учебном пособии подробно разобраны алгоритмы, широко применяемые при решении разных классов задач: основные алгоритмы на графах, алгоритм полного перебора и методы его улучшения (алгоритмы динамического программирования, «жадный» алгоритм, метод ветвей и границ), алгоритмы формирования основных комбинаторных объектов.

Учебное пособие предназначено не только для студентов, изучающих начальные разделы программирования, но и для тех, кто желает обогатить свои навыки конструирования алгоритмов (вместо «изобретения очередного велосипеда»). Часто разница между плохим и хорошим алгоритмами более существенна, чем между быстрым и медленным компьютерами. Например, мы хотим отсортировать массив из миллиона чисел. Что быстрее – отсортировать его вставками на супер–компьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? При этом, если сортировка вставками написана на ассемблере чрезвычайно экономно, для сортировки n чисел нужно приблизительно 2n2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и требует 50·n· log n операций. В первом случае для сортировки 1 миллиона чисел получаем:

для супер–компьютера:

     

для домашнего компьютера:

     

Отсюда видно, что разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники.

Учебное пособие дополняет лекционный и практический материал дисциплины «Практикум на ЭВМ» и ориентировано прежде всего на поддержку самостоятельной работы студентов при выполнении РГР и курсовых работ. Поэтому каждый алгоритм, приведенный в учебном пособии, разобран на практическом примере, для некоторых приведена программная реализация на языке программирования (Си). Также для алгоритмов даны оценки их сложности.

Алгоритмы записаны в виде «псевдокода», прокомментированы в тексте, наглядно представлены на рисунках и в таблицах.