Практикум по решению задач на ЭВМ: Учебно-методическое пособие. Практикум по решению задач на ЭВМ: Учебно-методическое пособие Представление графов в ЭВМ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

«ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

__________________________________________________________________

«УТВЕРЖДАЮ»

Директор ИДО

«____»____________2007 г.

ПРАКТИКУМ НА ЭВМ

Рабочая программа, методические указания и контрольные задания для студентов специальностей 521600(080100) «Экономика», 060500(080109) «Бухгалтерский учет, анализ и аудит», 060700(080103) «Национальная экономика», 060800(080502) «Экономика и управление на предприятии», 061100(080507) «Менеджмент организации» Института дистанционного образования

Семестр
Самостоятельная работа, недели
Выполнение заданий, недели
Написание отчета, часы
Формы контроля

УДК 681.3:658.8

Практикум на ЭВМ: Рабочая программа, методические указания для студентов специальностей 521600(080100) «Экономика», 060500(080109) «Бухгалтерский учет, анализ и аудит», 060700(080103) «Национальная экономика», 060800(080502) «Экономика и управление на предприятии», 061100(080507) «Менеджмент организации». ИДО/ Сост. , . – Томск: Изд. ТПУ, 2007. – 23 с.

Рабочая программа, методические указания и контрольные задания рассмотрены и рекомендованы к изданию методическим семинаром кафедры экономики 12 апреля 2007 г., протокол

Зав. кафедрой, профессор, д. э. н.____________

Аннотация

Рабочая программа, методические указания и контрольные задания по производственной практике «Практикум на ЭВМ» предназначены для студентов специальностей 521600(080100) «Экономика», 060500(080109) «Бухгалтерский учет, анализ и аудит», 060700(080103) «Национальная экономика», 060800(080502) «Экономика и управление на предприятии», 061100(080507) «Менеджмент организации». Учебная практика проходится в четвертом семестре на ЭВМ в компьютерном классе обеспечивающей кафедры или филиала ИДО, длительность практики – 4 недели.

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

1. ЦЕЛИ И ЗАДАЧИ ПРОИЗВОДСТВЕННОЙ ПРАКТИКИ

Цели проведения производственной практики

Учебная практика «Практикум на ЭВМ» предназначена для закрепления навыков по применению информационных технологий . За время ее прохождения студенты знакомятся со структурой экономической информационной системы , с информационными ресурсами, общей характеристикой и классификацией информационных технологий, используя в своей работе приложения Microsoft Office. Практика имеет важное значение в подготовке экономиста , способствует успешному выполнению программы непрерывного использования ЭВМ в учебном процессе. Особое внимание уделяется самостоятельной работе и привитию практических навыков с широким использованием ЭВМ. Для закрепления и проверки полученных навыков практикум содержит дополнительные задания, которые студенты должны выполнить и результаты представить в отчете.

Задачи, выполняемые в ходе учебной практики

За время практики студенты выполняют задания по обработке экономической информации и проведению финансовых расчетов в Excel, созданию баз данных и работы с ними в среде СУБД Access.

Прохождение учебной практики «Практикум на ЭВМ» включает:

а) самостоятельную работу над учебными пособиями , методическими указаниями;

б) выполнение самостоятельных заданий и контрольного задания;

г) защиту практики.

Тема 1. Информационные технологии

1. Информация, технология.

2. Экономическая информационная система.

3. Концептуальная модель информационной технологии.

4. Информационные ресурсы и свойства информационных технологий.

5. Классификация информационных технологий.

Тема 2. Обработка экономической информации в Excel

1. Подготовка и редактирование экономической информации.

2. Простейшие вычисления в таблицах Excel.

3. Подготовка отчетов для бизнес-анализа.

Тема 3. Финансовые расчеты в Excel

1. Начисление процентных ставок.

2. Анализ инвестиций.

3. Прогнозирование значений временного ряда .

Тема 4. Система управления базой данных Access

1. Основные понятия СУБД Access.

2. Рабочая среда базы данных Access.

3. Создание таблиц средствами Access.

4. Создание простейших форм и их использование.

5. Поиск информации и создание запросов.

6. Создание отчетов.

Во время прохождения практики выполняются задания по нижеприведенным темам. Каждый студент должен выполнить по одной задаче из приведенных заданий для самостоятельной работы. Номер задачи указывает руководитель практики. Учебная практика проводится на персональных ЭВМ и заключается в практическом использовании студентами компьютерных программных продуктов (Microsoft Office).

Тема 2 . Обработка экономической информации в Excel

Подготовка и редактирование экономической информации

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

2. Создать таблицу, фиксирующую результаты сессии и включающие следующие данные: фамилию, имя, отчество, дату сдачи экзамена, название предмета, результат сдачи (число). В сессию было 4 экзамена.

3. Создать таблицу, содержащую следующие сведения о поставке фирмой товаров продовольственной группы: наименование товара, стоимость за единицу (р.), количество (шт., кг), название фирмы - покупателя, фамилию, имя, отчество дилера, дату поставки. Таблица должна содержать не менее десяти видов товаров.

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

Задания для самостоятельной работы

Тема 3. Финансовые расчеты в Excel

