ISBN 978-5-7883-0633-9
Пособие представляет собой указания к курсовому проекту по дисциплине
"Компьютерная алгебра", выполняемому в 9-м семестре студентами
специальности "Прикладная математика и информатика" специализации
"Математическое обеспечение систем обработки изображений". <...> Пособие
содержит весь необходимый теоретический и практический материал, включая
сведения из теории алгебраических структур, быстрые алгоритмы двумерного
дискретного преобразования Фурье, а также требования к программному
обеспечению, созда-ваемому в ходе выполнения проекта, рекомендации по его
тести-рованию и экспериментальному исследованию реализованного алгоритма. <...> Целью курсового проекта является программная реализация и исследование
одного из алгоритмов двумерного дискретного преобразования Фурье (ДПФ) с
представлением данных в одной из заданных алгебраических структур. <...> Первая глава содержит сведения из теории алгебраических структур. <...> Вторая глава посвящена схемам декомпозиции двумерного ДПФ, методике
реализации соответствующих алгоритмов, способам учета вещественности входного
сигнала. <...> Приводится методика расчета вычислительной сложности быстрых
алгоритмов. <...> Там
же приведен образец оформления пояснительной записки и вспомогательные
алгоритмы перестановок. <...> 5
1 НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ АЛГЕБРАИЧЕСКИХ
СТРУКТУР
Эта глава содержит необходимые для выполнения курсового проекта сведения об
используемых
алгебраических
структурах:
алгебре
кватернионов
и
гиперкомплексной алгебре. <...> Кроме того, в главу входит материал о представлении
кватернионов в форме кодов Гамильтона-Эйзенштейна, необходимый при
реализации преобразований по основаниям 3 и 6 (см. главу 2), а также о
представлении гиперкомплексных чисел в прямой сумме комплексных алгебр,
которое позволяет строить параллельные алгоритмы двумерного ДПФ (см. главу 3). <...> 1.1 Алгебра кватернионов
Под телом Η гамильтоновых
ассоциативная алгебра над Ρ
кватернионов <...>
Компьютерная_алгебра._Методические_указания_к_курсовому_проектированию.pdf
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»
М.А. ЧИЧЕВА
КОМПЬЮТЕРНАЯ АЛГЕБРА.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К КУРСОВОМУ ПРОЕКТИРОВАНИЮ
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
С А М А Р А
Издательство СГАУ
2007
Стр.1
УДК 681.3
ББК 22.343
Ч-722
Инновационная образовательная программа
"Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических
и геоинформационных технологий"
Рецензенты: д-р техн. наук А. Г. Х р а м о в,
д-р техн. наук В. Г. К а р т а ш е в с к и й
Чичева М.А.
Ч-722 Компьютерная алгебра. Методические указания к курсовому
проектированию: учеб. пособие / М.А. Чичева. – Самара: Изд-во
Самар. гос. аэрокосм. ун-та, 2007. – 64 с. : ил. 11.
ISBN 978-5-7883-0633-9
Пособие представляет собой указания к курсовому проекту по дисциплине
"Компьютерная алгебра", выполняемому в 9-м семестре студентами
специальности "Прикладная математика и информатика" специализации
"Математическое обеспечение систем обработки изображений". Пособие
содержит весь необходимый теоретический и практический материал, включая
сведения из теории алгебраических структур, быстрые алгоритмы двумерного
дискретного преобразования Фурье, а также требования к программному
обеспечению, созда-ваемому в ходе выполнения проекта, рекомендации по его
тести-рованию и экспериментальному исследованию реализованного алгоритма.
В приложения вынесены необходимые технические материалы.
Учебное пособие предназначено для студентов факультета инфор-матики,
обучающихся по специальности "Прикладная математика и информатика".
УДК 681.3
ББК 22.343
ISBN 978-5-7883-0633-9
© Чичева М.А., 2007
© Самарский государственный
аэрокосмический университет, 2007
П
Р
И
О
Р
И
Т
Т
К
Е
Т
О
Н
Ы
Е
Н
А
Ц
И
О
А
Н
Л
Ь
Н
Ы
Е
П
Р
Е
Ы
Стр.2
ОГЛАВЛЕНИЕ
Введение..................................................................................................................5
1 Необходимые сведения из теории алгебраических структур..........................6
1.1 Алгебра кватернионов..............................................................................6
1.2 Представление данных в кодах Гамильтона-Эйзенштейна ..................8
1.3 Алгебра гиперкомплексных чисел........................................................11
1.4 Прямая сумма комплексных алгебр......................................................13
2 Двумерное ДПФ и его быстрые алгоритмы в специальных
алгебраических структурах............................................................................14
2.1 Определение двумерного ДПФ в алгебре комплексных чисел и
в четырехмерных алгебрах ....................................................................14
2.2 Алгоритм двумерного ДПФ по основанию 2.......................................15
2.3 Алгоритм двумерного ДПФ по основанию 4.......................................16
2.4 Алгоритм с расщеплением основания ..................................................17
2.5. Двумерное ДПФ по основанию 3..........................................................18
2.6 Двумерное ДПФ по основанию 6..........................................................19
2.7 Реализация: от коротких длин к большим............................................20
2.8 Учет вещественности входного сигнала...............................................21
2.8.1 Алгоритм двумерного ДПФ с совмещением.................................. 24
2.8.2 Учет симметрий спектра вещественного сигнала.......................... 26
2.9 Оценка сложности алгоритмов..............................................................26
2.9.1 Методика оценки вычислительной сложности быстрых алгоритмов
двумерного ДПФ.......................................................................................... 26
2.9.2 Сложности алгоритмов по основанию 2 и 4 в алгебре
кватернионов..................................................................................... 29
2.9.3 Сложности алгоритмов в гиперкомплексной алгебре ................... 30
2.9.4 Сложности алгоритмов с представлением данных в кодах
Гамильтона-Эйзенштейна ................................................................ 31
2.9.5 Сложности алгоритмов в прямой сумме комплексных алгебр..... 31
2.9.6 Сравнительный анализ сложности алгоритмов.............................. 32
3 Параллельные алгоритмы двумерного ДПФ...................................................33
3.1 Распараллеливание по структуре декомпозиции.................................33
3.2 Распараллеливание за счет структуры алгебры...................................35
3
Стр.3