Введение в схемы, автоматы и алгоритмы

: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Темы: Алгоритмы и дискретные структуры, Дискретные структуры, Алгоритмы
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР). Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков. Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Цель: Ознакомить студентов с базовыми понятиями и методами решения типовых задач в таких разделах дискретной математики и теоретической информатики как представление булевых функций с помощью схем и диаграмм, теория конечных автоматов и теория алгоритмов, выработать у них навыки алгоритмического мышления, характерного для этих дисциплин.
Необходимые знания: Для изучения курса желательно предварительное знакомство с материалами курса "Основы дискретной математики".

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
1 час 27 минут
Предварительные сведения
Класс mathcal{P}_n булевых функций от n переменных. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой и 2-х переменных. Булевы (логические) формулы и их эквивалентность. Основные эквивалентности ( законы логики ). Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Графы. Деревья.
Оглавление
    		-
    Лекция 2
    40 минут
    Реализация булевых функций с помощью логических схем
    Логические схемы (схемы из функциональных элементов) и реализуемые ими функции. Задачи синтеза и анализа схем. Логические схемы и линейные программы. Примеры логических схем: сложение по модулю 2 и двоичный сумматор
    Оглавление
      		-
      Тест 1
      18 минут
      		 -
      Лекция 3
      47 минут
      Упорядоченные бинарные диаграммы решений (УБДР)
      Бинарные деревья решений и их превращение в упорядоченные бинарные диаграммы решений (УБДР). Сокращенные УБДР и их построение по произвольным УБДР, алгоритм СОКРАЩЕНИЕ-УБДР. Построение сокращенных УБДР по формулам
      Оглавление
        		-
        Тест 2
        18 минут
        		 -
        Лекция 4
        1 час 49 минут
        Конечные автоматы: преобразователи и распознаватели
        Конечные автоматы-преобразователи. Пример: сложение двоичных чисел. Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство правильности автомата. Произведение автоматов. Замкнутость класса конечно-автоматных языков относительно теоретико-множественных операций
        Оглавление
          		-
          Тест 3
          24 минуты
          		 -
          Лекция 5
          49 минут
          Регулярные языки и конечные автоматы
          Операции конкатенации и итерации языков. Регулярные выражения и языки. Примеры регулярных выражений и языков. Построение конечного автомата по регулярному выражению
          Оглавление
            		-
            Тест 4
            18 минут
            		 -
            Лекция 6
            1 час 18 минут
            Свойства замкнутости класса автоматных языков. Неавтоматные языки
            Построение конечного автомата для гомоморфного образа автоматного языка и для обращения гомоморфизма. Теорема о разрастании для автоматных языков. Ее применение для доказательства неавтоматности языка.Примеры неавтоматных языков
            Оглавление
              		-
              Тест 5
              18 минут
              		 -
              Лекция 7
              42 минуты
              Алгоритмы: структурированные программы
              Алгоритмы и модели вычислений. Структурированные программы: синтаксис и семантика. Арифметические функции, вычислимые структурированными программами
              Оглавление
                		-
                Тест 6
                18 минут
                		 -
                Лекция 8
                1 час 5 минут
                Алгоритмы: частично рекурсивные функции
                Операторы суперпозиции, примитивной рекурсии и минимизации. Классы частично рекурсивных и примитивно рекурсивных функций. Программная вычислимость частично рекурсивных функций. Рекурсивность табличных функций, функций, определенных с помощью суммирования и произведения, кусочно заданных функций, функций нумерации n-ок и функций, определенных совместной рекурсией
                Оглавление
                  		-
                  Тест 7
                  18 минут
                  		 -
                  Лекция 9
                  1 час 22 минуты
                  Алгоритмы: машины Тьюринга
                  Определение машин Тьюринга и класса вычислимых ими функций. Примеры работы машин Тьюринга. Тьюрингово программирование: последовательная и параллельная композиция, ветвление (условный оператор), повторение (оператор цикла)
                  Оглавление
                    		-
                    Тест 8
                    18 минут
                    		 -
                    Лекция 10
                    1 час 31 минута
                    Вычислимые функции, тезис Тьюринга-Черча и неразрешимые проблемы
                    Частично рекурсивные функции вычислимы на м.Т. М.Т. моделируют структурированные программы. Классы частично рекурсивных функций, функций, вычислимых структурированными программами, и функций, вычислимых машинами Тьюринга, совпадают. Тезис Тьюринга-Черча. Алгоритмически разрешимые и неразрешимые проблемы. Неразрешимость проблем самоприменимости, останова, тотальности, эквивалентности и оптимизации текста программ
                    Оглавление
                      		-
                      Тест 9
                      18 минут
                      		 -
                      5 часов
                      		 -

                      ( ! ) Warning: include_once(./includes/unicode.entities.inc) [<a href='function.include-once'>function.include-once</a>]: failed to open stream: No such file or directory in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5572101527368watchdog( )../bootstrap.inc:0
                      22.5575101529824module_invoke( )../bootstrap.inc:967
                      32.5575101531680call_user_func_array ( )../module.inc:462
                      42.5575101532016devel_watchdog( )../module.inc:462
                      52.5576101532864decode_entities( )../devel.module:382
                      62.5576101534784drupal_error_handler( )../devel.module:340
                      72.5577101538392watchdog( )../common.inc:663
                      82.5577101540448module_invoke( )../bootstrap.inc:967
                      92.5577101542304call_user_func_array ( )../module.inc:462
                      102.5577101542640devel_watchdog( )../module.inc:462
                      112.5577101543336decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once() [<a href='function.include'>function.include</a>]: Failed opening './includes/unicode.entities.inc' for inclusion (include_path='.:/usr/local/zend/var/libraries/Zend_Framework_1/default/library:/usr/local/zend/share/pear') in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5572101527368watchdog( )../bootstrap.inc:0
                      22.5575101529824module_invoke( )../bootstrap.inc:967
                      32.5575101531680call_user_func_array ( )../module.inc:462
                      42.5575101532016devel_watchdog( )../module.inc:462
                      52.5576101532864decode_entities( )../devel.module:382
                      62.5576101534784drupal_error_handler( )../devel.module:340
                      72.5577101538392watchdog( )../common.inc:663
                      82.5577101540448module_invoke( )../bootstrap.inc:967
                      92.5577101542304call_user_func_array ( )../module.inc:462
                      102.5577101542640devel_watchdog( )../module.inc:462
                      112.5577101543336decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once(./includes/unicode.entities.inc) [<a href='function.include-once'>function.include-once</a>]: failed to open stream: No such file or directory in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5572101527368watchdog( )../bootstrap.inc:0
                      22.5575101529824module_invoke( )../bootstrap.inc:967
                      32.5575101531680call_user_func_array ( )../module.inc:462
                      42.5575101532016devel_watchdog( )../module.inc:462
                      52.5576101532864decode_entities( )../devel.module:382
                      62.5583101534976drupal_error_handler( )../devel.module:340
                      72.5583101538664watchdog( )../common.inc:663
                      82.5583101540720module_invoke( )../bootstrap.inc:967
                      92.5584101542576call_user_func_array ( )../module.inc:462
                      102.5584101542912devel_watchdog( )../module.inc:462
                      112.5584101543688decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once() [<a href='function.include'>function.include</a>]: Failed opening './includes/unicode.entities.inc' for inclusion (include_path='.:/usr/local/zend/var/libraries/Zend_Framework_1/default/library:/usr/local/zend/share/pear') in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5572101527368watchdog( )../bootstrap.inc:0
                      22.5575101529824module_invoke( )../bootstrap.inc:967
                      32.5575101531680call_user_func_array ( )../module.inc:462
                      42.5575101532016devel_watchdog( )../module.inc:462
                      52.5576101532864decode_entities( )../devel.module:382
                      62.5583101534976drupal_error_handler( )../devel.module:340
                      72.5583101538664watchdog( )../common.inc:663
                      82.5583101540720module_invoke( )../bootstrap.inc:967
                      92.5584101542576call_user_func_array ( )../module.inc:462
                      102.5584101542912devel_watchdog( )../module.inc:462
                      112.5584101543688decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once(./includes/unicode.entities.inc) [<a href='function.include-once'>function.include-once</a>]: failed to open stream: No such file or directory in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5590101527912watchdog( )../bootstrap.inc:0
                      22.5590101529968module_invoke( )../bootstrap.inc:967
                      32.5590101531824call_user_func_array ( )../module.inc:462
                      42.5590101532160devel_watchdog( )../module.inc:462
                      52.5591101532864decode_entities( )../devel.module:382
                      62.5591101534784drupal_error_handler( )../devel.module:340
                      72.5591101538392watchdog( )../common.inc:663
                      82.5591101540448module_invoke( )../bootstrap.inc:967
                      92.5591101542304call_user_func_array ( )../module.inc:462
                      102.5591101542640devel_watchdog( )../module.inc:462
                      112.5592101543336decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once() [<a href='function.include'>function.include</a>]: Failed opening './includes/unicode.entities.inc' for inclusion (include_path='.:/usr/local/zend/var/libraries/Zend_Framework_1/default/library:/usr/local/zend/share/pear') in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5590101527912watchdog( )../bootstrap.inc:0
                      22.5590101529968module_invoke( )../bootstrap.inc:967
                      32.5590101531824call_user_func_array ( )../module.inc:462
                      42.5590101532160devel_watchdog( )../module.inc:462
                      52.5591101532864decode_entities( )../devel.module:382
                      62.5591101534784drupal_error_handler( )../devel.module:340
                      72.5591101538392watchdog( )../common.inc:663
                      82.5591101540448module_invoke( )../bootstrap.inc:967
                      92.5591101542304call_user_func_array ( )../module.inc:462
                      102.5591101542640devel_watchdog( )../module.inc:462
                      112.5592101543336decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once(./includes/unicode.entities.inc) [<a href='function.include-once'>function.include-once</a>]: failed to open stream: No such file or directory in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5590101527912watchdog( )../bootstrap.inc:0
                      22.5590101529968module_invoke( )../bootstrap.inc:967
                      32.5590101531824call_user_func_array ( )../module.inc:462
                      42.5590101532160devel_watchdog( )../module.inc:462
                      52.5591101532864decode_entities( )../devel.module:382
                      62.5596101534976drupal_error_handler( )../devel.module:340
                      72.5596101538664watchdog( )../common.inc:663
                      82.5597101540720module_invoke( )../bootstrap.inc:967
                      92.5597101542576call_user_func_array ( )../module.inc:462
                      102.5597101542912devel_watchdog( )../module.inc:462
                      112.5597101543688decode_entities( )../devel.module:382
                      ( ! ) Warning: include_once() [<a href='function.include'>function.include</a>]: Failed opening './includes/unicode.entities.inc' for inclusion (include_path='.:/usr/local/zend/var/libraries/Zend_Framework_1/default/library:/usr/local/zend/share/pear') in /.2/var_www_new.intuit.ru/htdocs/includes/unicode.inc on line 340
                      Call Stack
                      #TimeMemoryFunctionLocation
                      12.5590101527912watchdog( )../bootstrap.inc:0
                      22.5590101529968module_invoke( )../bootstrap.inc:967
                      32.5590101531824call_user_func_array ( )../module.inc:462
                      42.5590101532160devel_watchdog( )../module.inc:462
                      52.5591101532864decode_entities( )../devel.module:382
                      62.5596101534976drupal_error_handler( )../devel.module:340
                      72.5596101538664watchdog( )../common.inc:663
                      82.5597101540720module_invoke( )../bootstrap.inc:967
                      92.5597101542576call_user_func_array ( )../module.inc:462
                      102.5597101542912devel_watchdog( )../module.inc:462
                      112.5597101543688decode_entities( )../devel.module:382