Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов» Направление №230100 «Информатика и вычислительная техника»
| Вид материала | Рабочая учебная программа |
- Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
- Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
- Рабочая учебная программа по дисциплине «Базы данных» Направление №230100 «Информатика, 115.03kb.
- Рабочая учебная программа по дисциплине вычислительная математика специальность: 230100, 133.73kb.
- Рабочая учебная программа по дисциплине «Информатика» Направление №230100 «Информатика, 91.73kb.
- Рабочая учебная программа по дисциплине «Программирование на языке высокого уровня», 119.59kb.
- Рабочая учебная программа по дисциплине «Теория принятия решений» Направление №230100, 82.23kb.
- Рабочая программа учебной дисциплины днн. 02 Современные научные проблемы автоматизированных, 221.23kb.
- Рабочая учебная программа дисциплины Моделирование рассуждений (наименование дисциплины), 166.66kb.
- Рабочая учебная программа по дисциплине «Современные интегрированные среды» Направление, 52.27kb.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МАТИ» - РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
имени К.Э. ЦИОЛКОВСКОГО
Кафедра «Проектирование вычислительных комплексов»
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине «Математическая логика и теория алгоритмов»
Направление № 230100 «Информатика и вычислительная техника»
Шифр учебного плана: 230100.05пвк
Факультет № 6
Выпускающая кафедра: Проектирование вычислительных комплексов
Форма обучения: очная
Количество часов по дисциплине: 102
Цикл дисциплин: Е
Распределение времени студента по видам учебных занятий
(часы аудиторных занятий/самостоятельная работа)
| Семестр | 4 | |
| По учебному плану (АР/СР) | 48/54 | |
| Лекции (АР/СР) | 32/30 | |
| Лабораторные работы (АР/СР) | 16/24 | |
| Практические занятия (АР/СР) | - | |
| Курсовая работа (0/СР) | - | |
| Форма контроля | экзамен | |
Москва 2006 г.
ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Цель преподавания дисциплины
Основной целью преподавания курса "Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных программ, направленное на обеспечение плодотворной профессиональной деятельности специалистов по направлению 230100 "Информатика и вычислительная техника".
Углубленно даются разделы теории и алгоритмов, являющиеся базовыми для ряда специальных курсов по технологии программирования, системному программированию, теории языков программирования. В программу курса входит знакомство с основными типами и структурами данных, средствами их формального представления в языках программирования, а также приемами их программирования; широко рассматриваются основные типы алгоритмов сортировки, поиска, рекурсивные алгоритмы, производится анализ методов построения алгоритмов и сравнение их свойств.
- Задачи изучения дисциплины
Задачи изучения курса " Математическая логика и теория алгоритмов " определяются результатами анализа потребностей дальнейшего образования по специальностям направления. Должно быть обеспечено усвоение студентами основных методов и приемов построения и анализа алгоритмов различных классов, выработано умение в применении разных типов данных при написании программ. Должна быть обеспечена стройная логическая взаимопреемственность изложения основных разделов курса " Математическая логика и теория алгоритмов " с другими дисциплинами. Важной задачей является выработка навыков и умения в экспериментальной подготовке на базе лабораторного практикума и в процессе самостоятельной работы над индивидуальными заданиями по курсу.
- Перечень тем и разделов предшествующих дисциплин, освоение которых необходимо для изучения данной дисциплины
Для изучения данной дисциплины необходимо знакомство с курсами дискретная математика, программирование на языке высокого уровня, информатики, математики.
- СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
- Наименования разделов и тем, объем в часах лекционных занятий.
4 семестр (32 часа)
| № | Тема и содержание | Кол-во часов |
| | Основные типы и структуры данных. Простые типы данных. Определения основных структур данных (массивы, записи, объединения, множества, таблицы, последовательности - файлы, буферы, стеки, очереди). Ссылочный тип данных. Списки, деревья, графы. Операции над структурами данных. Их использование в программировании. | 4 |
| | Абстрактные типы данных. Понятие АТД и их применение в языках высокого уровня. | 4 |
| | Итерационные и рекурсивные алгоритмы. | 2 |
| | Анализ сложности алгоритмов. Классы сложности: P-сложность, NP-сложность | 4 |
| | Сортировка и поиск. Основные алгоритмы сортировки (с помощью прямого включения, с помощью прямого выбора, с помощью прямого обмена). Улучшенные методы сортировки (сортировка Шелла, сортировка с помощью дерева). Сравнение методов сортировки. Некоторые алгоритмы поиска (линейный поиск, двоичный поиск, прямой поиск в строке, алгоритм Кнута, Мориса и Пратта, алгоритм Боуера и Мура). | 6 |
| | Разрешимость и неразрешимость. Машина Поста. Универсальная машина Тьюринга.RAM-машина. Алгоритмически неразрешимые проблемы | 4 |
| | Стратегии конструирования алгоритмов. Метод "разделяй и властвуй". Метод последовательных приближений. Метод наискорейшего спуска. Метод обратного прохода. Метод динамического программирования. Алгоритмы поиска с возвратом. Метод выделения подцелей. Метод моделирования. | 4 |
| | Параллельные и распределенные алгоритмы. Модели параллельных архитектур. Примеры параллельных алгоритмов. | 4 |
- Лабораторные занятия, их содержание и объем в часах
4 семестр (16 часов)
| № | Тема и содержание | Кол-во часов |
| | Основные типы и структуры данных. -Применение данных разных типов при решении задач. | 4 |
| | Итерационные и рекурсивные алгоритмы. - Разработка итерационных алгоритмов решения задач. - Разработка рекурсивных алгоритмов решения задач. - Анализ процесса выполнения рекурсивных алгоритмов. - Сравнение двух типов алгоритмов. | 4 |
| | Анализ сложности алгоритмов. - Практическая оценка сложности реализованных программно алгоритмов. | 2 |
| | Программная реализация основных методов сортировки. - Сравнительный анализ методов сортировки. - Программная реализация основных методов поиска. - Сравнительный анализ методов поиска. | 2 |
| | Стратегии конструирования алгоритмов. - Программная реализация некоторых методов конструирования алгоритмов | 2 |
| | Параллельные и распределенные алгоритмы. - Сравнение параллельной и последовательно реализации алгоритмов. | 2 |
-
САМОСТОЯТЕЛЬНАЯ РАБОТА
4 семестр
- Проработка конспекта лекций и изучение дополнительной литературы по основным темам лекций (30 часов).
- Подготовка к лабораторным занятиям (24 часа)
-
УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
- Обязательная литература
- Н.Вирт "Алгоритмы и структуры данных" М., "Мир", 2001
4.2 Рекомендуемая литература
- Д.Кнут “Искусство программирования для ЭВМ”, т.1. Основные алгоритмы. М., Мир, 2000.
- Д.Кнут “Искусство программирования для ЭВМ”, т.2. Получисленные алгоритмы. М., Мир, 2000.
- Д.Баррон “Рекурсивные методы в программировании”. М., “Мир”, 1994.
- А.Костин, В.Шаньгин “Организация и обработка структур данных в вычислительных системах”. М., “Высшая школа”, 1997.