В условиях соответствующих самостоятельных заданий для раздела «Подготовка и редактирование экономической информации» найти:

1. Возраст владельцев транспортных средств (ТС), общую стоимость всех ТС, средний пробег ТС, дату выпуска самого нового и самого старого ТС.

2. Средний балл, полученный на экзаменах, дату первого экзамена, –дату последнего экзамена.

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

4. Стоимость всех товаров на складе, дату поступления товара, дольше всех хранящегося на складе, общее количество товара, цену самого дорогого товара.

Тема 4. Система управления базой данных Access

Задания для самостоятельной работы

При помощи СУБД Access создать:

1. Базу данных реализации продукции коммерческой организацией за указанный период.

Имена полей : дилер, сумма поставки, количество поставок, дата поставки, номер накладной, клиент.

Таблицы : Дилер, Клиент.

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

Имена полей : наименование товара, количество, цена за ед., поставщик, дата поставки.

Таблицы : Товары, Поставщики.

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

В форме дилер (задание 1) и наименование товара (задание 2) создать кнопки: Вперед по записям , Назад по записям , Поиск , Выход .

4. КОНТРОЛЬНАЯ РАБОТА

4.1. Общие методические указания

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

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

Оформление отчета производится в соответствии с общими требованиями оформления отчетов (см. п. 6.)

4.2. Методические указания и варианты контрольных заданий

Задание № 1

Торговая фирма в текущем месяце осуществила поставку продукции N клиентам на общую сумму S р. с предоставлением торгового кредита сроком на один месяц под процент Pi . Определить:

· прибыль фирмы от этого кредита;

· чистую прибыль, при условии, что налог на прибыль 20 %;

· прибыль при росте инфляции 1 % в месяц;

· сменить условия кредитования для полученного уровня инфляции так, чтобы фирма имела прибыль 10 % .

Значения S 1 , S 2 ,…, SN задать произвольно так, чтобы .

Значения Pi взять из интервала:

Исходные данные для вариантов задания приведены в таблице 1. Таблица 1

№ варианта	Сумма поставки	Количество клиентов N

Пример выполнения

Пусть данные о совершенных продажах заданы таблицей 2

Таблица 2

Клиент	Сумма продаж, р.	Процент

Для выполнения задания необходимо провести следующие расчеты:

Прибыль = 13350 р.

Налог на прибыль = 2670 р.

Чистая прибыль = 10680 р.

Чистая прибыль при инфляции 1 % https://pandia.ru/text/78/464/images/image009_63.gif" width="351" height="41">=7,92 %

Рис. 4.1. Выполнение задания № 1 в Excel

Задание № 2

Товарные запасы приобретаются предприятием 4 раза в течение операционного цикла (N 1, N 2, N 3, N 4). Запасы на начало (нач. остаток) составляют N 0 единиц. Движение запасов (количество, цена, стоимость) по периодам задаются табл. 3.

Определить:

· товарные запасы N за период поступления и их стоимость по ценам поступления S ;

· остаток товаров R на конец периода;

· стоимость остатка товаров тремя методами – средневзвешенным, LIFO, FIFO, если было реализовано 500 единиц товара;

· стоимость остатка товаров тремя методами – средневзвешенным, LIFO, FIFO, если было реализовано 100 единиц товара.

Таблица 3

Показатели	Количество	Цена за ед., р.	Стоимость по ценам поступления, р.
Остаток (начальный)
Реализация
Остаток (конечный)

Исходные данные для вариантов задания приведены в таблице 4.

Таблица 4

№ варианта	N 0				N 4

Данное учебное пособие содержит комплект лабораторных работ по дисциплине "Практикум по решению задач на ЭВМ". Практикум по решению задач на ЭВМ изучается в девятом и десятом семестрах и является составной частью непрерывной компьютерной подготовки студентов. С одной стороны, он опирается на знания, полученные при изучении классических математических дисциплин (алгебра, геометрия, математический анализ, теория вероятностей), а с другой стороны, на знания основ информатики и вычислительной техники, приобретенные в процессе обучения дисциплинам: информатика, программирование, программное обеспечение ЭВМ. Основная цель практикума - сформировать у студентов практические умения и навыки в решении прикладных задач на персональных компьютерах. В пособии большое внимание уделяется разбору примеров решения задач. Прилагаются вопросы и задачи для самостоятельного решения. Для самопроверки в пособии приведены два варианта типовых контрольных работ в рамках изучаемого материала.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.

Министерство образования и науки РФ Федеральное агентство по образованию РФ Московский государственный областной университет Елецкий государственный университет имени И. А. Бунина Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. Москва – Елец 2005 УДК Печатается по решению редакцион- 002 но-издательского совета Елец- ББК кого государственного уни- 22.18 верситета им. И.А. Бунина прото- Т19 кол № 5 от 30 ноября 2005 года Рецензенты: доктор физико-математичеких наук, профессор кафедры алгебры и геометрии Меренков Ю.Н. (ЕГУ им. И.А. Бунина); доктор физико-математических наук, профессор, ведущий сотрудник Вычислительного центра им. А.А. Дородницына – РАН Дикусар В.В. (Мо- сква); кандидат физико-математических наук, старший преподаватель ка- федры уравнений в частных производных и теории вероятностей Малю- тина О.П. (ВГУ, Воронеж) Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. Т19 Практикум по решению задач на ЭВМ: Учебно-методическое посо- бие. – Елец: ЕГУ им. И.А. Бунина, 2005. – 194 с. ISВN 5-7017-0825-Х При изучении дисциплины «Практикум по решению задач на ЭВМ» студенты сталкиваются с трудностями, связанными с отсутствием необхо- димой литературы по отдельным темам в библиотеке. Данное учебное по- собие содержит комплект лабораторных работ по дисциплине. Большое внимание уделяется разбору примеров решения задач. Прилагаются во- просы и задачи для самостоятельного решения. Для самопроверки в посо- бии приведены два варианта типовых контрольных работ в рамках изучае- мого материала. Данное учебно-методическое пособие адресовано студентам дневного и заочного отделений физико-математических факультетов университетов. УДК 002 ISВN 5-7017-0825-Х ББК 22.18 © ЕГУ им. И.А.Бунина, 2005 © Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В., 2005 © МГОУ, 2005 © издательство МГОУ, 2005 Практикум по решению задач на ЭВМ Содержание ВВЕДЕНИЕ 5 ЧАСТЬ I Программирование на языке высокого уровня 9 семестр Язык программирования Pascal. Теоретический материал 7 1. Арифметика действительных чисел Вычис- 2 часа 25 ления по формулам 2. Разветвления 2 часа 27 3. Простейшая целочисленная арифметика 2 часа 31 4. Простейшие циклы 2 часа 35 5. Простейшие графические построения 2 часа 39 6. Пошаговый ввод данных и вывод результатов 2 часа 42 7. Сочетания цикла и развилки 2 часа 46 8. Обработка последовательностей символов 2 часа 51 9. Вычисления с хранением последовательно- 2 часа 56 стей значений 10. Вложенные циклы 2 часа 59 11. Вложенные циклы в матричных задачах 2 часа 62 12. Использование процедур 2 часа 66 13. Файлы 4 часа 69 14. Вычисления с хранением последовательно- 4 часа 75 стей, число членов которых зависит от исход- ных данных 15. Контрольная работа №1 2 часа 79 16. Целые числа 4 часа 81 17. Системы счисления 4 часа 88 18. Геометрия 6 часов 96 19. Сортировка массивов и файлов 4 часа 99 10 семестр 20. Многочлены 2 часа 101 21. Преобразование и построение матриц 4 часа 103 22. Матричная алгебра 4 часа 105 23. Численные методы 10 часов 110 24. Случайные числа 4 часов 124 25. Вычисления с некоторой точностью 4 часа 127 26. Графика 2 часа 130 27. Графика и движение 6 часов 137 28. Игры 2 часа 144 ЧАСТЬ II Математические вычисления в MathCAD Математические вычисления в MathCAD. Теоретический материал. 146 29. Введение в MathCAD 4 часа 162 3 Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. 30. Контрольная работа №2 2 часа 164 31. MathCAD Задачи линейной алгебры 10 часов 166 32. MathCAD Задачи математического анализа 10 часов 167 33. MathCAD Обыкновенные дифференциальные 10 часов 168 уравнения 34. MathCAD Задачи математической стати- 4 часа 170 стики ЗАКЛЮЧЕНИЕ 171 БИБЛИОГРАФИЯ 172 ПРИЛОЖЕНИЕ Рабочая программа по дисциплине 174 «Практикум по решению задач на ЭВМ» ВВЕДЕНИЕ Практикум по решению задач на ЭВМ изучается в девятом и десятом семестрах и является составной частью непрерывной компьютерной под- готовки студентов. С одной стороны, он опирается на знания, полученные при изучении классических математических дисциплин (алгебра, геомет- рия, математический анализ, теория вероятностей), а с другой стороны, на знания основ информатики и вычислительной техники, приобретенные в процессе обучения дисциплинам: информатика, программирование, про- граммное обеспечение ЭВМ. Основная цель практикума – сформировать у студентов практические умения и навыки в решении прикладных задач на персональных компью- терах. Перед студентами ставятся следующие задачи: закрепить и углубить навыки программирования для ПЭВМ (язык программирования Pascal); углубить и систематизировать представление о применении новых информационных технологий в приложениях математики; получить опыт построения простейших математических моделей и их реализации на ЭВМ (вычислительный эксперимент); научиться решать на ПЭВМ классические задачи геометрии, алгеб- ры, матричной алгебры, а также сортировки массивов и файлов; получить навыки решения на ПЭВМ задач, относящихся к специаль- ным разделам математики и информатики: численные методы; слу- чайные числа; графика и движение; компьютерные игры. Данное учебно-методическое пособие состоит из двух частей: первая часть представляет собой набор из двадцати семи лабораторных работ, ориентированных на программирование на языках высокого уровня, вто- рая часть рассчитана на вычисления в математических пакетах и состоит из пяти лабоаторных работ. Всего пособие содержит тридцать две лабора- торных работы, каждая из которых включает примеры решения заданий и задачи для самостоятельного решения. 4 Практикум по решению задач на ЭВМ Для организации самопроверки в пособие включены две контрольные работы, рассчитанные на два варианта каждая. Обе части содержат теоретический материал, соответствующий их те- матике. Учебно-методическое пособие основано на материале, изучаемом сту- дентами в рамках дисциплины: «Практикум по решению задач на ЭВМ» в течение ряда лет. При составлении задач использовался сборник задач следующих авто- ров: С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. Авторы учебно-методического пособия выражают благодарность пре- подавателям и асситсентам кафедры вычислительной математики и ин- форматики ЕГУ имени И.А. Бунина за помощь в постановке лабораторных работ. ЧАСТЬ I Программирование на языке высокого уровня Теоретический материал: Язык программирования Pascal Язык Паскаль создан Н. Виртом в 1971 году. Он играет особую роль и в практическом программировании и в его изучении. Существует много вер- сий языка Паскаль. Любая программа на Паскале является текстовым фай- лом с собственным именем и расширением.pas. Она имеет вид последова- тельности символов латинских и русских букв, арабских цифр, знаков опе- раций, скобок, знаков препинания и некоторых дополнительных символов. Схематически программа представляется в виде последовательности вось- ми разделов: 1. заголовок программы (начинается со слова program); 2. описание внешних модулей, процедур и функций; 3. описание меток; 4. описание констант (начинается со слова const); 5. описание типов переменных (начинается со слова var); 6. описание переменных; 7. описание функций и процедур; 8. раздел операторов (начинается со слова begin). Не в каждой программе обязательно присутствуют все разделы. Каж- дый раздел начинается со служебного слова, назначение которого зафик- сировано так, что его нельзя употреблять для других целей. Программа за- канчивается служебным словом end, после которого ставится точка. Опи- сания величин и операторы отделяются друг от друга точкой с запятой. Для обозначения величин используются имена. Они состоят из латинских букв и цифр, причем первым символом должна быть буква. Имя програм- мы выбирается автором и составляется по тому же правилу. Постоянные величины бывают числовыми или символьными. Значения символьных ве- 5 Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. личин заключаются в апострофы. Постоянные величины описываются в разделе констант по схеме: const<имя>=<константа>. Данные, обрабаты- ваемые программой, могут быть разных типов. Тип определяет область допустимых значений, а также операторы и функции, применимые к вели- чине. В Паскале имеется несколько встроенных простых типов со стан- дартными именами. Скалярный тип – тип, значения которого можно перечислить в некото- ром списке. Для них определена порядковая функция ord(x) – номер зна- чения х в списке (для целочисленного х ord(x)=x), pred(x) – значение в списке, предшествующее х, succ(x) – значение в списке, следующее за х. Упорядоченный тип – тип, значения которого упорядочены в обычном смысле. К ним применимы операции отношения <,>,<=,>=,<>. Для логиче- ских величин выполняется неравенство false:<тип>. Имена в списке разделяются запя- той. Над целыми величинами (тип integer) определены операции: *, div (де- ление нацело), mod (деление с остатком), +, - (приведены в порядке стар- шинства). Над вещественными величинами (тип real) определены: *, +, -, /, а также функции при вещественном или целом аргументе: abs(x), sqr(x), sin(x), cos(x), arctan(x), ln(x), exp(x), sqrt(x), int(x), random. Они дают веще- ственный результат. Над логическими величинами (тип string) определены операции: not - отрицание, and - конъюнкция, or - дизъюнкция. Логическая функция odd(x) принимает значение true, если целочисленное х является нечетным, false - если четным. Множество всех символов образуют символьные величины (тип char) которые являются упорядоченными. Выражения - это конструкции, которые задают правила вычисления значений переменных. Они строятся из переменных, констант, функций с помощью операций и скобок. Основные конструкции. Следование - реализовывается с помощью составного оператора: begin <последовательность операторов> end. Развилка – реализовывается с помощью условного оператора и оператора варианта (выбора). Структура условного оператора: if <логическое выражение> then <оператор 1> else <оператор 2> Оператор варианта имеет форму: 6 Практикум по решению задач на ЭВМ case <выражение> of <список констант 1>:<оператор 1>; <список констант 2>:<оператор 2>; ……………… <список констант N>:< оператор N > end. Для реализации циклов имеются три оператора. Если число повторений из- вестно заранее, то используют цикл с параметром: 1) for <параметр>:= <выражение 1> to <выражение 2> do <оператор>, 2) for <параметр>:= <выражение 1> downto <выражение 2> do <оператор>; в других случаях используют цикл с предусловием: while <логическое выражение> do <оператор>, (действие: вычисляется значение логического выражения, ес- ли оно истинно, то выполняется оператор, после чего снова вычисляется значение логического выражения, в противном случае действие заканчива- ется); или цикл с постусловием: repeat <последовательность операторов> until <логическое выражение>, (действие: выполняется последователь- ность операторов, далее вычисляется значение логического выражения, ес- ли оно истинно, то действие заканчивается, в противном случае снова вы- полняется последовательность операторов). Массивы. Составные типы величин образуются из других типов, при этом существенную роль играет метод образования или структура состав- ного типа. Часто используемый составной тип – массив. Массив – это по- следовательность, состоящая из фиксированного числа однотипных эле- ментов. Все элементы массива имеют общее имя и различаются индекса- ми. Индексы можно вычислять. При описании массивов используются слова: array и of. В описании массива указывается тип его элементов и ти- пы индексов: type <имя массива>=array [<список типов индексов>] of <тип элементов>. Число индексов называется размерностью массива. Об- ращение к элементу массива осуществляется с помощью задания имени переменной, за которым следует заключенный в квадратные скобки список индексов элемента. Пример. Рассмотрим задачу упорядочения членов числовой последова- тельности по какому-либо признаку (по возрастанию). Используем метод, носящий название «пузырек». Для этого будем рассматривать пары эле- ментов последовательно слева направо и переставлять элементы в паре, если они стоят неправильно. В начале присвоим некоторой логической пе- ременной значение p:=true, если при просмотре пар была хотя бы одна пе- рестановка изменим значение логической переменной. Цикл заканчивает- ся, если после очередного просмотра выполняется условие: p=true. 7 Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. Программа: Program bubble; const a: array of integer=(19,8,17,6,15,4,13,2,11,0); var b, I: integer; p: Boolean; begin clrscr; for I:=1 to 10 do while (a[I]:3); writeln; writeln; repeat p:=true; for I:=10 downto 2 do if a[I] (<список описаний формальных параметров>). Описание параметров имеет вид <список имен>: <тип> или var <список имен>: <тип>. В первом случае говорят о параметрах-значениях, во втором – о параметрах-переменных. В простейшем случае заголовок процедуры со- держит только ее имя. Оператор вызова процедуры имеет вид: <имя процедуры> (<список выражений>). Указанные выражения называют фактическими параметрами. Их список должен точно соответствовать списку описаний формальных параметров процедуры. Во время вызова процедуры каждому параметру-значению присваивается значение соответ- ствующего фактического параметра, и поэтому их обычно используют для передачи входных данных. Переменные-параметры следует использовать для представления результатов процедуры. 8 Практикум по решению задач на ЭВМ Функция – это подпрограмма, определяющая единственное скалярное, вещественное или строковое значение. Отличия функции от процедуры: заголовок функции начинается со служебного слова function и за- канчивается указанием типа значения функции; раздел операторов функции должен содержать хотя бы один опера- тор присваивания имени функции; обращение к функции – не оператор, а выражение вида <имя функции> (<список фактических параметров>). Функции и процедуры могут использовать свое имя в собственном опи- сании, т. е. могут быть рекурсивными. Работа с файлами. Файл (последовательность) - это одна из наиболее фундаментальных структур данных. Программная организация компьюте- ров, их связь с внешними устройствами основаны на файловой структуре. Файлы позволяют решить две проблемы: 1) возможность формирования и сохранения значений для последую- щего использования другими программами (например, в программах многократной обработки информационных систем, таких как платеж- ные ведомости, различные АСУ, базы данных, необходимость длительно- го хранения информации очевидна); 2) взаимодействие программ с внешними устройствами ввода-вывода: дисплеем, принтером, АСП и т.п. В Паскале эти проблемы снимаются с помощью структурированных дан- ных файлового типа. Файловый тип данных в программе задается следующем образом: type <имя файлового типа>= file of <тип компонентов> В качестве типа компонентов файла разрешается использовать любой тип данных, кроме файлового. Например: type intfile=file of integer; refile=file of real; chfile=file of char; ran=1..10; st=set of ran; vector=array of real; compl=record; re,im: integer; end; setfile=file of st; vecfile=file of vector; compfile=file of compl; Описание файловой переменной задается обычным способом в разделе 9 Тарова И.Н., Терехов Ю.П., Масина О.Н., Скоков А.В. описаний. Например: Var f: intfile; или var f: file of integer. Файловая переменная является буфером между Паскаль-программой и внешним устройством и должна быть логически с ним связана. Связь осуще- ствляется оператором языка Паскаль: assign (<имя файловой переменной>,"<имя устройства>") Как правило, файлы для хранения данных связаны с устройством внешней памяти на магнитных носителях (дисковод) и носят название внешние фай- лы. Если, например, файл с именем primer.dat логически связан с дисково- дом А:, то все данные, помещаемые в файл, будут храниться на этом дис- ковом накопителе, а установка «окна» между программой и файлом будет определяться через файловую переменную f оператором assign (f, "primer.dat") Если внешним устройством является принтер, то связь осуществляется оператором assign(f, "1st:"). Здесь 1st - логическое имя печатающего устрой- ства. Ниже приветны логические имена внешних устройств ввода-вывода: con - консоль; trm - терминал; kbd - клавиатура; 1st - принтер; aux - бу- фер сети; usr - драйвер пользователя. После осуществления связи файловая переменная f отождествляется с соответствующим файлом. Для работы с файлом его необходимо открыть, а по окончании работы - закрыть. Файл открывается для чтения операто- ром reset(f), для записи - оператором rewrite(f). Чтение и запись данных осуществляется известными командами read/write, только в начале списка помещается имя файловой переменной: read (f, <список ввода>); readln (f, <список ввода>); write(f, <список вывода>); writeln(f, <список вывода>). Закрытие файла осуществляется командой close(f). Условно файл можно представить в виде ленты, у которой есть начало, а конец нe фиксируется. Компоненты файла записываются на эту ленту последовательно, дpyr за другом: … M. F0 F1 F2 F3 K. ^T.M. Здесь т.м. - текущий маркер, указывающий на рабочую позицию (окно) файла; м.к. (маркер конца файла) - специальный код, автоматически фор- мируемый вслед за последним элементом файла. Такого рода файлы называются файлами последовательного доступа. В исходной версии Паскаля файлов прямого доступа, для которых можно непосредственно «достать» любую компоненту, не предусмотрено; однако, в Турбо-Паскале элементы прямого доступа есть (например, через функ- цию seek). Команда rewrite(f) - открыть файл для записи - устанавливает файл в начальное состояние режима записи; текущий маркер устанавливается на 10

