Вопросы на экзамен
.docВопросы по курсу "Дискретная математика" для студентов групп АП
-
Дайте определение взаимно однозначного соответствия между двумя множествами, приведите примеры. Дайте определение счетного множества. Докажите счетность множеств всех целых и всех рациональных чисел.
-
Дайте определение счетного множества. Докажите счетность множеств всех слов в конечном алфавите и всех конечных подмножеств счетного множества.
-
Докажите, что всякое бесконечное множество содержит счетное подмножество, а также счетнасть объединения любых двух /или счетного семейства/ счетных множеств.
-
Дайте определение несчетного множества. Докажите, что множество всех бесконечных последовательностей нулей и единиц несчетно.
-
Дайте определение несчетного множества. Докажите несчетность множества всех подмножеств натурального ряда и множества всех бесконечных последовательностей натуральных чисел.
-
Объясните, что значит, что мощность одного множества превосходит мощность другого. Докажите, что мощность множества всех подмножеств любого множества имеет мощность большую, чем данное множество.
-
Дайте определение конечного автомата, приведите пример. Дайте определение множества, представимого /распознаваемого/ данным автоматом. Докажите, что существуют множества, не представимые никаким конечным автоматом.
-
Дайте определение регулярного множества /события/, приведите примеры. Докажите какие-либо тождества в алгебре регулярных событий. Сформулируйте основную теорему о связи регулярных событий с конечными автоматами.
-
Изложите алгоритм синтеза автомата, распознающего данное регулярное событие.
-
Дайте определение машины Тьюринга, приведите пример. Дайте определение функции, вычисляемой данной машиной Тьюринга. Постройте МТ, вычисляющую функцию f(n)=2n.
-
определение функции, универсальной для данного класса функций. Докажите, что класс функций обладает универсальной функцией тогда и только тогда, когда он непуст и не более чем счетен.
-
Изложите тезис Черча. Изложите аргументы, делающие его убедительным.
-
Докажите существование вычислимой функции, универсальной для класса всех вычислимых функций одного переменного.
-
Докажите, что универсальная вычислимая функция не может быть продолжена до всюду определенной вычислимой. Докажите, что ее область определения - перечислимое неразрешимое множество.
-
Дайте определение нормального алгорифма Маркова, приведите пример. Дайте определение функции, вычисляемой нормальным алгорифмом. Постройте нормальный алгорифм, вычисляющий функцию f(n)=2n.
-
. Дайте определение разрешимого множества, приведите примеры. Докажите теорему о свойствах замкнутости класса разрешимых множеств.
-
Дайте определение перечислимого множества, приведите примеры. Докажите теорему о свойствах замкнутости класса перечислимых множеств.
-
Дайте определения разрешимого и перечислимого множеств, приведите примеры. Докажите теорему о связи этих понятий.
-
Докажите, что множество перечислимо тогда и только тогда, когда оно есть область определения вычислимой функции. Докажите существование перечислимого неразрешимого множества.
-
Доказать теорему Райса.
-
Теорема Форда – Фалкерсона.
-
Алгоритм Форда – Фалкерсона.