«деревенский парикмахер» icon

«деревенский парикмахер»


Смотрите также:
Образовательный стандарт начального профессионального образования по профессии 100108...
2008 г. Комплект Учебно-программной документации по профессии «Парикмахер» профессии по ок...
Водной из рукописей поэмы «Кому на Руси жить хорошо» Некрасов изображает деревенский пожар...
Лицензия №399 от 27 декабря 2010г. Парикмахер-стилист 10 месяцев обучения...
И. А. Крылов (3-4 басни на выбор)...
И. А. Крылов (3-4 басни на выбор)...
И. А. Крылов (3-4 басни на выбор)...
И. А. Крылов (3-4 басни на выбор)...
И. А. Крылов (3-4 басни на выбор)...
Произведения Для самостоятельного чтения 5-11 классы...
Фролов А. А. "Педагогика А. С. Макаренко (наука о взаимодействии поколений)"...
Список литературы для самостоятельного чтения летом (5–11 классы)...



Загрузка...
скачать
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

(Вопросы к экзамену по курсу)

  1. Множества и классы. Антиномии (парадоксы). Антиномия всемогущества, парадокс «деревенский парикмахер». Антиномия Рассела. Класс разбиений множества. Пустое множество. Универсум. Мощность (кардинальное число, порядок) множества.

  2. Отношение. Кортеж. Бинарное отношение. Отношение принадлежности. Отношение включения. Подмножество, надмножество, собственное подмножество. Операции над множествами: объединение (дизъюнкция, сумма), пересечение (конъюнкция, произведение), разность, симметрическая разность, дополнение.

  3. Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область значений, образ (Im) соответствия. Всюду определенные и сюръективные соответствия. Образ (im) и прообраз (coim) элемента. Cоответствие как частично определенная многозначная функция. Матричное и графовое представление соответствия.

  4. Инволюция (обращение) соответствий. Объединение, пересечение, дополнение, произведение соответствий. Дифункциональное соответствие. Функциональные соответствия, их связь с графиками функций. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.

  5. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное соответствия. Отношение предпорядка, порядка, толерантности, эквивалентности. Фактормножество множества по отношению.

  6. Изоморфизм, изоморфное отображение. Автоморфизм. Гомоморфизм, ядро гомоморфизма, конгруэнция, факторалгебра универсальной алгебры. Эпиморфизм (сюръекция). Класс объектов (Ob), класс морфизмов (Mor) и категория. Эндоморфизм. Мономорфизм (инъекция). Биморфизм (биекция). Гомеоморфизм в топологии.

  7. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа. Основная теорема об абелевых группах. Группа симметрий фигуры. Симметрическая группа (группа подстановок), стабилизатор элемента, орбита элемента. Регулярная группа подстановок.

  8. Циклическая группа. Порядок элемента группы. Прямое произведение подгрупп. Теорема Лагранжа и ее следствия. Примарная группа, элементарная группа. Инвариантный элемент группы. Сопряженные элементы и подгруппы, трансформация и инвариантность относительно трансформации. Нормальный делитель (инвариантная подгруппа), центр группы. Фактор-группа. Теорема Силова и ее следствия.

  9. Кольцо. Аддитивная группа кольца. Нуль, делители нуля. Делители нуля и вычисления на ЭВМ. Ассоциативное кольцо, альтернативное кольцо, йорданово кольцо, кольцо Ли, коммутативное кольцо, область целостности. Квазитело. Дистрибутивное, ассоциативное, альтернативное квазитело. Тело. Теорема о кольце, являющемся телом. Теорема Веддербёрна. Поле (коммутативное тело). Поле Галуа. Иерархия систем с двумя бинарными операциями.

  10. Алгебра (операторное кольцо) над произвольным ассоциативным кольцом с единицей. Алгебра над полем (линейная алгебра, векторное пространство), ранг алгебры над полем (размерность векторного пространства). Подкольцо, подалгебра. Левый, правый, двусторонний идеал. Сравнимость по идеалу, классы вычетов по идеалу. Факторкольцо, факторалгебра. Теорема о гомоморфизмах. Простое кольцо.

  11. Поле, поле Галуа. Поле вычетов кольца по простому модулю, характеристика поля. Простое поле. Алгебраические (в том числе конечные) и трансцендентные расширения поля. Алгебраически замкнутое поле. Поле комплексных чисел. Основная теорема алгебры.

  12. Точная верхняя (sup) и точная нижняя (inf) грани подмножеств. Свойства рефлексивности, антирефлексивности, антисимметричности, транзитивности отношений. Отношение предпорядка, упорядоченности, строгой упорядоченности. Решетка (структура). Ðåшетка как частично упорядоченное множество и как универсальная алгебра. Тождества: идемпотентность, поглощение и другие. Диаграмма Хассе. Теорема об уникальности наибольшего и наименьшего элементов упорядоченного множества.

  13. Тождества (законы), определяющие операции дизъюнкции, конъюнкции и отрицания: идемпотентностей, коммутативностей, ассоциативностей, дистрибутивностей, двойного отрицания, де-Моргана, склеивания, поглощения, нуля (лжи) и единицы (истины). Закон противоречия, закон исключенного третьего. Теорема Стоуна.

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

  15. Формула. Глубина формулы. Суперпозиция функций. Таблицы истинности и таблицы Кэли. Формы записи операций (функций) — инфиксная, префиксная (прямая польская запись), постфиксная (обратная польская запись).

  16. Условия определения аксиоматической (формальной) теории. Выражения, формулы, аксиомы, правила вывода формальной теории. Непосредственное следствие формул по правилу вывода; вывод формулы; теорема формальной теории. Разрешимая и неразрешимая формулы.

  17. Исчисление высказываний как аксиоматическая теория в дизъюнктивном базисе Буля. Связки, пропозициональные буквы. Формула и аксиомы исчисления высказываний. Правила вывода: правило подстановки, правило заключения (modus ponens).

  18. ^ Некоторые булевы алгебры: дизъюнктивная алгебра, алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина.

  19. Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Конечнозначная функция Вебба и конечнозначная алгебра Вебба. Конечнозначные алгебры Поста, Россера-Тьюкетта.

  20. Алгебраическая система (алгебра). Носитель, основное множество алгебры. Сигнатура алгебры: множество основных (главных) операций и множество основных (главных) отношений. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры). Свойства сигнатуры: полнота, независимость, непротиворечивость. Сведение k-значных логик к двузначным.

  21. Предикат: n-местный (n=0, n>0), тождественно истинный, тождественно ложный, выполнимый. Область истинности предиката. Связь между n-местными предикатами и n-местными отношениями. Квантор всеобщности и квантор существования. Предикатная переменная.

  22. Исчисление предикатов. Четыре группы символов формализованного языка логики предикатов: предикатные переменные, предметные переменные, логические символы, вспомогательные символы. Пропозициональные переменные, m-местные переменные. Элементарная формула. Правила построения предикатных формул из элементарных.

  23. Формула, подформула в исчислении предикатов. Область действия квантора. Связанное и свободное вхождение переменной в формулу. Интерпретация формулы на непустом множестве. Истинность формулы в данной интерпретации. Общезначимая формула, тождественно истинная формула (тавтология). Цель логики. Исчисление предикатов как описание класса всех общезначимых формул.

  24. Исчисление высказываний как основа (схема) исчисления предикатов. Три правила вывода исчисления предикатов (modus ponens, -правило и -правило). Вывод формулы в исчислении предикатов. Теорема Геделя о полноте. Состав и использование дедуктивного аппарата исчисления предикатов.

  25. Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи. Блочный двоичный (m,n)-код и функции, определяющие схему кодирования и схему декодирования. Функция ошибок. Коды с обнаружением ошибок и коды с исправлением ошибок.

  26. Аксиомы расстояний и расстояние Хемминга. Вес слова, вес поразрядной суммы. Теорема о наименьшем расстоянии между кодовыми словами, необходимом для обнаружения ошибок; теорема о наименьшем расстоянии между кодовыми словами, необходимом для исправления ошибок.

  27. ^ Преимущества матричного кодирования. Порождающая матрица кода. Требование к матрице, достаточное для различия кодов разных исходных слов.

  28. Групповые коды. Матричные коды как групповые. Наименьшее расстояние между кодовыми словами группового кода. Схема декодирования, при которой вероятность искажения кода минимальна. Лидер смежного класса коммутативной группы всех слов фиксированной длины. Табличный метод кодирования с учетом лидеров.

  29. ^ Групповые коды Хемминга, исправляющие однократную ошибку. Схема кодирования и схема декодирования Хемминга.

  30. Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина. Укладка графа. Плоский граф.

  31. Матрица смежности, матрица инцидентности. Задание графа списками. Изоморфные графы. Подграфы. Маршрут, цепь, простая цепь, (простой) цикл. Компонента связности. Дерево. Графы k-связные (k-реберно-связные).

  32. Обход графа. Длина маршрута, расстояние между вершинами. Одноместные операции: удаление или добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра. Двуместные операции: соединение, сложение, различные виды умножений и др.средства для анализа и синтеза графов с заданными свойствами.

  33. Эйлеров путь в графе. Задача о кенигсбергских мостах, головоломки. Эйлеров цикл. Теорема о существовании эйлерова пути. Теорема об эйлеровом пути в связном графе без вершин нечетной степени. Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма. Прикладные задачи теории графов.

  34. Критерий существования графа с заданными степенями вершин. Критерий существования обхода всех ребер графа. Необходимое и достаточное условие вложения графа в плоскость. Теорема о наименьшем числе цветов, достаточном для раскраски графа. Теорема о группе автоморфизмов (симметрий) графа. Случайные графы.

  35. Гамильтонов путь в графе, гамильтонов цикл. NP-полные задачи. Алгоритм с возвратом для поиска гамильтонова пути. Рекурсивный вариант алгоритма с возвратом для поиска гамильтонова пути. Алгоритм нахождения всех гамильтоновых циклов в графе.

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

  37. ^ Алгоритм Форда-Беллмана нахождения расстояния от источника до всех вершин. Доказательство правильности алгоритма. Оценка временной сложности алгоритма.

  38. Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Оценка сложности алгоритма и его модификации с использованием таблицы указателей.

  39. Лемма о перенумерации вершин. Алгоритм нумерации вершин бесконтурного графа. Утверждение о вершине, в которую не заходит ни одна дуга, использование стека для накапливания таких вершин. Сравнение скорости роста двух функций (принятые обозначения) и оценка сложности алгоритма.

  40. Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе (с предварительной перенумерацией вершин). Применение алгоритмов в методах управления выполнением проекта (сети PERT — Project Evaluation and Review Technique или CPM — Critical Path Method).

  41. Нахождение кратчайших путей между всеми парами вершин в ориетированном графе — транзитивное замыкание отношенияю. Модификация алгоритма Уоршалла. Алгоритм вычисления расстояний между всеми парами вершин — метод Флойда.

  42. ^ Графы и ориентированные графы: аналогии и отличия. Подграфы, ориентированные подграфы и связность.

  43. Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики. Теорема о структуре (теорема Харари о балансе). Законы передачи импульса во взвешенно/знаковых моделях на орграфах. Контуры положительной и отрицательной обратной связи и устойчивость/изменчивость моделей на орграфах.

  44. Конечный автомат как математическая модель устройства в конечной памятью и как управляющая система. Входной и выходной каналы, входной и выходной алфавит, тактовые моменты, состояния конечного автомата, алфавит состояний; выходная и переходная функции.

  45. Абстрактный и структурный конечные автоматы. Бесконечные автоматы. Частичные, недетерминированные, вероятностные автоматы. Автоматы со специфическими множествами входных объектов, автоматы с переменной структурой. Самонастраивающиеся, обратимые автоматы. Автомат как математическая модель преобразователя дискретной информации. Ñâÿçü òåîðèè àâòîìàòîâ с теорией алгоритмов, с математической лингвистикой, с формальными системами, аксиоматическими теориями и другими математическими теориями.

  46. Задачи теории автоматов: задача анализа, задача синтеза, задача полноты, задача эквивалентных преобразований. Поведение автомата. Задача минимизации числа состояний автомата. Моделирование поведения автоматов одного класса автоматами другого класса. Эксперименты с автоматами.

  47. Способы описания конечных автоматов: перечислительный (алфавиты и предписания для функций выхода и перехода); диаграмма состояний (помеченный ориентированный граф); таблица состояний. Преимущества и недостатки каждого способа, связь между ними. Примеры.

  48. Машина Тьюринга. Входной/выходной алфавит, конечное множество внутренних состояний, выходная, переходная и управляющая функции. Основные различия между машиной Тьюринга и конечным автоматом. Способы задания машины Тьюринга: перечислительный и в обозначениях Тьюринга. Теорема о построении машины Тьюринга, соответствующей заданному конечному автомату.

  49. Формальные грамматики. Место теории формальных грамматик в математической лингвистике. Порождающая грамматика. Основной и вспомогательный алфавит (словарь). Терминальные (основные) и нетерминальные (вспомогательные) символы. Начальный символ; конечный набор правил вывода и их вид.

  50. Вывод в порождающей формальной грамматике. Слова языка (основные символы); имена классов слов и словосочетаний (вспомогательные символы); имя класса словосочетаний, являющихся предложениями (начальный символ = символ предложения). Выводимая цепочка. Предложение. Язык, порожденный грамматикой.

  51. Основные классы порождающих грамматик. Грамматики составляющих (грамматики непосредственно составляющих — НС-грамматики, контекстные грамматики). Бесконтекстные грамматики (контекстно-свободные грамматики — КС-грамматики. Автоматная грамматика (грамматика с конечным числом состояний) как частный случай бесконтекстной грамматики. НС-языки (контекстные языки) и КС-языки (бесконтекстные языки, автоматные языки).

  52. ^ Дерево вывода в грамматике составляющих. Доминационные грамматики. Трансформационные грамматики.

  53. Алгоритм. Уточнение понятия алгоритма и семь его параметров. Область применимости алгоритма. Вычислимая функция. Разрешимое множество. Перечислимое множество. Семь основных базовых результатов теории алгоритмов.

  54. Алгоритм с неразрешимой областью применимости. Основание алгоритмической теории множеств. Дескриптивная (качественная) и метрическая (количественная) теории алгоритмов. Результат Черча о неразрешимости проблемы разрешения для множества всех истинных предложений логики предикатов.




Скачать 104,05 Kb.
оставить комментарий
Дата21.09.2011
Размер104,05 Kb.
ТипВопросы к экзамену, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх