Что такое простой граф? Что такое матрица смежности простого графа? Запишите матрицу смежности простого графа
жүктеу/скачать 6.13 Mb.
|
| Что такое простой граф? Что такое матрица смежности простого графа? Запишите матрицу смежности простого графа . . . Что такое матрица Кирхгофа простого графа? Запишите матрицу Кирхгофа простого графа . . . Что такое матрица инцидентности простого графа? Запишите матрицу инцидентности простого графа . . . Что такое ориентированный граф? Что такое матрица инцидентности ориентированного графа? Запишите матрицу инцидентности . . Что такое остовное дерево связного графа? Сколько ребер в остовном дереве . . Сколько остовных деревьев в полном графе . . . ? Что такое ранг простого графа? Чему равен ранг . . . ? Что такое дерево? Сколько ребер, циклов и компонент связности у дерева . . .? Что такое связный граф? Что такое компонента связности простого графа? Сколько компонент связности может иметь граф . . . ? Что такое матрица достижимости ориентированного графа? Как она связана с матрицей смежности этого графа? Запишите матрицы смежности и достижимости для . . . Что такое матрица стоимости путей ориентированного взвешенного графа? Как она связана с взвешенной матрицей смежности этого графа? Запишите матрицы взвешенной смежности и стоимости путей для ориентированного полного графа . . . С помощью матриц смежности, используя различные алгебры, можно определить наличие путей различной длины между произвольными вершинами, количество таких путей и перечисление таких путей Что такое степень вершины простого графа? Чему равна сумма степеней вершин простого графа? Что такое степень вершины простого графа? Чему равна сумма степеней вершин простого графа? Что такое подграф простого графа? Что такое остовный подграф? Приведите пример остовного и не остовного подграфов . . . Что такое изоморфизм простых графов? Перечислите простые попарно неизоморфные графы . . . Что такое дерево? Что такое компонента связности? Сколько ребер имеет ацикличный граф . . . ? Что такое слово, подслово, язык над конечным алфавитом? Перечислите все подслова в слове . . . Что такое язык над конечным алфавитом? Что такое атомарные языки? Перечислите атомарные языки. . . Что такое регулярные операции над языками? Найдите произведение языков . . . Найдите сумму языков . . . Что такое регулярный язык и регулярное выражение? Является ли регулярным язык . . . ? Если да, запишите для него регулярное выражение. Сформулируйте лемму о разрастании для регулярных языков. Проверьте, выполняется ли эта лемма для языка . . . (если да, то укажите подходящую константу). Сформулируйте лемму о разрастании для регулярных языков. Покажите, что язык . . . не является регулярным. Что такое регулярный язык и регулярное выражение? Опишите все слова, входящие в язык . . . ? Входит ли в этот язык слово . . . ? Что такое итерация языка? Найдите итерацию языка . . . над алфавитом A = {a, b, c} (опишите все входящие в язык L∗ слова). Что такое замкнутое идемпотентное полукольцо? Является ли замкнутым полукольцо всех языков над фиксированным алфавитом (в качестве сложения берется объединение языков, а в качестве умножения — произведение языков)? Выпишете соотношения, которые нужно проверить для доказательства замкнутости. (как-то аналогично сделать) Что такое замкнутое идемпотентное полукольцо? Является ли замкнутым полукольцо всех регулярных языков над фиксированным алфавитом (в качестве сложения берется объединение языков, а в качестве умножения — произведение языков)? Выпишете соотношения, которые нужно проверить для доказательства замкнутости. (как-то аналогично сделать) Что такое автомат-распознаватель? Что такое язык, порожденный автоматом-распознавателем? Постройте автомат, язык которого равен . . . Сформулируйте теорему Клини. Объясните, как найти язык автомата с помощью взвешенной матрицы смежности его графа. Найти язык автомата, взвешенная матрица смежности которого имеет вид . . . По взвешенной матрице смежности построить граф автомата, из него найти язык (30) Что такое конечный детерминированный автомат с выходом? Для автомата с выходом с алфавитами A = Z = {0, 1}, состояниями {q1, q2, q3, q4} и таблицей состояний . . . вычислите значение расширенной функции выхода g5(01100, q2). (31) Какие состояния конечного детерминированного автомата с выходом называются k-эквивалентными? Эквивалентными? Выяснить, являются ли эквивалентными состояния q3 и q5 автомата с выходом с алфавитами A = Z = {0, 1}, состояниями {q1, q2, q3, q4, q5} и таблицей состояний . . . Если нет, то для каких k они являются k-эквивалентными? (32) Что такое фактор-автомат? Запишите его функции выхода и перехода. Для автомата с выходом с алфавитами A = Z = {0, 1}, состояниями {q1, q2, q3, q4} и таблицей состояний . . . построить фактор автомат. (33) Что такое покрытия конечных детерминированных автоматов с выходом? Для автомата с выходом с алфавитами A = Z = {0, 1}, состояниями {q1, q2, q3, q4} и таблицей состояний . . . опишите его покрытие минимальным автоматом. (34) Что такое морфизмы конечных детерминированных автоматов с выходом? Для автомата с выходом с алфавитами A = Z = {0, 1}, состояниями {q1, q2, q3, q4} и таблицей состояний . . . опишите его морфизм на соответствующий фактор-автомат жүктеу/скачать 6.13 Mb. Достарыңызбен бөлісу:
|