Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
В конце своего жизненного пути Николай Семенович Лесков (1831— 1895) писал: «Я вижу яркий маяк и знаю, чего держаться». Это признание было поистине в...полностью>>
'Документ'
В настоящее время отечественная металлургия располагает большим опытом использования различных методов ввода ферросплавов-модификаторов в жидкий мета...полностью>>
'Документ'
Текст предоставлен порталом "Журнальный Зал" (архив журнала "Иностранная литература") и воспроизводится по изданию: "Иностра...полностью>>
'Конкурс'
Провести с 27 января 2012 года по 07 марта 2012 года региональный этап Всероссийского открытого конкурса юношеских исследовательских работ имени В.И....полностью>>

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

Главная > Рабочая программа
Сохрани ссылку в одной из сетей:

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

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

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

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

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

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

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

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

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

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 час.

Курс входит в раздел: национально-региональный (вузовский) компонент

  1. Принципы построения

Традиционно результаты данной науки относятся к следующим

разделам:

(1) классическая теория (идеальной) вычислимости,

(2) теория сложности вычислений,

(3) теория сложности алгоритмов (дескриптивной сложности),

(4) структурная теория сложности (одновременный учет

ограничений, рассматриваемых в разделах (2) и (3)).

Непосредственно наиболее близок к практике раздел (4).

Более того, все классические результаты предыдущих разделов

в настоящее время нетрудно трансформировать в результаты

раздела (4). Классические результаты необходимо, тем не менее,

изучать, во-первых, с целью получения общей культуры в знании

данного вопроса и его истории, во-вторых, - потому что

результаты первых разделов проще для изложения и могут быть

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

вопросам. Однако, стоит подчеркнуть, что некоторые факты,

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

зрения практического применения. Наиболее яркие примеры этого:

- идеальная вычислимость ничего не говорит о практической

вычислимости, например, разрешимость множества истинных формул

ограниченной арифметики на поверку означает, что в настоящее

время мы обладаем разрешающим алгоритмом, даже не являющимся

элементарным по Кальмару, а выполнение его для некоторых формул,

запись которых, например, в системе TeX, занимает всего 1000

байт, параллельно на всех компьютерах, имеющихся сейчас в мире,

займет время, гораздо большее, чем время, прошедшее с

гипотетического "Большого взрыва" при образовании наблюдаемой

Вселенной;

- идеальная невычислимость может также означать только

отсутствие алгоритма, охватывающего все математически идеальное

бесконечное множество возможных аргументов функции, тогда как на

практике нужно вычислять определенную функцию только для

относительно небольших значений аргумента (хотя практически

идеальная невычислимость может быть и полезна: она

предотвращает появление совсем уж некорректных постановок

задач);

- асимптотический характер большинства традиционных сложностных

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

n(log_2 n)^2 считается хуже, чем время работы 10000 n log_2 n,

но те длины входных данных (n), при которых первое время

действительно становится хуже, неосуществимы в наблюдаемой

нами части Вселенной с помощью известных нам физических

эффектов; и наоборот, время работы 1.0001^{n^0.0001} с точки

зрения асимптотики должно считаться очень плохим: почти

экспоненциальным, но реальный его рост начинается также с

совершенно неосуществимых n: больше 10000^{10000};

- традиционные модели вычислимости: машины Тьюринга, нормальные

алгоритмы и т.п., - очень далеки от практики, когда речь

заходит о конкретных (не асимптотических и даже иногда -

асимптотических) сложностных характеристиках вычислений;

относительно адекватной в этом отношении является модель РАМ.

Можно привести и массу других замечаний в этом же роде. Все это

говорит о том, что следует пересмотреть традиции преподавания

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

Предлагается сделать следующее.

Во-первых, надо взять три вида базовых моделей вычислений (три

вида нужны для иллюстрации тезиса Черча):

- равнодоступные адресные машины с сохраняемой в памяти

программой (РАСП), кроме всего прочего, это еще и математически

точная иллюстрация архитектуры Фон-Неймана (можно ее развить и

до параллельной архитектуры ПРАСП, что сейчас актуально);

иллюстрация методов программирования на такой модели заодно

является и экскурсом в историю информатики; для изучения

сложностных ограничений вычислимости изучается практически

точная модель семейств реальных компьютеров с сокращенным

набором команд: ограниченные РАСП (и ПРАСП) - ОРАСП (и ОПРАСП),

на которые накладываются ограничения по используемым

диапазонам адресов и чисел вообще; эти модели очень удобны для

того, чтобы приводить примеры практической относительной

неразрешимости, когда даются задачи, которые в идеале, вообще

говоря, можно решить алгоритмически, но для некоторых конкретных

сложностных ограничений они становятся неразрешимыми;

- для иллюстрации свойств замкнутости классов (ограниченной)

вычислимости удобно в качестве примера модели привести

определение вычислимости на основе идеального языка; лучше

всего для этой цели подходят идеализированные подмножества

реальных наиболее традиционных алгоритмических языков,

например, pascal и C (можно подобрать даже подходящее

"семантическое пересечение" этих языков); заодно это помогает

студентам понять, что представляет собой "ядро" этих языков,

избавившись от вторичных деталей; наиболее удачными

представляются чисто арифметические языки (работающие с

натуральными или целыми числами) и "структурные" языки,

работающие с бинарными деревьями или термами; возможно и

наложение сложностных ограничений на используемые данные;

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

ИНТЕРПРЕТАТОРА (универсального алгоритма) для РАСП (ОРАСП) и

эта конструкция удобно с самого начала излагается в сложностной

форме; меры сложности для этой модели - более грубые, чем для

РАСП, но легче поддаются оценке;

- в любом случае необходимы модели, основанные на рекурсивных

схемах: числовых, словарных и структурных (на термах); эти

модели - наиболее традиционные математические конструкции (с

точки зрения остальной математики); кроме того, с точки зрения

иллюстрации тезиса Черча, рекурсивые схемы могут

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

идеальных алгоритмических языках в программы РАСП; это также

является иллюстрацией понятия компилятора и одним из его

простейших примеров; рекурсивные схемы удобно определить так,

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

алгоритмического языка (который должен содержать подпрограммы,

в том числе и рекурсивные); семантика идеального

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

(возможно и преобразование - компиляция идеальных программ в

рекурсивные схемы).

В качестве вспомогательных моделей вычислимости с

ограниченной сложностью берутся модели, основанные на схемах из

логических элементов и на конечных автоматах (модель конечных

автоматов полезна в виду ее широкой известности и практического

использования многих связанных с ней понятий). Модели на схемах

из логических элементов нужны для получения конкретных примеров

задач большой сложности.

Во-вторых, излагаемые результаты должны сразу даваться и в

конкретном сложностном варианте, как можно более близком к

практике. Например, приводится не просто пример неразрешимого

множества, а излагается способ определения множеств,

неразрешимых при заданных сложностных ограничениях (и

разрешимых при других - более слабых ограничениях). При этом,

если быть ближе к практике, то фактически получается некоторое

комбинированное ограничение на размер программы, размер

используемой памяти и время работы. Надо подчеркнуть при этом,

что есть некоторый разрыв между нижними теоретическими

границами сложности и верхними практическими, более того, мы не

знаем, что будет происходить при ослаблении только ОДНОГО

ограничения - мы знаем, лишь, что если одновременно ослабить

ВСЕ (хотя и относительно немного), то задача из разряда

неразрешимых перейдет в разряд разрешимых.

В-третьих нужно с крайней осторожностью относиться к полным

задачам классов, для которых достаточно эффективные

универсальные разрешающие процедуры неизвестны: таким, как

NP-полные проблемы. Для многих из NP-полных задач известны

очень сложные сводимости к ним классически трудных задач. В

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

сложность сводимости, а конкретные относительные границы

сложности вычислений: сводимость может быть настолько сложной,

что окажется бесполезной с практической точки зрения. С другой

стороны, иногда сама формулировка задачи в этом случае

оказывается непрактичной: например, задача о рюкзаке с

"суперастрономической" точностью. Следует заметить, что

результаты об относительной неразрешимости, хотя и в любом

случае негативны, но могут обладать "здоровым" и "нездоровым"

негативизмом. В первом случае мы строго обосновали конкретные

ограничения, во втором - ссылаемся на то, что задачу никто

еще не решил. От вторых формулировок следует избавляться,

заменяя их на относительные оценки сложности.

  1. Цели курса

Общие требования к курсам по теории алгоритмов и сложности

для специалистов по информатике

(разработаны на основе кн.: "Рекомендации по преподаванию

информатики в университетах" / Пер. с англ., С.-Петербург:

Изд-во СПбГУ, 2002)

Основная цель преподавания Теории алгоритмов и сложности для

будущих специалистов по информатике - дать им инструмент для

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

задач по программированию становятся некорректными: задачи

становятся или неразрешимыми даже в принципе (в идеале), или

неразрешимыми с учетом конкретной возможности использования

вычислительных ресурсов. В свете этого некоторые традиции в

изложении этой науки в академической литературе нуждаются в

пересмотре для того, чтобы излагаемые результаты

формулировались в виде пригодном для их практического

применения без приложения дополнительных теоретических усилий.

  1. Учебно-тематический план

Тема

Количество часов

Лекц

Лаб.

Сам

1

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

2

1

3

2

Виды алгоритмов

2

1

3

3

Магазинные автоматы. Нормальные алгоритмы. Регистровые машины

2

1

3

4

Равнодоступные адресные машины (РАМ)

2

1

3

5

Примитивно рекурсивные, частично-рекурсивные и общерекурсивные функции

2

1

3

6

Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов

2

1

3

7

Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.

2

1

3

8

Программа машины Джонса как структура данных

2

1

3

9

Разрешимые и неразрешимые множества.

Перечислимые и неперечислимые множества

2

1

3

10

Элементарные по Кальмару функции

2

1

3

11

Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности

2

1

3

12

Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи

2

1

3

13

On-line - вычисления, вычисления в реальное время

2

1

3

14

Автоматные вычисления. Регулярные множества

2

1

3

15

Регулярность автоматных и автоматность регулярных множеств

2

1

3

16

Связь логики и вычислимости

2

1

3

17

Доказательства как программы

1

1

18

Нетрадиционные конструктивные теории

1

1

  1. Содержание лекционных занятий



Скачать документ

Похожие документы:

  1. Рабочая программа дисциплины: интеллектуальные информационные системы для специальностей: 351400 Прикладная информатика (по областям)                                      Ведущая кафедра

    Рабочая программа
    1. Государственного образовательного стандарта высшего профессионального образования по специальности или направлению подготовки дипломированного специалиста 351400 "Прикладная информатика (по областям)", утвержденного приказом
  2. Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика ( в сфере сервиса )»

    Учебное пособие
    Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика (в сфере сервиса)», изучающих дисциплину «Вычислительные системы, сети и телекоммуникации», и разработано с целью
  3. Учебно-методический комплекс «Высокоуровневые методы информатики и программирования» (для студентов отделения высшего профессионального образования специальности «Прикладная информатика (в экономике)») Рубцовск

    Учебно-методический комплекс
    Рабочая программа учебной дисциплины «Высокоуровневые методы информатики и программирования» предназначена для реализации государственных требований к минимуму содержания и уровню подготовки выпускников по специальности: 351400 «Прикладная
  4. Учебное пособие допущен о министерством образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в сфере сервиса)» Омск 2005

    Учебное пособие
    Учебное пособие разработано с целью обеспечения обучающихся и преподавателей систематизированным учебным материалом по теоретическим основам операционных систем.
  5. Отчет по проекту: Гуманитарная компонента в учебных планах высшего профессионального образования: мировой опыт и российские реалии Программа

    Публичный отчет
    В недавно опубликованном “Российской газетой” интервью Я.И.Кузьминов, ректор Государственного университета – Высшей школы экономики и права, говорит: “Наше высшее образование где-то наполовину потеряло звание профессионального.

Другие похожие документы..