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

ральский государственный технический университет

кафедра «Информационные системы и технологии»

Методические указания к лабораторной работе

Компрессия данных или измерение и избыточность информации Алгоритм Фаулкса

по курсу «ТЕОРИЯ информационныxсистем» для специальностей и направлений подготовки:

Специальности (направления)		Квалификация специалиста
Код	Наименование	Код	Наименование
230200	Информационные системы	62	Бакалавр информационных систем
230201	Информационные системы и технологии	65	Инженер

/ГоризПоз= по центру /ГоризПозОтносительно=текст

катеринбург2017

6. Дипломный проект, ДП

7. Курсовой проект, КП

8. Отчет по УИРС, ОУ

9. Отчет по практике, ОП

10. Отчет по лабораторной работе, ОЛ

4. 070500, Ядерные энергетические установки

5. 010800, Физика кинетических явлений

6. 071900, Информационные системы в технической физике

3. 000000, Не поддающаяся классификации работа

4. 443122, Оборудование для электрохимического травления поверхностей

4. Научно-исследовательская, Н

5. Технологическая, Т

6. Экономическая, Э

Министерство общего и профессионального образования Российской ФедерацииУральский государственный технический университет

кафедра молекулярной физики

Оценка проекта: ____ Члены комиссии: ____________________ ____________________ ____________________ ____________________

Екатеринбург

Селезнев В.Д.

д. ф.-м. н., профессор

Александров О.Е.

к. ф.-м. н., программист

Студент группа Фт-

__.__.11 . .17

20112017

Данные для титульного листа(это будет стерто в документе)

3.24

Версия 3.2. Диплом ПЗ (шаблон) .dot

©Шаблон, макрокоманды, стили: Александров О.Е. 1996, 97, 98.

©Template, macros, styles: Aleksandrov O.E. 1996, 97, 98.

Не стирайте эти данные — если это удалить, то будет хуже!

УДК 774:002:006.354

Составители: О. Е. Александров.

Научный редактор: доц., канд. физ.-мат. наук О. Е. Александров

Алгоритм Фаулкса: методические указания к лабораторной работеМетодические указания к лабораторной работе / О. Е. Александров Екатеринбург: УГТУ-УПИ, 2010. 3324с.

Изложен алгоритм отыскания допустимой последовательности операций при наличии ограничений. Приведены задания для самостоятельного выполнения.

Библиогр. 0 назв. Рис. 3. Табл. 4. Прил. 1.

Подготовлено кафедрой «Информационные системы и технологии».

Методические указания обсуждены на заседании кафедры, протокол №__

Заведующий кафедрой ____________.

© Содержание, оформление: Александров о.Е., 2010 © Уральский государственный технический университет, 2000Содержание

Перечень условных обозначений символов, единиц и терминов 8

Введение 8

111111100 010_h_1глава0101. 0Алгоритм Фаулкса и его приложения 8

1.1. Постановка проблемы 9

1.2. Идея алгоритма Фаулкса 9

1.3. Алгоритм Фаулкса 15

2. Задания для самостоятельного выполнения 20

2.1. Общие замечания 20

2.2. Варианты заданий 20

Вариант 0 (стандартный) 20

Вариант 0 21

100 01_h_1глава00010_h_1глава100_h_1пункт01.210 _h_1глава1001.2. 10 _h_1глава100Оформление результатов работы 21

200 01_h_1глава00010_h_1глава100_h_2пункт01.410 _h_1глава1001.4. 10 _h_1глава100Прием зачета по результатам работы 22

Заключение 23

Список использованных источникоВ 23

Перечень условных обозначений символов, единиц и терминов

0111b	суффикс «b» означает число, записанное по основанию 2 — двоичное число;
0ABCh	суффикс «h» означает число, записанное по основанию 16 — шестнадцатиричное число;
111.	суффикс «.» означает число, записанное по основанию 10 — десятичное число;
N1..N2	диапазон целых чисел от N1доN2;
[X1..X2)	интервал чисел от X1доX2,X1принадлежит интервалу,X2– не принадлежит;

Введение

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

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

Ниже изложена простейшая теория и алгоритм Фаулкса [¹].

111111100 010_H_1глава0101. 0Алгоритм Фаулкса и его приложения

1.1. Постановка проблемы

На днях мы посетили нашего друга Фреголи, хорошо известного в Мексике, и спросили у него, не мог бы он раскрыть нам секрет, который сделал его замечательным циркачом, неизменно любимым детьми и даже взрослыми. В самом деле, известно, что Фреголи может полностью сменить одежду в рекордное время. «Речь идет не о секрете, — сказал он нам, — а о логическом методе одевания и раздевания, переданном мне моими предками». И как хорошо воспитанный человек он счел возможным добавить: «Несомненно, математика, которая является вашей профессией, позволила бы вам представить себе усилия, которых потребовало от моего прадеда решение подобных задач».

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

Посмотрим, что он может сделать по крайней мере с восемью первыми предметами; при этом любой согласится с тем, что:

1. взять свою трость он сможет в последнюю очередь,

2. ему остается исследовать самое большее

8! = 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 40 320

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