Основы информатики и программирования

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

Пояснительная записка

Содержание 18.05.2006 Регистрационный № ТД-I.023/тип. Рекомендована к утверждению в качестве типовой Пояснительная записка Цели и задачи дисциплины, ее место среди других дисциплин в учебном процессе Содержание дисциплины Тема 2. БУЛЕВЫ ФУНКЦИИ Тема 4. ГРАФЫ И СЕТИ Тема 6. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ И АВТОМАТОВ примерный перечень ТЕМ Практических занятий

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

• В курсе информатики основной школы, 96.17kb.
• Учебно-методический комплекс по дисциплине высокоуровневые методы информатики и программирования, 435.89kb.
• Программа курса по выбору «Основы программирования» (6-8 классы,, 35.37kb.
• «Основы алгоритмизации и объектно-ориентированного программирования на языке Gambas», 318.06kb.
• Урок на тему «Решение логических задач с помощью электронных таблиц ms excel\ Раздел, 149.53kb.
• Поэтапном формировании у студентов следующих знаний, умений и владений: основы алгоритмизации,, 25.99kb.
• Программа курса " Азы программирования", 26.19kb.
• Курс: 2 Саранск 2007 а рассмотрено и одобрено на заседании предметной (цикловой) комиссии, 168.43kb.
• Курс Методы визуального программирования при разработке системного программного обеспечения., 30.14kb.
• Учебно-методический комплекс дисциплины высокоуровневые методы информатики и программирования, 533.39kb.

^

18.05.2006

Регистрационный № ТД-I.023/тип.

Основы дискретной математики и теории алгоритмов

Учебная программа для высших учебных заведений

по специальности I-40 01 02 Информационные системы и технологии

(по направлениям)

I-40 01 02-02 Информационные системы и технологии (в экономике)


СОСТАВИТЕЛЬ:

С. А. Поттосина, доцент кафедры экономической информатики Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники», кандидат физико-математических наук


РЕЦЕНЗЕНТЫ:

П.Н. Бибило, заведующий лабораторией логического проектирования Объединенного института проблем информатики НАН Беларуси, доктор технических наук;

Кафедра вычислительной техники Учреждения образования «Белорусский государственный аграрный технический университет» (протокол № 8 от 14.03.2006)


^ РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ В КАЧЕСТВЕ ТИПОВОЙ

Кафедрой экономической информатики Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» (протокол № 15 от 10.02.2003);

Научно-методическим советом Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» (протокол № 3 от 21.12.2005)


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


Программа «Основы дискретной математики и теории алгоритмов» разработана для специальности I-40 01 02 Информационные системы и технологии (по направлениям) по направлению специальности I-40 01 02-02 Информационные системы и технологии (в экономике). Она предусматривает лекционный материал и практические занятия. Задачи изучения дисциплины - освоение основных понятий и методов теории графов и комбинаторного анализа, теории множеств и отношений, теории булевых функций, теории алгоритмов и автоматов, исчисления высказываний и предикатов.


^ ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО СРЕДИ ДРУГИХ ДИСЦИПЛИН В УЧЕБНОМ ПРОЦЕССЕ

Цель преподавания дисциплины заключается:

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

Для усвоения дисциплины необходимо усвоение такой дисциплины как «Высшая математика».

Программа составлена в соответствии с требованиями общеобразовательного стандарта и рассчитана на объем 51 аудиторных часов. Примерное распределение учебных часов по видам занятий: лекции – 34 час, практические занятия – 17 часов.

^

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

ВВЕДЕНИЕ

ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ. СТРУКТУРА КУРСА


Тема 1. МНОЖЕСТВА, ОТНОШЕНИЯ, ФУНКЦИИ

1.1. Способы задания множеств. Операции над множествами.

1.2. Декартово произведение множеств. Бинарные и n–арные отношения.

1.3. Свойства бинарных отношений. Отношения эквивалентности и порядка.

1.4. Функции, соответствия, отображения.

1.5. Алгебраические структуры.

^

Тема 2. БУЛЕВЫ ФУНКЦИИ

2.1. Способы задания логических функций.

2.2. Булевы функции двух переменных.

2.3. Алгебра булевых функций.

2.4. Нормальные формы логических функций.

2.5. Полнота и замкнутость.

2.6. Минимизация логических функций. Метод Квайна-Мак-Класки. Визуально матричный метод.

2.7. Применение логических функций.


Тема 3. ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ

3.1. Основные понятия логики высказываний. Тождественно истинные формулы логики высказываний и их формальный вывод.

3.2. Основные понятия логики предикатов. Суждения и соллогизмы. Применение выражений логики предикатов для описания некоторых отношений.

^

Тема 4. ГРАФЫ И СЕТИ

4.1. Основные понятия и определения.

4.2. Маршруты, цепи, циклы.

4.3. Эйлеровы и гамильтоновы циклы. Задачи китайского почтальона и коммивояжера

4.4. Деревья. Построение остовных деревьев.

4.5. Независимые и доминирующие множества.

4.6. Раскраска и планарность графов.

4.7. Паросочетания в графе.

4.8. Кратчайшие пути и алгоритмы их поиска.

4.9. Задача о покрытии булевой матрицы и родственные с ней оптимизационные задачи на графах.

4.10. Достижимость. Исследование структур организаций.

4.11. Размещение центров и медиан в графе.

4.12. Транспортная сеть. Понятие о максимальном потоке и минимальном разрезе в транспортной сети.

4.13.Прикладные задачи теории графов в экономике.


Тема 5. КОМБИНАТОРНЫЕ ЗАДАЧИ И МЕТОДЫ КОМБИНАТОРНОГО ПОИСКА

5.1. Перечислительные и оптимизационные комбинаторные задачи.

5.2. Комбинаторные конфигурации: перестановки и размещения.

5.3.Методы комбинаторного поиска. Производящие функции Дерево поиска. Принцип включения и исключения.

5.4. Сложность комбинаторных задач.

^

Тема 6. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ И АВТОМАТОВ

6.1. Интуитивное понятие алгоритма и его уточнение в модели Маркова.

6.2. Алгоритмическая модель Тьюринга. Частично-рекурсивные функции.

6.3. Алгоритмически разрешимые и неразрешимые проблемы. Вычислительная сложность проблем.

6.4. Понятие о конечном автомате. Интерпретация автоматов. Распознавание множеств автоматов. Автоматы и теория алгоритмов

6.5. Сети из автоматов. Программная реализация логических функций и автоматов.

^

примерный перечень ТЕМ Практических занятий

1. Алгебра множеств. Основные соотношения и вывод формул.
   
2. Отношения и функции.
   
3. Функции алгебры логики. Карта Карно.
   
4. Нахождение ДНФ и КНФ.
   
5. Минимизация логических функций.
   
6. Решение логических уравнений.
   
7. Алгебра высказываний.
   
8. Предикаты и кванторы.
   
9. Графы и их матрицы. .
   
10. Деревья. Достижимость и связность. Раскраска графа.
    
11. Задача о покрытии и родственные с ней задачи.
    
12. Поиск кратчайших путей в графе.
    
13. Элементы комбинаторики.
    
14. Рекуррентные соотношения и производящие функции.
    
15. Машина Тьюринга.
    
16. Алгоритмическая разрешимость. Вычислительная сложность алгоритмов.
    

литература

Основная

1. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. – 384 с.

2. Глушков В.М. Синтез цифровых автоматов. - М.: ГИФМЛ, 1962. - 476 с.

3. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергия, 1988. - 480 с.

5. Лекции по теории графов/ В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич – М.: Наука, 1990. – 384 с.