(Документ)

Каруна С.Н., Шапошникова С.В. Практикум по дисциплине Мировая экономика (Документ)

(Документ)

Бобцов А.А., Болтунов Г.И. и др. Управление непрерывными и дискретными процессами (Документ)

Могилев А.В., Пак Н.И., Хённер Е.К. Практикум по информатике (Документ)

Кириллов В.В. Архитектура базовой ЭВМ (Документ)

Трушин Н.Н. Аппаратное обеспечение ЭВМ, средств телекоммуникаций и сетей (Документ)

Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ (Документ)

Хокни Р., Джессхоуп К. Параллельные ЭВМ: Архитектура, программирование, алгоритмы (Документ)

Зайцев В.Ф. Кодирование информации В ЕС ЭВМ (Документ)

n1.doc

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

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

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

АЛГОРИТМЫ

Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
для студентов I курса ФПМиИ
(направление 510200 – Прикладная математика
и информатика, специальность 351500 –
Математическое обеспечение и администрирование
информационных систем) дневной формы обучения

Новосибирск
2004

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

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

Л.В. Тюнина, канд. техн. наук, доц.
Работа подготовлена на кафедре прикладной математики

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

П 691 Учебное пособие / В.П. Хиценко, Т.А. Шапошникова. – Новосибирск: Изд-во НГТУ, 2004. – 112 с.
Рассмотрены основные алгоритмы, изучаемые в курсе «Практикум на ЭВМ»: алгоритмы на графах, комбинаторные алгоритмы, алгоритмы полного перебора. Разобрано много примеров, иллюстрирующих теоретический материал.

УДК 004.421+519.1](075.8)

Новосибирский государственный
технический университет, 2004
оглавление

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

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

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

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

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

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

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

1. Основные алгоритмы на графах

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

1.1. Некоторые основные определения

Графом (неориентированным графом) G (V , E ) называется совокупность двух множеств, где V – конечное непустое множество элементов, называемых вершинами, а E – множество неупорядоченных пар различных элементов множества V (эти пары называются ребрами). Граф, состоящий из одной вершины, называется тривиальным .

Говорят, что ребро e = (u , v ) соединяет вершины u и v . Ребро e и вершина u (а также e и v ) называются инцидентными , а вершины u и v – смежными . Ребра, инцидентные одной и той же вершине, также называются смежными .

Степень вершины – это число ребер, инцидентных ей. Вершина графа, имеющая степень 0, называется изолированной , а имеющая степень 1, – висячей .

Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами , а граф – мультиграфом .

Если элементом множества E может быть пара одинаковых (не различных) элементов V , то такой элемент E называется петлей. Псевдограф – это граф, у которого наряду с кратными ребрами допускаются и петли, причем даже несколько петель при одной вершине.

Граф называется простым , если любая пара вершин соединена не более чем одним ребром и граф не имеет петель.

Маршрут (путь ) – это чередующаяся последовательность

a = v 0 , e 1 , v 1 , e 2 , ..., v n – 1 , e n , v n = b

Вершин и ребер графа такая, что e i = (v i- 1 , v i ), 1 ? i ? n . Говорят, что маршрут соединяет вершины a и b – концы маршрута. В простом графе маршрут можно задать перечислением лишь его вершин a = v 0 , v 1 , …, v n = b или его ребер e 1 , e 2 , …, e n .

Маршрут называется цепью , если все его ребра различные. Маршрут называется замкнутым , если v 0 = v n .

Замкнутая цепь называется циклом . Цепь называется простой , если не содержит одинаковых вершин. Простая замкнутая цепь называется простым циклом.

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа.

Вершина u достижима из вершины v , если существует путь из v в u .

Длина пути v 0 , v 1 , …, v n равна числу его ребер, т.е. n .

Расстояние между двумя вершинами – это длина кратчайшего пути, соединяющего эти вершины.

Часть графа G (V , E ) – это такой граф G "(V ", E "), что V "  V и E "  E .

Подграфом графа G называется такаяего часть G " , которая вместе со всякой парой вершинu, v содержит и ребро (u , v ) , если оно есть в G .

Дополнением графа G называется граф G " с тем же множеством вершин, что и у G , причем две различные вершины смежны в G " тогда и только тогда, когда они несмежны в G . Ребра графов G и G " вместе образуют полный граф. Граф называется полным , если любые две его вершины смежны.

Два графа G 1 и G 2 изоморфны , если существует взаимно однозначное отображение множества вершин графа G 1 на множество вершин графа G 2, сохраняющее смежность.

Граф называется связным, если для любой пары вершин существует соединяющий их путь. Максимальный связный подграф несвязанного графа называется компонентой связности данного графа.

Если задана функция F : V ?M , то множество M называется множеством пометок, а граф – помеченным . Если задана функция F : E ?M , т.е. ребрам графа приписаны веса, то граф называется взвешенным .

Ребро графа называется ориентированным , если существен порядок расположения его концов. Граф, все ребра которого ориентированные, называется ориентированным графом (или орграфом ). В этом случае элементы множества V называются узлами , а элементы множества E – дугами . Дуга (u , v ) ведет от вершины u к вершине v , Вершину v называют преемником вершины u , а u – предшественником вершины v . Понятия части орграфа, пути, расстояния, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг.

Источник орграфа – это вершина, от которой достижимы все остальные вершины. Сток орграфа – это вершина, достижимая со всех других вершин.

Деревом называется связный граф без циклов.

Корневое дерево – это связный орграф без циклов, удовлетворяющий условиям:

1. 
   имеется единственная вершина, называемая корнем, в которую не входит ни одна дуга;
2. 
   к каждой некорневой вершине ведет одна дуга.

Вершины, из которых не выходит ни одна дуга, называются листьями .

1.2. Представление графов в ЭВМ

Представление в программе объектов математической модели – это важная составляющая программирования. Выбор наилучшего представления определяется требованиями конкретной задачи. Известны различные способы представления графов в памяти компьютера. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Следует заметить, что во многих задачах на графах выбор представления – решающий для эффективности алгоритмов. На рис. 1.1 для неориентированного (а, б, в, г ) и ориентированного (д, е, ж, з ) графов показаны различные представления: б, е – матрица смежности; в, ж – матрица инцидентности; г – список смежности неориентированного графа при смежном размещении элементов списка; з – список смежности ориентированного графа при связанном размещении элементов списка.

1.2.1. Матрица смежности графа

Матрицей смежности помеченного графа с n вершинами называется матрица A = [a ij ], i , j = 1, 2, ..., n , в которой

Матрица смежности однозначно определяет граф (рис. 1.1, а–в , д–е ). Для неориентированного графа матрица A является симметричной относительно главной диагонали. Число единиц в строке равно степени соответствующей вершины. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.

Преимуществом такого представления является «прямой доступ» к ребрам графа, т.е. имеется возможность за один шаг получить ответ на вопрос «существует ли в графе ребро (x , y ) ?» Для небольших графов, когда места в памяти достаточно, с матрицей смежности часто проще работать. Недостаток заключается в том, что независимо от числа ребер объем занимаемой памяти составляет n  n или n  n /2 – n , если использовать симметрию и хранить только треугольную подматрицу матрицы смежности. Кроме того, каждый элемент матрицы достаточно представить одним двоичным разрядом.

1.2.2. Матрица инцидентности графа

Матрицей инцидентности называется матрица B = [b ij ], i = 1, 2, ..., n , j = 1, 2, ..., m (где n – число вершин, а m – число ребер графа), строки которой соответствуют вершинам, а столбцы – ребрам. Элемент матрицы в неориентированном графе равен:

В случае ориентированного графа с n вершинами и m дугами элемент матрицы инцидентности равен:

Строки матрицы также соответствуют вершинам, а столбцы – дугам.

Матрица инцидентности однозначно определяет структуру графа (рис. 1.1, а –в , д–ж ). В каждом столбце матрицы B ровно две единицы. Равных столбцов нет.

Недостаток данного представления состоит в том, что требуется n  m единиц памяти, большинство из которых будет занято нулями. Не всегда удобен доступ к информации. Например, для ответа на вопросы «есть ли в графе дуга (x , y ) ?» или «к каким вершинам ведут ребра из вершины x ?» может потребоваться перебор всех столбцов матрицы.

1.2.3. Матрица весов графа

Простой взвешенный граф может быть представлен своей матрицей весов W = [w ij ], где w ij – вес ребра, соединяющего вершины i , j = 1,2, ..., m . Веса несуществующих ребер полагаются равными? или 0 в зависимости от задачи. Матрица весов – простое обобщение матрицы смежности.

1.2.4. Список ребер графа

При описании графа списком его ребер (или для орграфов списком дуг) каждое ребро представляется парой инцидентных ему вершин. Это представление можно реализовать двумя массивами (или одним двумерным):

x = (x 0 , x 1 , ..., x m) и y = (y 0 , y 1 , ..., y m),

Где m –– количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i -е ребро графа выходит из вершины x i и входит в вершину y i . Объем занимаемой памяти составляет в этом случае 2m единиц памяти. Неудобством является большое число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

1.2.5. Списки смежных вершин графа

Граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков Adj [x ] вершин графа, смежных с вершиной x . Списки Adj [x ] составляются для каждой вершины графа. Структура смежности удобно реализуется массивом из n (число вершин в графе)
линейно связанных списков (1.1, а–г ). Каждый список содержит

