Образовательной программы по укрупненной группе 230000 Информатика и вычислительная техника по направлению 230100. 62 Информатика и вычислительная техника по профилю 230100. 62. 09 Технологии разработки программного обеспечения Красноярск 2011 г

Вид материала

Документы

Содержание Дискретная математика Структура дисциплины Основные дидактические единицы В результате изучения дисциплины студент должен Виды учебной работы Теория алгоритмов

Подобный материал:

• Примерная программа учебной дисциплины, 177.93kb.
• Примерная программа профессионального модуля ввод и обработка цифровой информации, 453.01kb.
• Примерная программа профессионального модуля ввод и обработка цифровой информации, 455.69kb.
• Рабочая учебная программа по дисциплине «Базы данных» Направление №230100 «Информатика, 115.03kb.
• Образовательный стандарт по направлению 230100. 62 Информатика и вычислительная техника, 328.94kb.
• Основная образовательная программа высшего профессионального образования Направление, 300.24kb.
• Примерная программа учебной дисциплины основы электроники и цифровой схемотехники Санкт-Петербург, 137.39kb.
• Рабочая учебная программа по дисциплине «Информатика» Направление №230100 «Информатика, 91.73kb.
• Рабочая программа учебной дисциплины днн. 02 Современные научные проблемы автоматизированных, 221.23kb.
• Программа государственного экзамена по направлению 230100 «Информатика и вычислительная, 60.5kb.

Дискретная математика

Общая трудоемкость изучения дисциплины составляет 4 зачетных единиц (144 час).

Цели и задачи дисциплины

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

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

Структура дисциплины (распределение трудоемкости по отдельным видам аудиторных учебных занятий и самостоятельной работы): 72 часа – аудиторные, 72 часа – самостоятельная работа.

Основные дидактические единицы (разделы): множества и их спецификации; диаграммы Венна; отношения; свойства отношений; разбиения и отношение эквивалентности; отношение порядка; функции и отображения; операции; комбинаторные объекты; метод траекторий; основные понятия теории графов; маршруты; циклы; связность; планарные графы; обходы графов; деревья; алгоритмы на графах.

Компетенции обучающегося, формируемые в результате освоения дисциплины: ОК8, ОК11, ОК12, ПК1.

В результате изучения дисциплины студент должен:

знать: области применения моделей и подходов дискретной математики в компьютерных науках; способы представления и описание дискретных объектов; структуру дискретной математики как области знания; основные дискретные объекты, способы представления и методы перечисления дискретных объектов; круг задач, решаемых с помощью теоретико-множественных, комбинаторных, графических и логических методов описания и исследования.

уметь: выполнить основные операции над конечными множествами, проиллюстрировать действия с помощью диаграмм Эйлера – Венна; задать бинарное отношение, исследовать его свойства; решать задачи комбинаторного типа, применять основные комбинаторные объекты для разработки алгоритмов решения практических задач на ЭВМ; решать задачи с применением производящих функций; построить графическую модель объекта, задать ее одним из возможных способов и указать характеристики полученного графа, выполнить обход графа в глубину и в ширину, найти кратчайшее расстояние между двумя вершинами, построить каркасное дерево в графе; выполнить обход вершин бинарного дерева в прямом, обратном и внутреннем порядках, использовать бинарное дерево как модель для записи арифметических выражений, выражений на языках программирования и описания структуры данных;

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

Виды учебной работы: лекции, лабораторные работы, практические занятия, самостоятельная работа.

Изучение дисциплины – 2-й семестр. Студенты должны уже владеть основами программирования.

Теория алгоритмов

Цель дисциплины: овладение основами аппарата теории алгоритмов для последующего применения его при анализе и синтезе технических и программных систем с учётом специфических задач информатики и вычислительной техники.

Задачи дисциплины: изучение теоретических оснований теории алгоритмов, системы понятий и особенностей используемого аппарата; классификация задач теории алгоритмов; знакомство с методами решения определённых классов задач.

Место дисциплины в учебном плане: является вариативной дисциплиной, обязательной для изучения в цикле математических и естественно-научных дисциплин. Предыдущие компетенции — в объёме учебных дисциплин "Математика 1. Математический анализ", "Линейная алгебра", "Дискретная математика".

Формируемые компетенции:

владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);

умеет логически верно, аргументировано и ясно строить устную и письменную речь (ОК-2);

стремится к саморазвитию, повышению своей квалификации и мастерства (ОК-6);

использует основные законы естественно-научных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10).

В результате изучения дисциплины студент должен:

знать: основные понятия математической логики: формальной теории, исчисления; структуру исчислений высказываний и предикатов 1-го порядка; основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгорифмы Маркова), понятия вычислимости, разрешимости, перечислимости; основные неразрешимые массовые проблемы;

уметь: доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгорифмов для решения простых вычислительных задач;

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

Содержание дисциплины

Логика высказываний (пропозициональная логика). Высказывания и истинностные значения высказываний. Логические операции. Формулы логики высказываний (пропозициональные формулы). Истинностные функции. Тавтологии. Эквивалентность формул. Замена эквивалентным и двойственность. Дизъюнктивная и конъюнктивная нормальные формы. Классическое исчисление высказываний. Аксиомы и правила вывода. Вывод формул и вывод формул из гипотез. Теорема о дедукции. Теоремы полноты и непротиворечивости. Исчисление предикатов. Предикаты и кванторы. Предикатные формулы. Интерпретация предикатных формул. Выполнимость, истинность. Логическая общезначимость. Аксиомы и правила вывода исчисления предикатов 1-го порядка. Структура теории 1-го порядка. Нормальные алгорифмы и машины Тьюринга. Вычисление словарных функций нормальными алгорифмам и и машинами Тьюринга. Принцип нормализации и тезис Тьюринга. Универсальные алгоритмы. Теоремы сочетания. Разрешимость и перечислимость. Неразрешимые массовые проблемы.