ТК 3.1
Пәннің шифры: AET 5303
Пән атауы: Алгоритмдер және есептеу теориясы
Пререквизитері: Программалау
Постреквизиттері: ХХІ ғасырдың әдіснамасы және информатика мен білімді ақпараттандыру аясында оқыту әдістемесі және тәрбиелеу
Мақсаты: Курс есептеу және дәлелдеу сияқты математиканың фундаменталды түсініктерімен танысуға арналған. Алгоритмдер теориясын және математикалық логикадағы аксиоматикалық келулерді қарастырады
Пәнге берілген қысқаша сипаттама: Алгоритмдер түсінігін. Алгоритмдік модель классификациясын. Тьюрингмашиннасының теориясын. "Дәлелдеу" және "есептеу". "Алгоритм" түсінігі анықталады, алгоритмге қойылатын негізгі талаптар қарастырылады, Тьюрингмашинасы. Есептеулер. мысалдар. Рекурсивті функциясы. Рекурсивті теория функциясына кіріспе. Рүқсат етілген, аударылатын жиындар. Аяққы автоматтар теориясына кіріспе. Аяққы автоматтар нұсқалары мен қасиеттері. Аяққы автоматтардың алгоритмдік мүмкіндіктері қарастырылады. Петри желілері Формальдік жүйелері. Қаситтер, интерпретация, модельдеу Формальдік грамматика Логика. Айтылуларды есептеу және предикаттарды есептеу. Метатеория. Предикаттарды есептеуге кіріспе.
Күтілетін нәтиже:
- әртүрлі алгоритмдердің құрылымдық схемасын;
- талап ететін есептерге сәйкес мәліметтер құрылымын ұйымдастыруды;
- тіл құрылысын қолданып берілген программалау тілінде программа құру және
жақсы стилде программа жазу;
- программаны сынау және қалыптастыру, сапалы программалық құжаттарды
құруды білулері тиіс.
Құзіреті: өмірде кездесетін түрлі есептерді шешуге компьютерді тиімді, пайдалану, енгізілетін, шығарылатын мәліметтерді формальдау және кез келген есепке алгоритм құра білу мүмкіндігіне ие болады.
|
К.В.3.1
Шифр дисциплины: ATV 5303
Название дисциплины: Алгоритмы и теория вычислений
Пререквизиты: Программирование
Постреквизиты: методология обучения и воспитания информатики и информатизация образования ХХІ веке
Цель изучения: Курс посвящен знакомству с такими фундаментальными математическими понятиями, как вычисления и доказательство. Курс предусматривает изучение теории алгоритмов и аксиоматического подхода к математической логике
Краткое содержание основных разделов: Понятие алгоритма. Классификация алгоритмических моделей. Знакомство с машиной Тьюринга
В начале лекции рассказывается об истории возникновения математики, формировании понятий "Доказательство" и "Вычисление". Определяется понятие "Алгоритм", приводятся основные требования, предъявляемые к алгоритму. Во второй половине лекции рассказывается о классификации алгоритмических моделей, начинается знакомство с машинами Тьюринга. Машина Тьюринга. Вычислимость. Примеры. Способы задания
В начале лекции обсуждается понятие вычислимости. Далее приводится описание, способы задания, указываются особенности программирования машин Тьюринга (МТ). Рассматриваются основные операции над МТ, доказывается теорема о существовании универсальной МТ.
Рекурсивные функции
Введение в теорию рекурсивных функций. Дается определение, рассматриваются примеры, способы задания рекурсивных функций, формулируются и доказываются соответствующие теоремы.
Разрешимые и перечисляемые множества. Введение в теорию конечных автоматов
В первой части обсуждаются вопросы разрешимости и перечислимости множеств, сходимости алгоритмов, приводится формулировка теоремы Райса. Вторая часть лекции посвящена введению в теорию конечных автоматов (КА). Дается формальное определение КА, рассматриваются способы задания, примеры.
Свойства и варианты конечных автоматов
свойства и варианты конечных автоматов (КА). Дается определение, и приводятся примеры эквивалентных автоматов.
Алгоритмические возможности конечных автоматов. Сети Петри
В лекции рассматривается понятие регулярного множества. Приводится формулировка теоремы Клини. Рассматривается блочное описание конечного автомата. Обсуждаются понятия композиции и декомпозиции. В заключение рассматриваются сети Петри.
Формальные системы. Свойства, интерпретация, моделирование
Лекция посвящена формальным системам (ФС). Дается строгое определение ФС, приводятся примеры, рассматриваются свойства ФС.
Формальные грамматики
В лекции рассматриваются и строго определяются такие понятия как формальный язык, грамматика языка, язык грамматики. Приводится классификация формальных грамматик по Хомскому. Рассматриваются примеры.
Логика. Исчисления высказываний и исчисление предикатов
В начале лекции рассказывается об истории возникновения понятия " Логика". Далее обсуждаются основные различия между исчислением высказываний и исчислением предикатов. Рассматриваются правила вывода Modus Ponens, приводятся примеры их использования.
|
