Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная

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

Рабочая программа

Содержание Теория АЛГОРИТМОВ и СЛОЖНОСТИ Принципы построения Цели курса Учебно-тематический план Количество часов Содержание лекционных занятий Лекция 2. Виды алгоритмов Лекция 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины Лекция 4. Равнодоступные адресные машины (РАМ) Write * 2 5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции Лекция 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и н Лекция 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Лекция 10. Элементарные по Кальмару функции Лекция 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности Лекция 12. Методы оценки сложности вычислений и алгоритмов. Лекция 13. On-line - вычисления, вычисления в реальное время Лекция 14. Автоматные вычисления. Регулярные множества Лекция 15. Регулярность автоматных и автоматность регулярных множеств Лекция 16. Связь логики и вычислимости ... Полное содержание

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

• Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика, 292.77kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
• Паспорт (государственный стандарт) Специальности «прикладная информатика (по областям)», 504.1kb.
• Рабочая программа дисциплины: интеллектуальные информационные системы для специальностей:, 369.71kb.
• Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
• Рабочая программа по курсу Проектирование информационных систем для специальностей, 202.08kb.
• Рабочая программа дисциплины для магистрантов направления «Прикладная математика, 128.62kb.
• Рабочая программа учебной дисциплины «теория систем и системный анализ» Направление, 223.11kb.
• Рабочая программа по курсу «Мировые информационные ресурсы» 351400 «Прикладная информатика, 315.91kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.

Федеральное агентство по образованию


ГОУ ВПО «Удмуртский государственный университет»


факультет Информационных технологий и

вычислительной техники


кафедра Теоретических основ информатики


РАБОЧАЯ ПРОГРАММА


по дисциплине


«ТЕОРИЯ АЛГОРИТМОВ И СЛОЖНОСТИ»


для специальности


351400 Прикладная информатика (по областям)


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

Курс	2
Семестр	4
Всего часов	100
Всего аудиторных часов	51
Лекции, час.	34
Лабораторные занятия, час.	17
Самостоятельная работа, час.	49
Экзамен, номера семестров	4
Зачет, номера семестров	-
Другие виды контроля: дом. задание, семестр	4

Ижевск

2007

Рабочая программа составлена на основании ГОС ВПО специальности 351400 «Прикладная информатика (по областям)» (квалификация – информатик (квалификация в области ), утвержденного 14 марта 2000 г.


Составитель рабочей программы

д.ф-м.н., профессор ________________ А.П.Бельтюков


Рабочая программа утверждена на заседании кафедры

«___» _____________ 2009 г.


Заведующий кафедрой ___________________ А.П.Бельтюков

д.ф-м.н., профессор


Одобрено методической комиссией

«___» _______________ 2009 г.


Председатель методической комиссии ______________________В.И.Родионов


Декан факультета _____________________В.И.Родионов


Рекомендации Computing Curricula 2001: Computer Science


Темы


Основы анализа алгоритмов

Распределенные алгоритмы

Основы теории вычислимости

Классы сложности P и NP

Теория автоматов

Углубленный анализ алгоритмов

Параллельные алгоритмы


Введение


Теория алгоритмов и сложности является основой информатики и

программной инженерии. Фактическая производительность

программной системы зависит от двух факторов: (1) применяемых в

ней алгоритмов и (2) эффективности реализации на различных

уровнях. Поэтому разработка хорошего алгоритма имеет решающее

значение для любой программной системы. Кроме того, изучение

алгоритмов позволяет более глубоко вникнуть в задачу и может

подсказать методы решения, не зависящие от языка

программирования, парадигмы программирования, аппаратного

обеспечения и других аспектов реализации.


Важной основной частью знаний в области информатики является

способность выбрать алгоритм, подходящий для решения данной

задачи, или доказать, что такого алгоритма не существует. Эта

способность основывается на знании класса алгоритмов, которые

предназначены для решения определенного набора известных задач,

понимании их сильных и слабых сторон, применимости различных

алгоритмов в данном контексте. Эффективность является важнейшим

вопросом в данной области

1. 
   Требования
   

государственного образовательного стандарта (ГОС)

по специальности 351400 – Прикладная информатика (по областям)

Индекс	Наименование дисциплины	Всего часов
ОПД.Р.01	Теория АЛГОРИТМОВ и СЛОЖНОСТИ Требования федерального компонента отсутствуют. Требования вузовского компонента: классическая теория (идеальной) вычислимости, теория сложности вычислений, теория сложности алгоритмов (дескриптивной сложности), структурная теория сложности (одновременный учет ограничений, рассматриваемых в разделах теория сложности вычислений и теория сложности алгоритмов).	100 час.