«Математическая логика и теория алгоритмов»




Название«Математическая логика и теория алгоритмов»
Дата26.01.2013
Размер69.2 Kb.
ТипКурсовая


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ


ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ


«МАТИ» - РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

имени К.Э. ЦИОЛКОВСКОГО




Кафедра «Проектирование вычислительных комплексов»





























РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА


по дисциплине «Математическая логика и теория алгоритмов»


Направление № 230100 «Информатика и вычислительная техника»

Шифр учебного плана: 230100.05пвк

Факультет № 6

Выпускающая кафедра: Проектирование вычислительных комплексов

Форма обучения: очная

Количество часов по дисциплине: 102

Цикл дисциплин: Е


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

(часы аудиторных занятий/самостоятельная работа)



Семестр

4




По учебному плану (АР/СР)

48/54




Лекции (АР/СР)

32/30




Лабораторные работы (АР/СР)

16/24




Практические занятия (АР/СР)

-




Курсовая работа (0/СР)

-




Форма контроля

экзамен






Москва 2006 г.


  1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ



Цель преподавания дисциплины

Основной целью преподавания курса "Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных программ, направленное на обеспечение плодотворной профессиональной деятельности специалистов по направлению 230100 "Информатика и вычислительная техника".

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


    1. Задачи изучения дисциплины


Задачи изучения курса " Математическая логика и теория алгоритмов " определяются результатами анализа потребностей дальнейшего образования по специальностям направления. Должно быть обеспечено усвоение студентами основных методов и приемов построения и анализа алгоритмов различных классов, выработано умение в применении разных типов данных при написании программ. Должна быть обеспечена стройная логическая взаимопреемственность изложения основных разделов курса " Математическая логика и теория алгоритмов " с другими дисциплинами. Важной задачей является выработка навыков и умения в экспериментальной подготовке на базе лабораторного практикума и в процессе самостоятельной работы над индивидуальными заданиями по курсу.



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


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



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




    1. Наименования разделов и тем, объем в часах лекционных занятий.


4 семестр (32 часа)




Тема и содержание

Кол-во

часов



Основные типы и структуры данных.

Простые типы данных. Определения основных структур данных (массивы, записи, объединения, множества, таблицы, последовательности - файлы, буферы, стеки, очереди). Ссылочный тип данных. Списки, деревья, графы. Операции над структурами данных. Их использование в программировании.


4



Абстрактные типы данных.

Понятие АТД и их применение в языках высокого уровня.


4



Итерационные и рекурсивные алгоритмы.

2



Анализ сложности алгоритмов.

Классы сложности: P-сложность, NP-сложность

4



Сортировка и поиск.

Основные алгоритмы сортировки (с помощью прямого включения,

с помощью прямого выбора, с помощью прямого обмена). Улучшенные методы сортировки (сортировка Шелла, сортировка с помощью дерева). Сравнение методов сортировки.

Некоторые алгоритмы поиска (линейный поиск, двоичный поиск, прямой поиск в строке, алгоритм Кнута, Мориса и Пратта, алгоритм Боуера и Мура).

6



Разрешимость и неразрешимость.

Машина Поста. Универсальная машина Тьюринга.RAM-машина. Алгоритмически неразрешимые проблемы

4



Стратегии конструирования алгоритмов.

Метод "разделяй и властвуй". Метод последовательных приближений.

Метод наискорейшего спуска. Метод обратного прохода.

Метод динамического программирования. Алгоритмы поиска с возвратом.

Метод выделения подцелей. Метод моделирования.

4



Параллельные и распределенные алгоритмы.

Модели параллельных архитектур. Примеры параллельных алгоритмов.

4




    1. Лабораторные занятия, их содержание и объем в часах



4 семестр (16 часов)







Тема и содержание

Кол-во

часов



Основные типы и структуры данных.

-Применение данных разных типов при решении задач.


4



Итерационные и рекурсивные алгоритмы.

- Разработка итерационных алгоритмов решения задач.

- Разработка рекурсивных алгоритмов решения задач.

- Анализ процесса выполнения рекурсивных алгоритмов.

- Сравнение двух типов алгоритмов.


4



Анализ сложности алгоритмов.

- Практическая оценка сложности реализованных программно алгоритмов.


2



Программная реализация основных методов сортировки.

- Сравнительный анализ методов сортировки.

- Программная реализация основных методов поиска.

- Сравнительный анализ методов поиска.


2



Стратегии конструирования алгоритмов.

- Программная реализация некоторых методов конструирования алгоритмов

2



Параллельные и распределенные алгоритмы.

- Сравнение параллельной и последовательно реализации алгоритмов.



2



  1. САМОСТОЯТЕЛЬНАЯ РАБОТА



4 семестр


    1. Проработка конспекта лекций и изучение дополнительной литературы по основным темам лекций (30 часов).

    2. Подготовка к лабораторным занятиям (24 часа)



  1. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ





    1. Обязательная литература




  1. Н.Вирт "Алгоритмы и структуры данных" М., "Мир", 2001



4.2 Рекомендуемая литература


  1. Д.Кнут “Искусство программирования для ЭВМ”, т.1. Основные алгоритмы. М., Мир, 2000.

  2. Д.Кнут “Искусство программирования для ЭВМ”, т.2. Получисленные алгоритмы. М., Мир, 2000.

  3. Д.Баррон “Рекурсивные методы в программировании”. М., “Мир”, 1994.

  4. А.Костин, В.Шаньгин “Организация и обработка структур данных в вычислительных системах”. М., “Высшая школа”, 1997.


Похожие:

«Математическая логика и теория алгоритмов» iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
«Математическая логика и теория алгоритмов» iconРабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов
Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки...
«Математическая логика и теория алгоритмов» iconПрограмма дисциплины математическая логика и теория алгоритмов
Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса
«Математическая логика и теория алгоритмов» iconУльянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: Мгапи, 2003. – 80 с
«Математическая логика и теория алгоритмов» iconМатематическая логика и теория алгоритмов

«Математическая логика и теория алгоритмов» iconМатематическая логика и теория алгоритмов

«Математическая логика и теория алгоритмов» iconУчебно-методический комплекс по дисциплине математическая логика и теория алгоритмов
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»
«Математическая логика и теория алгоритмов» iconТемы курсовых работ по дисциплине «Математическая логика и теория алгоритмов»
В. А. Молчанов, В. Е. Новиков, Т. М. Отрыванкина, П. Н. Пронин, В. Е. Фирстов. – Оренбург: гоу огу, 2004. – 68 с
«Математическая логика и теория алгоритмов» iconМатематическая логика и теория алгоритмов
Автор: д-р физ мат наук, профессор, зав кафедрой компьютерной безопасности и математических методов обработки информации Дурнев В....
«Математическая логика и теория алгоритмов» iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования
Цель дисциплины «Математическая логика и теория алгоритмов» – формирование систематизированных знаний в области математической логики...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница