WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

ТЕОРИЯ ПРОГРАММИРОВАНИЯ

к.ф.-м.н., доцент Бульонков М.А.

Понятие машины Тьюринга. Запись программ на МТ. Функционирования

1.

МТ: конфигурация, протокол. Вычисляемая функция. Временная

сложность. Ёмкостная сложность. Вариации МТ. Понятие РАМ-машины.

Вычисление на РАМ: состояние памяти, конфигурация, операнды, команды.

Функция, вычисляемая РАМ. Временная и мкостная сложность,

равномерный и логарифмический весовой критерии. Понятие сложности в среднем.

Понятие порядка сложности, полиномиальная связанность, 2.

экспоненциальная функция. Понятие моделирования, пошаговое моделирование. Моделирование РАМ на МТ, оценка сложности.

Невозможность моделирование РАМ на МТ при равномерном весовом критерии. Моделирование РАМ на МТ при логарифмическом весовом критерии, оценка сложности.

Теорема об ускорении. Понятие сигнализирующего оператора. Временная и 3.

мкостная сложность МТ как сигнализирующие. Теорема Цейтина, диагональный метод. Теорема Рабина.

Нижние оценки. Задачи, допускающие матричные формулировки.

4.

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

Примеры использования.

Понятие конечного автомата. Графовое представление. Язык конечного 5.

автомата. Понятие регулярного выражения и его языка. Понятие регулярного выражения. Теорема о регулярности конечно-автоматных языков. Лемма о разрастании, примеры использования.

Проблемы пустоты и эквивалентности конечных автоматов. Переборный и 6.

алгебраический способы доказательства эквивалентности, оценка сложности. Понятие минимального автомата и его построение методом грубейшего разбиения. Оценка сложности. Доказательство эквивалентности методом сведения к задаче «Объединить-найти».

Поиск в информационном массиве. Линейный поиск, оценка сложности в 7.

худшем и среднем. Бинарный поиск и двоичные деревья поиска.

Сбалансированные деревья. 2-3 деревья: оценка сложности, процедуры вставки и удаления. B-деревья, как обобщение 2-3 деревьев: оценка сложности. АВЛ-деревья: оценка сложности, процедуры вставки в АВЛ дерево. Метод расстановки: оценка сложности в худшем и среднем.

Задача сортировки. Классификация методов сортировки: по области 8.

применения, по используемым методам. Критерии оценки сложности.

Примеры сортировки вставкой, выбором и обменом. Понятие дерева решений. Оценка сложности в худшем случае для сортировки, основанной на сравнениях. Сортировка слиянием: оценка временной и мкостной сложности в худшем случае. Оценка сложности в среднем для сортировки, основанной на сравнениях. Быстрая сортировка: оценка временной сложности в среднем.

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

9.

Понятие полурештки свойств, свойства ограниченности и обрыва цепей.

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

Формулировка задачи глобального анализа. Понятие точного решение ЗГА, Понятие недетерминированного процесса разметки. Понятие стационарной разметки, доказательство е существования. Понятие безопасной разметки.

Теоремы о безопасности и единственности стационарной разметки.

Теорема о точности стационарной разметки в дистрибутивном случае.

10.

Пример формулировки ЗГА для анализа циклов в графе. Методы минимизации количества применений правила разметки. Теорема о невозможности построения точного решения в монотонном случае.

Понятие стандартной схемы: базис, термы, операторы. Понятие аргументов 11.

и результатов, правильность стандартной схемы. Понятие интерпретации:

значение терма, протокол, результат. Свободные интерпретации как пример интерпретации. Понятие функциональной эквивалентности стандартных схем. Понятие логико-термальной эквивалентности: логико-термальная история, детерминант. Теорема о корректности лт-эквивалентности.

Понятие информационных связей и информационного графа. Нахождение 12.

информационного графа путм сведения к ЗГА. Компоненты связности информационного графа, их зацеплнность. Переименование переменных, минимизация количества переменных в стандартной схеме путм сведения к задаче раскраски графов.

Понятие инвариантного соотношения. Функциональные сети, как средство 13.

представления инвариантных соотношений. Множество утверждений функциональной сети, приведнные сети. Операция пересечения функциональных сетей. Функциональные сети как полурештка свойств.

Преобразователи функциональных сетей, их дистрибутивность. Решение задачи нахождения инвариантных соотношений методом ЗГА.

Понятие фрагмента стандартной схемы. Фрагмент, как обобщение 14.

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

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

Теорема о полноте: согласование стандартных схем, Л-графы, Оценка сложности.

Понятие смешанного вычисления программ: программы как данные, 15.

доступные и задержанные вычисления, основное уравнение СВ. Связь смешанных вычислений с S-m-n теоремой Клини. Условия выгодности СВ, Связь СВ и трансляции программ: понятие транслятора и интерпретатора.

Проекции Футамуры. Понятие метаинтерпретатора и автоинтерпретатора, критерий оптимальности Джонса. Другие потенциальные применения СВ.

Пример функции xn. Интерпретационный подход к реализации СВ. Понятие 16.

генерирующего расширения, как объектного кода для семантики, заданной СВ, Трансформационный подход.

Проблема задержанного управления при СВ, Поливариантные СВ, Пример 17.

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

Понятие анализа периода связывания (BTA). Сведение задачи BTA к ЗГА, 18.

Решение BTA методом нахождения неподвижной точки. Решение BTA методом решения системы неравенств. Понятие поливариантного анализа периода связывания: преобразование программы в процессе анализа.

ЛИТЕРАТУРА

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.:

Издательский дом “Вильямс”, 2000.

Бульонков М.А. Смешанные вычисления. Учебное пособие. – Новосибирск:

Изд-во НГУ, 1995.

Карпов Ю. Теория автоматов. Учебник для вузов. – СПб.: Издательский дом Котов В.Е., Сабельфельд В.К. Теория схем программ. – М.: Наука, 1991.

Лавров С. Программирование. Математические основы, средства, теория. – СПб.: БХВ-Петербург, 2001.

Мотвани Р., Хопкрофт Дж., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е издание, – М.: Издательский дом “Вильямс”, Сабельфельд В.К. Теория программирования. Учебное пособие. – Новосибирск: Изд-во НГУ, 1993.

Ахо А., Сети Р., Ульман Дж.Д. Компиляторы: принципы, технологии и инструменты. – М.: Издательский дом “Вильямс”, 2001.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

Биркгоф Г. Теория решеток. – М.: Наука, 1984.

10.

Ершов А.П. Введение в теоретическое программирование (беседы о 11.

методе). – М.: Наука, 1977.

Касьянов В.Н. Лекции по теории формальных языков, автоматов и 12.

сложности вычислений. Учебное пособие. – Новосибирск: Изд-во НГУ, Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.:

13.

Котов В.Е. Введение в теорию схем программ. – М.: Наука, 1978.

14.

Трахтенброт Б.А. Сложность алгоритмов и вычислений. – Новосибирск:

15.

Изд-во НГУ, 1967.





Похожие работы:

«Муниципальное бюджетное образовательное учреждение дополнительного образования детей Центр детского творчества станицы Роговской муниципального образования Тимашевский район. ЗАНЯТИЕ ПО ТЕМЕ: ТЕАТРАЛЬНОЕ ИСКУССТВО Разработал: Педагог дополнительного образования Протопопов А.А 2013г Пояснительная записка Направленность театральная Тема урока Театральное искусство Характеристика В группе 11 человек, возраст 11-16 лет, программа авторская, составил Протопопов Александр Александрович, 12 часов в...»

«Приложение 8 Б: Рабочая программа факультативной дисциплины Педагогическое проектирование ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПЯТИГОРСКИЙ ГОСУДАРСТВЕННЫЙ ЛИНГВИСТИЧЕСКИЙ УНИВЕРСИТЕТ Утверждаю Проректор по научной работе и развитию интеллектуального потенциала университета профессор З.А. Заврумов _2012 г. Аспирантура по специальности 13.00.01 Общая педагогика, история педагогики и образования отрасль науки: 13.00.00...»

«1. Общие положения 1.1. Настоящие Правила приема на обучение по программам подготовки научнопедагогических кадров в аспирантуре (далее – Порядок) регламентируют прием граждан Российской Федерации, иностранных граждан, лиц без гражданства на обучение в аспирантуре Керченского государственного морского технологического университета (далее – КГМТУ) по образовательным программам высшего образования – программам подготовки научно-педагогических кадров в аспирантуре, определяет перечень вступительных...»

«Российская академия художеств Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный академический художественный институт имени В.И.Сурикова (МГАХИ им.В.И.Сурикова) Кафедра русского и иностранных языков ПРОГРАММА КАНДИДАТСКОГО ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ ИНОСТРАННЫЙ ЯЗЫК Для аспирантов специальности 17.00.04 – Изобразительное и декоративно-прикладное искусство и архитектура Квалификация (степень) выпускника Москва, 2011...»

«Олег Матвейчев Уши машут ослом { Сумма политтехнологий } Данная книга представляет собой сборник, в который вошли 4 ранее опубликованные книги ( в несколько отредактированном виде) ПЛЮС двадцать НОВЫХ ( то есть в виде книги не опубликованных текстов): Таким образом, книга распадается на 5 частей: 1. Что такое политический консалтинг? (1998г) 2. Проблемы манипуляции (1999г) 3. Уши машут ослом.Современное социальное программирование (2002г) 4.Предвыборная камапния. Практика против теории ( 2003г)...»

«ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА ДЛЯ ПОСТУПАЮЩИХ В ДОКТОРАНТУРУ ПО СПЕЦИАЛЬНОСТИ 06D073900 Нефтехимия (шифр и название специальности) Алматы 2013 Научно-образовательный центр Химическая инженерия Казахстанско-Британский технический университет Ул. Валиханова, 106, г. Алматы, 050010, Казахстан тел: +7(727)291-5784 e-mail: [email protected] http://www.cheng.kbtu.kz Программа вступительного экзамена для поступающих в докторантуру по специальности 06D073900 - Нефтехимия разработана Высшей комиссией...»

«УТВЕРЖДЕНО: Директор Фонда Наше будущее /Н.И. Зверева/ __2011 г. ПОЛОЖЕНИЕ О ВСЕРОССИЙКОМ КОНКУРСЕ ПРОЕКТОВ СОЦИАЛЬНЫЙ ПРЕДПРИНИМАТЕЛЬ 2011 (далее – Положение) Настоящее Положение определяет порядок организации и проведения Всероссийского конкурса проектов Социальный предприниматель 2011 (далее по тексту Конкурс). Общие положения I. Всероссийский конкурс проектов Социальный предприниматель 2011 проводится Фондом региональных социальных программ Наше будущее (далее – Фонд), учрежденным Вагитом...»

«1 Министерство сельского хозяйства Российской Федерации Федеральное государственное образовательное учреждение высшего профессионального образования Кубанский государственный аграрный университет РАБОЧАЯ ПРОГРАММА по дисциплине ГСЭ.Ф.1 Иностранный язык (индекс и наименование дисциплины) Специальность 111201.65 Ветеринария Квалификация (степень) выпускника Ветеринарный врач Факультет Ветеринарной медицины Кафедра-разработчик Кафедра иностранных языков Ведущий Косенко С.П. преподаватель...»

«ПРОФИЛАКТИКА ВИЧ ИНФЕКЦИИ СРЕДИ ПОТРЕБИТЕЛЕЙ ИНЪЕКЦИОННЫХ НАРКОТИКОВ Практическое руководство Москва 2006 В работе над данным документом принимали участие: – Васильева Н. В. – директор Открытого Института Здоровья, г. Москва – Бобрик А. В. – заместитель директора Открытого Института Здоровья, г. Москва – Летягина В. А. – программный менеджер Открытого Института Здоровья, г. Москва – Бадриева Л. И. – зав. отделом психо социального консультирования ВИЧ инфицированных и групп риска...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Адыгейский государственный университет Факультет социальных технологий и туризма ПРОГРАММА вступительного испытания при приеме на обучение по программе подготовки аспирантуры по направлению подготовки кадров высшей квалификации 41 образование и педагогические науки квалификация: Исследователь. Преподаватель-исследователь профиль: 13.00.08 -...»

«Пояснительная записка В МАОУ СОШ №16 г. Сыктывкара реализуется учебный предмет Биология углубленного уровня: 4 часа в неделю в 10 классе, 3 часа в неделю в 11 классе. Данная РУП составлена в соответствии с федеральным компонентом государственного стандарта среднего (полного) общего образования по биологии, на основе программы углубленного курса В.Б. Захарова. Курс биологии на ступени среднего (полного) общего образования на углубленном уровне направлен на формирование у учащихся целостной...»

«ТЮМЕНСКАЯ ОБЛАСТЬ АССОЦИАЦИЯ ОРГАНИЗАТОРОВ ОТДЫХА И ОЗДОРОВЛЕНИЯ НАСЕЛЕНИЯ МЫ ВМЕСТЕ 625550, Тюменская область, Тюменский район, Тел/факс (3452): 59-32-27; 52-97-51 38 км Салаирского тракта Е-mail: [email protected] Исх №_ 2013 г. Для размещения на сайт МОО СДО Новости о жизни загородных центров в Тюменской области Приветствуем коллег отрасли отдыха и оздоровления из регионов Российской Федерации. Осенняя пора очень быстро пролетела и уже сейчас мы активно готовимся к предстоящим новогодним...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Кемеровский государственный университет Кафедра физиологии человека и животных и валеологии ПРОГРАММА кандидатского экзамена по специальности 19.00.02 - ПСИХОФИЗИОЛОГИЯ КЭ.А.03; цикл КЭ.А.00 Кандидатские экзамены основной профессиональной образовательной программы подготовки аспиранта по отрасли 03.00.00 Биологические науки Квалификация...»

«ВОКРУГ СВЕТА ЗА ДЕСЯТЬ ДНЕЙ Пособие для наставника Учебно-познавательная программа для детей ВОКРУГ СВЕТА ЗА ДЕСЯТЬ ДНЕЙ Пособие для учителя (Рекомендуется для детей 7 - 11 лет) Автор Ирина Царицон Редактор Евгений Новицкий Художник Евгения Царицон Компьютерная верстка Вадим Царицон Пособие разработано отделом детских программ Христианского научно-апологетического центра WWW.SCIENCEANDAPOLOGETICS.COM Руководитель отдела детских программ Ирина Царицон [email protected]...»

«Правительство Российской Федерации Санкт-Петербургский государственный университет Факультет психологии Регистрационный номер рабочей программы учебной дисциплины 2010 РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ Психофизиология с практикумом Основной образовательной программы высшего профессионального образования Психология Подготовка по направлению 030300 Психология Для получения квалификации (степени) Бакалавр Код по учебному плану форма обучения: очная Дисциплины Виды промежуточной аттестации:...»

«ИСПОЛНИТЕЛЬНО-РАСПОРЯДИТЕЛЬНЫЙ ОРГАН ГОРОДА МОНЧЕГОРСКА Администрация муниципального образования город Мончегорск с подведомственной территорией (АДМИНИСТРАЦИЯ города МОНЧЕГОРСКА) ПОСТАНОВЛЕНИЕ 03.09.2012 N 1182 Мончегорск Об утверждении Порядка предоставления грантов начинающим предпринимателям и малым инновационным компаниям на создание собственного бизнеса по результатам конкурса бизнес-планов В соответствии с Федеральным законом от 06.10.2003 N 131 - ФЗ Об общих принципах организации...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Санкт-Петербургский государственный университет аэрокосмического приборостроения УТВЕРЖДАЮ Ректор ГУАП д.т.н., профессор А.А. Оводенко 20_г. Программа профессиональной подготовки руководителей индустрии здоровья и эстетических услуг (велнесс-индустрии), менеджеров в сфере оказания медицинских услуг и эстетических услуг, подлежащих медицинскому лицензированию Разработчики программы, составители учебно-тематического плана к.т.н., доцент Яковлев А.В....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Кемеровский технологический институт пищевой промышленности 240700 Программа подготовки Промышленная биотехнология вид профессиональной деятельности Производственно-технологическаяи научно-исследовательская от г. 22.12.2009 NQ 808 Квалификация (степень) магистр Форма обучения очная Нормативный срок освоения программы - 2 года Кемерово 1....»

«НАЦИОНАЛЬНЫЙ ОТЧЕТ РЕСПУБЛИКИ ТАДЖИКИСТАН в рамках Программы UNEP по содействию и помощи развивающимся странам в выполнении Йоханнесбургского Плана реализации цели Планы (2005) действий по Интегрированному Управлению Водными Ресурсами и Водосбережению ДУШАНБЕ – 2006 НАЦИОНАЛЬНЫЙ ОТЧЕТ РЕСПУБЛИКИ ТАДЖИКИСТАН _ Общие сведения География: Таджикистан расположен в юго-восточной части Центральной Азии, на западе и северо-западе граничит с Узбекистаном, на северо-востоке – с Кыргызстаном, на востоке –...»

«СОДЕРЖАНИЕ Стр. 1. ОБЩИЕ ПОЛОЖЕНИЯ 4 Нормативные документы для разработки ООП по направлению 1.1. 4 подготовки Общая характеристика ООП.2. 6 1.3. Миссия, цели и задачи ООП ВПО 7 1.4. Требования к абитуриенту 7 ХАРАКТЕРИСТИКА ПРОФЕССИОНАЛЬНОЙ 2. 7 ДЕЯТЕЛЬНОСТИ ВЫПУСКНИКА ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 2.1. Область профессиональной деятельности выпускника Объекты профессиональной деятельности выпускника 2.2. Виды профессиональной деятельности выпускника 2.3. Задачи профессиональной деятельности...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.