Бекітілдіутвержден



жүктеу 4.54 Mb.
бет23/26
Дата15.01.2017
өлшемі4.54 Mb.
1   ...   18   19   20   21   22   23   24   25   26

ТК 3.1

Пәннің шифры: AET 5303

Пән атауы: Алгоритмдер және есептеу теориясы

Пререквизитері: Программалау

Постреквизиттері: ХХІ ғасырдың әдіснамасы және информатика мен білімді ақпараттандыру аясында оқыту әдістемесі және тәрбиелеу

Мақсаты: Курс есептеу және дәлелдеу сияқты математиканың фундаменталды түсініктерімен танысуға арналған. Алгоритмдер теориясын және математикалық логикадағы аксиоматикалық келулерді қарастырады
1.1.1.1.1.1Пәнге берілген қысқаша сипаттама: Алгоритмдер түсінігін. Алгоритмдік модель классификациясын. Тьюрингмашиннасының теориясын. "Дәлелдеу" және "есептеу". "Алгоритм" түсінігі анықталады, алгоритмге қойылатын негізгі талаптар қарастырылады,
1.1.1.1.1.2Тьюрингмашинасы. Есептеулер. мысалдар.
1.1.1.1.1.3Рекурсивті функциясы. Рекурсивті теория функциясына кіріспе. Рүқсат етілген, аударылатын жиындар. Аяққы автоматтар теориясына кіріспе.
1.1.1.1.1.4Аяққы автоматтар нұсқалары мен қасиеттері.
1.1.1.1.1.5Аяққы автоматтардың алгоритмдік мүмкіндіктері қарастырылады. Петри желілері Формальдік жүйелері. Қаситтер, интерпретация, модельдеу
1.1.1.1.1.6Формальдік грамматика Логика. Айтылуларды есептеу және предикаттарды есептеу. Метатеория. Предикаттарды есептеуге кіріспе.

Күтілетін нәтиже:

- әртүрлі алгоритмдердің құрылымдық схемасын;

- талап ететін есептерге сәйкес мәліметтер құрылымын ұйымдастыруды;

- тіл құрылысын қолданып берілген программалау тілінде программа құру және

жақсы стилде программа жазу;

- программаны сынау және қалыптастыру, сапалы программалық құжаттарды

құруды білулері тиіс.

Құзіреті: өмірде кездесетін түрлі есептерді шешуге компьютерді тиімді, пайдалану, енгізілетін, шығарылатын мәліметтерді формальдау және кез келген есепке алгоритм құра білу мүмкіндігіне ие болады.


К.В.3.1

Шифр дисциплины: ATV 5303

Название дисциплины: Алгоритмы и теория вычислений

Пререквизиты: Программирование

Постреквизиты: методология обучения и воспитания информатики и информатизация образования ХХІ веке

Цель изучения: Курс посвящен знакомству с такими фундаментальными математическими понятиями, как вычисления и доказательство. Курс предусматривает изучение теории алгоритмов и аксиоматического подхода к математической логике
1.1.1.1.1.7Краткое содержание основных разделов: Понятие алгоритма. Классификация алгоритмических моделей. Знакомство с машиной Тьюринга

В начале лекции рассказывается об истории возникновения математики, формировании понятий "Доказательство" и "Вычисление". Определяется понятие "Алгоритм", приводятся основные требования, предъявляемые к алгоритму. Во второй половине лекции рассказывается о классификации алгоритмических моделей, начинается знакомство с машинами Тьюринга. Машина Тьюринга. Вычислимость. Примеры. Способы задания

В начале лекции обсуждается понятие вычислимости. Далее приводится описание, способы задания, указываются особенности программирования машин Тьюринга (МТ). Рассматриваются основные операции над МТ, доказывается теорема о существовании универсальной МТ.


1.1.1.1.1.8Рекурсивные функции

Введение в теорию рекурсивных функций. Дается определение, рассматриваются примеры, способы задания рекурсивных функций, формулируются и доказываются соответствующие теоремы.
1.1.1.1.1.9Разрешимые и перечисляемые множества. Введение в теорию конечных автоматов

В первой части обсуждаются вопросы разрешимости и перечислимости множеств, сходимости алгоритмов, приводится формулировка теоремы Райса. Вторая часть лекции посвящена введению в теорию конечных автоматов (КА). Дается формальное определение КА, рассматриваются способы задания, примеры.
1.1.1.1.1.10Свойства и варианты конечных автоматов

свойства и варианты конечных автоматов (КА). Дается определение, и приводятся примеры эквивалентных автоматов.
1.1.1.1.1.11Алгоритмические возможности конечных автоматов. Сети Петри

В лекции рассматривается понятие регулярного множества. Приводится формулировка теоремы Клини. Рассматривается блочное описание конечного автомата. Обсуждаются понятия композиции и декомпозиции. В заключение рассматриваются сети Петри.
1.1.1.1.1.12Формальные системы. Свойства, интерпретация, моделирование

Лекция посвящена формальным системам (ФС). Дается строгое определение ФС, приводятся примеры, рассматриваются свойства ФС.
1.1.1.1.1.13Формальные грамматики

В лекции рассматриваются и строго определяются такие понятия как формальный язык, грамматика языка, язык грамматики. Приводится классификация формальных грамматик по Хомскому. Рассматриваются примеры.
1.1.1.1.1.14Логика. Исчисления высказываний и исчисление предикатов

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

В первой половине лекции обсуждается понятие метатеории и метатеорем. Приводится теорема о дедукции, ее доказательство, обратная теорема о дедукции. В завершение рассматривается пример. Вторая половина лекции посвящена введению в исчисление предикатов (ИП): рассматриваются основные определения и понятия, дается формальное определение ИП.


Достарыңызбен бөлісу:
1   ...   18   19   20   21   22   23   24   25   26


©melimde.com 2017
әкімшілігінің қараңыз

    Басты бет