Программа промежуточной аттестации студентов по дисциплине Элементы абстрактной и компьютерной алгебры Специальность: 030100 Информатика

Вид материала

Программа

Содержание Пояснительная записка Содержание дисциплины РАЗДЕЛ 2. Кольцо целых чисел. Теория делимости в кольце целых чисел РАЗДЕЛ 3. Кольцо многочленов от одной переменной. Теория делимости РАЗДЕЛ 4. Первоначальные представления о теории кодирования РАЗДЕЛ 5. Поля. Расширения полей. Алгебраические и конечные расширения Примерный перечень вопросов к экзамену Рекомендуемая основная литература Рекомендуемая дополнительная литература Рефераты и курсовые работы не предусмотрены Оценка «хорошо» Оценка «удовлетворительно» Оценка «неудовлетворительно»

Подобный материал:

• Программа дисциплины " Элементы абстрактной и компьютерной алгебры " для подготовки, 75.59kb.
• Программа промежуточной аттестации студентов по дисциплине Численные методы Специальность:, 110.86kb.
• Практический курс иностранного языка (158, 22.94kb.
• Методические указания по текущему контролю знаний, проведению промежуточной аттестации, 150.11kb.
• Программа промежуточной аттестации студентов по дисциплине Методы и модели системного, 80.54kb.
• Учебно-методический комплекс учебной дисциплины Геометрия Специальность 030100., 92.15kb.
• М. К. Аммосова рабочая программа дисциплины «Уравнения математической физики» (специальность, 50.63kb.
• Учебная программа по дисциплине «физическая культура» для всех направлений и специальностей, 257.46kb.
• Положение об оценке знаний, умений и навыков, промежуточной аттестации студентов гбоу, 108.09kb.
• Учебно-методический комплекс по дисциплине ен. Ф. 03 Физика специальность/направление, 1647.21kb.

Федеральное агентство по образованию
СТАРООСКОЛЬСКИЙ ФИЛИАЛ
государственного образовательного учреждения высшего профессионального образования
«БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»


Кафедра естественнонаучных и математических дисциплин


ПРОГРАММА ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ СТУДЕНТОВ
по дисциплине Элементы абстрактной и компьютерной алгебры


Специальность: 030100 Информатика


Старый Оскол 2004

ББК П

Печатается по решению Редакционно-издательского Совета Старооскольского филиала Белгородского государственного университета

Составитель: доцент кафедры
естественнонаучных и
математических дисциплин
к. ф.-м. н. Кознов В. В.


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


Программа промежуточной аттестации студентов по дисциплине Элементы абстрактной и компьютерной алгебры / Составитель: В. В. Кознов — Старый Оскол: Изд-во СОФ БелГУ, 2004. — с. 11.

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
   

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

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

• овладение основными понятиями и фактами, характеризующими свойства абстрактных алгебраических объектов: группа, кольцо, поле;
  
• формирование знаний, умений и навыков в области алгоритмически разрешимых алгебраических задач и проблем;
  
• овладение навыками анализа, оценки эффективности и сложности алгоритмов символьных преобразований.
  

Компьютерная алгебра является одной из областей математики и информатики, особенно активно развивающейся в последние годы. Усилия специалистов в этой области направлены как на разработку новых алгоритмов, так и на создание систем компьютерной алгебры, которые всё шире используются в научных исследованиях, и в практических приложениях. Термин компьютерная алгебра объясняется способностью компьютера манипулировать математическими выражениями, заданными символьно. Исследования в области символьных преобразований включают в себя развитие и анализ эффективных алгоритмов для разложения на множители, вычисления наибольших общих делителей и отделения вещественных корней полиномов.

Студенты должны знать:

• определения и свойства теоретико-множественных операций и отношений, определение разбиения множества на классы;
  
• определение соответствия между множествами, бинарного отношения на множестве, их свойства и способы задания;
  
• определения отношения эквивалентности и порядка;
  
• характеристику числовых множеств;
  
• определение основных понятий абстрактной и компьютерной алгебры;
  
• алгоритмы действия модульной арифметики, принципы работы ЭВМ;
  
• определение и свойства отношения делимости;
  
• алгоритм Евклида;
  
• схему Горнера;
  
• сущность теории и способов кодирования;
  

должны уметь:

• устанавливать способ задания конкретного отношения и формулировать его свойства;
  
• определять по определению и по критерию различные алгебраические структуры;
  
• доказывать изоморфизм алгебраических структур;
  
• выполнять операции на множестве целых и комплексных чисел;
  
• производить вычисления, используя модульную арифметику;
  
• находить наибольший общий делитель и наименьшее общее кратное целых чисел и многочленов;
  
• проверять кратность корня многочлена;
  
• находить значения производных многочлена с помощью схемы Горнера;
  
• строить алгоритмы символьных преобразований;
  
• для списка сообщений с заданным распределением частот построить код Фано, определить стоимость кода;
  
• для заданного сообщения X построить код Хэмминга, внести одиночную ошибку замещения и произвести декодирование искажённого сообщения по методу Хэмминга;
  
• характеризовать числовые поля.
  

2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
   

РАЗДЕЛ 1. Группы, кольца, идеалы, факторкольца

Определение бинарной алгебраической операции. Алгебраические структуры с одной бинарной операцией. Понятие группы. Примеры и свойства групп. Подгруппы. Нормальные подгруппы и факторгруппы. Гомоморфизмы групп. Изоморфизмы. Алгебраические структуры с двумя бинарными алгебраическими операциями. Понятие кольца. Примеры и свойства колец. Подкольца. Идеалы кольца. Факторкольца.

РАЗДЕЛ 2. Кольцо целых чисел. Теория делимости в кольце целых чисел

Кольцо целых чисел. Отношение делимости, его простейшие свойства. Теорема о делении с остатком. Кольцо классов вычетов. НОД, НОК: алгоритм Евклида; расширенный алгоритм Евклида. Простые числа. Разложение целых чисел на множители. Точные вычисления, использующие модулярную арифметику. Представление больших чисел в памяти компьютера.

РАЗДЕЛ 3. Кольцо многочленов от одной переменной. Теория делимости

Построение кольца многочленов над полем. Отношение делимости многочленов. Теорема о делении с остатком. Деление на двучлен, схема Горнера. Корни многочлена, теорема Безу. НОД и НОК многочленов. Алгоритм Евклида. Взаимно простые многочлены. Приводимые и неприводимые многочлены. Разложение на неприводимые множители, единственность разложения.

РАЗДЕЛ 4. Первоначальные представления о теории кодирования

Алфавитное кодирование. Неравенство Макмиллана. Кодирование с минимальной избыточностью, алгоритм Фано. Оптимальное кодирование, кодовое расстояние. Кодирование с исправлением ошибок, код Хэмминга.

РАЗДЕЛ 5. Поля. Расширения полей. Алгебраические и конечные расширения

Понятие поля. Примеры и свойства полей. Поле комплексных чисел. Поле Галуа. Расширения полей. Конечные расширения поля. Строение простого алгебраического расширения. Конечные поля.

3. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ
   

1. Алгебраические операции, их свойства.
   
2. Нейтральный элемент. Теорема о единственности нейтрального элемента.
   
3. Симметричный элемент. Теорема о единственности симметричного элемента.
   
4. Бинарные отношения. Виды бинарных отношений. Отношение эквивалентности.
   
5. Алгебра. Гомоморфизм. Теорема о гомоморфизме.
   
6. Алгебра. Изоморфизм. Теоремы об изоморфизме.
   
7. Подалгебра. Замыкание, его свойства. Система образующих.
   
8. Полугруппа. Определяющие соотношения. Теорема Маркова — Поста. Моноид.
   
9. Группа. Свойства группы. Доказательство одного из свойств (по указанию преподавателя).
   
10. Подгруппа. Критерий подгруппы. Смежные классы.
    
11. Группа классов вычетов. Теорема Лагранжа.
    
12. Гомоморфизм групп. Свойства гомоморфизма.
    
13. Ядро гомоморфизма. Нормальная подгруппа. Критерий нормальности подгруппы.
    
14. Факторгруппа. Теорема о гомоморфизме.
    
15. Кольцо. Свойства кольца. Доказательство одного из свойств (по указанию преподавателя).
    
16. Области целостности. Подкольцо. Критерий подкольца.
    
17. Идеал. Критерий идеала. Факторкольцо.
    
18. Кольцо целых чисел. Отношение делимости, его простейшие свойства. Теорема о делении с остатком.
    
19. НОД и НОК. Линейное представление НОД. Связь НОК и НОД.
    
20. Линейные диофантовы уравнения.
    
21. Алгоритм Евклида.
    
22. Расширенный алгоритм Евклида.
    
23. Простые числа. Основная теорема арифметики.
    
24. Целые числа по модулю m. Кольцо целых чисел по модулю m. Полная система остатков, её виды.
    
25. Линейные уравнения по модулю m. Китайская теорема об остатках.
    
26. Списочное представление чисел. Короткие и длинные числа. Классические алгоритмы целочисленной арифметики.
    
27. Точные вычисления, использующие модулярную арифметику: случай одного модуля.
    
28. Точные вычисления, использующие модулярную арифметику: случай нескольких модулей.
    
29. Кольцо многочленов от одной переменной.
    
30. Теорема о делении многочленов с остатком. Теорема о кольце главных идеалов.
    
31. НОД и НОК многочленов. Теоремы существования и единственности НОД и НОК.
    
32. Алгоритм Евклида для многочленов.
    
33. Приводимые и неприводимые многочлены. Теорема об однозначном разложении на множители.
    
34. Корни многочленов. Теорема Безу и её следствие.
    
35. Схема Горнера.
    
36. Производная многочлена. Вычисление значения многочлена и его производных.
    
37. Алфавитное кодирование. Разделимые и префиксные схемы. Кодовое дерево. Неравенство Макмиллана.
    
38. Кодирование с минимальной избыточностью. Алгоритм Фано.
    
39. Коды с обнаружением и исправлением ошибок. Кодовое расстояние. Расстояние Хэмминга.
    
40. Код Хэмминга для исправления одного замещения.
    
41. Поле. Свойства поля. Доказательство одного из свойств (по указанию преподавателя).
    
42. Поле комплексных чисел. Изоморфизм полей комплексных и действительных чисел.
    
43. Подполе. Критерий подполя. Алгебраическое расширение поля.
    
44. Конечные расширения полей.
    

4. РЕКОМЕНДУЕМАЯ ОСНОВНАЯ ЛИТЕРАТУРА
   

1. Кнут Д. Э. Искусство программирования для ЭВМ. Т. 2. — М.: Издательский дом «Вильямс», 2001.
   
2. Куликов Л. Я., Москаленко А. И., Фомин А. А. Сборник задач по алгебре и теории чисел. — М.: Просвещение, 1993.
   
3. Нечаев В. И. Элементы криптографии (Основы теории защиты информации). — М.: Высш. шк., 1999.
   
4. Яблонский С. В. Введение в дискретную математику. — М.: Высш. шк., 2001.
   

5. РЕКОМЕНДУЕМАЯ ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
   

1. Акимов О. Е. Дискретная математика: логика, группы, графы. — М.: Лаборатория базовых знаний, 2001.
   
2. Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений. — М.: Высш. шк., 2002.
   
3. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия, алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. — М.: Мир, 2000.
   
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
   
5. Ларин С. В. Числовые системы. — М.: Издательский центр «Академия», 2001.
   
6. Новиков Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2001.
   
7. Норден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). — М.: Мир, 1999.
   
8. Самсонов Б. Б., Плохов Е. М., Филоненков А. И. Компьютерная математика (основание информатики). — Ростов-на-Дону: «Феникс», 2002.
   
9. Сборник задач по алгебре / Под ред. А. И. Кострикина. — М.: Факториал, 1995.
   
10. Теория информации и кодирование / Самсонов Б. Б., Плохов Е. М., Филоненков А. И., Кречет Т. В. — Ростов-на-Дону: «Феникс», 2002.
    

6. РЕФЕРАТЫ И КУРСОВЫЕ РАБОТЫ НЕ ПРЕДУСМОТРЕНЫ
   
7. КРИТЕРИИ ОЦЕНКИ КАЧЕСТВА ЗНАНИЙ СТУДЕНТОВ
   

Оценка «отлично» выставляется студенту, глубоко и прочно усвоившему программный материал, исчерпывающе, последовательно, грамотно и логически стройно его излагающему, в ответе которого увязывается теория с практикой, он показывает знакомство с монографической литературой, правильно обосновывает и использует рациональные способы решения задачи.

Оценка «хорошо» выставляется студенту, твёрдо знающему программный материал, грамотно и по существу излагающему его, который не допускает существенных неточностей в ответе на вопрос, правильно применяет теоретические положения при решении практических вопросов и задач.

Оценка «удовлетворительно» выставляется студенту, который знает только основной программный материал, но не усвоил его деталей, допускает в ответе неточности, недостаточно правильно формулирует основные законы и правила, затрудняется в выполнении практических задач.

Оценка «неудовлетворительно» выставляется студенту, который не знает значительной части программного материала, допускает в ответе существенные ошибки, с затруднениями выполняет практические работы.

СОДЕРЖАНИЕ

№ п/п	Название разделов	Страницы
1	Пояснительная записка	3
2	Содержание дисциплины	5
3	Примерный перечень вопросов к экзамену	6
4	Рекомендуемая основная литература	8
5	Рекомендуемая дополнительная литература	9
6	Примерный перечень тем рефератов и курсовых работ	9
7	Критерии оценки качества знаний студентов	9