а д

	1	2	3	4	5			1	2	3	4	5
1	0	1	1	0	1		1	0	1	1	0	0
2	1	0	1	0	0		2	0	0	0	0	0
3	1	1	0	1	1		3	0	0	0	0	0
4	0	0	1	0	1		4	1	1	0	0	0
5	1	0	1	1	0		5	0	0	0	1	0

б е

	Ѕ	1/3	1/5	2/3	3/4	3/5	4/5			Ѕ	1/3	4/1	4/2	5/4
1	1	1	1	0	0	0	0		1	1	1	-1	0	0
2	1	0	0	1	0	0	0		2	-1	0	0	-1	0
3	0	1	0	1	1	1	0		3	0	-1	0	0	0
4	0	0	0	0	1	0	1		4	0	0	1	1	-1
5	0	0	1	0	0	1	1		5	0	0	0	0	1

в ж

г з

Рис. 1.1

Вершины, смежные с вершиной, для которой составляется список. Список смежных вершин графа дает компактное представление для разреженных графов – тех, у которых множество ребер много меньше множества вершин. Недостаток этого представления таков: если мы хотим узнать, есть ли в графе ребро (x , y ), приходится просматривать весь список Adj [x ] в поисках y . Объем требуемой памяти составляет для ориентированных n + m и n +2 m для неориентированных графов единиц памяти, где n – число вершин графа, а m – число ребер (дуг) графа. Если в основе алгоритма решения задачи лежат операции добавления и удаления вершин из списков, то хранение списков смежности удобно реализовать, используя связанное представление списков (1.1, д–з ).

1.3. Обход графа

Обход графа – это некоторое систематическое прохождение его вершин (и/или ребер). Обходя граф, мы двигаемся по ребрам (дугам) и проходим все вершины. При этом можно получить много информации, которая необходима для дальнейшей обработки графа, поэтому обход графа – основа многих алгоритмов исследования структуры графа. Если при посещении вершины структура графа не меняется, то наиболее полезны два основные способа обхода: обход в глубину и обход в ширину.

1.3.1. Обход (или поиск) в глубину

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

Когда при поиске мы впервые обнаружим вершину v , смежную с вершиной u , необходимо отметить это событие. Алгоритм поиска в глубину использует для этого цвета (метки) вершин. Каждая из вершин вначале белая (не пройденная). Будучи обнаруженной, она становится серой. Когда вершина будет полностью обработана (т.е. когда список смежных с ней вершин будет просмотрен), она станет черной. Таким образом, в процессе поиска из графа выделяется часть – «дерево поиска в глубину» или несколько деревьев (лес поиска в глубину), если поиск повторяется из нескольких вершин. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Кроме этого можно ставить дополнительные метки на вершинах дерева: метку, когда вершина была обнаружена (сделалась серой), и метку, когда была закончена обработка списка смежных с u вершин (и u стала черной).

Приведенный ниже алгоритм использует представление графа списками смежных вершин Adj [u ]. Для каждой вершины u графа дополнительно хранятся ее цвет Mark[u ] и ее предшественник Pr[u ]. Если предшественника нет (например, если u = s или u еще не обнаружена), то Pr[u ] = nil . Кроме того, в d [u ] и
f [u ] записываются дополнительные для u метки: метки времени. В d [u ] записывается время, когда вершина u была обнаружена (и стала серой), а в f [u ] записывается время, когда была закончена обработка списка смежных с u вершин (и u стала черной). В приводимом ниже алгоритме метки времени d [u ] и
f [u ] это целые числа от 1 до 2| V |; для любой вершины u выполнено неравенство: d [u ] u]. Вершина u будет белой до момента d [u ], серой между d [u ] и f [u ] и черной после f [u ]. Алгоритм использует рекурсию для просмотра всех смежных с
u вершин.
Поиск_в_глубину (G )

2 for (каждая вершина u  V [G ])

4 Pr [u ] ?nil ;

7 for (каждая вершина s  V [G ])

Search (u )

3 d [u ] ?time?time+1;

4 for (каждая v  Adj [u ])

5 { if (Mark [v ] = БЕЛЫЙ)

6 { Pr [v ] ?u ; Search (v ); }

9 f [u ] ? time?time+1;

10 }
Алгоритм начинается с того, что сначала (строки 2–5) все вершины красятся в белый цвет (помечаются как не пройденные); в поле Pr помещается nil (пока у вершин нет предшественника). Затем (строка 6) устанавливается начальное (нулевое) время (переменная time – глобальная переменная). Для всех вершин (строки 7–8), которые все еще остались не пройденными (белыми), вызывается процедура Search. Эти вершины становятся корнями деревьев поиска в глубину.

В момент вызова Search (u ) вершина u – белая. В процедуре Search она сразу же становится серой (строка 2). Время ее обнаружения (строка 3) заносится в d[u ] (счетчик времени перед этим увеличился на единицу). Затем просматриваются (строки 4–7) смежные с u вершины; процедура Search вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с u вершин саму вершину u делаем черной и записываем в f [u ] время этого события.