Высшая математика.фип(3/3)_БАК_н/с

Скачать тест — (Высшая математика.фип(3_3)_БАК_н_с_c800aeb3.pdf)

Из скольких элементов состоит множество {1, 2, {3, 4}}?
Говорят, что множество A является … множества B, если каждый элемент A принадлежит B.
Обозначение ∅ используется для … множества.
Какие из этих множеств являются бесконечными?
Установите соответствие между уравнениями на множествах и выводами,
Множество, состоящее из всех элементов, принадлежащих A и B, называется … этих двух множеств.
Разность множеств A и B (A B) состоит из элементов,
Выберите все утверждения, верные для любых множеств
Множество, состоящее из пар (a, b), где a∈A, b∈B, называется декартовым … множеств A и B.
Диаграмма Венна используется для
Из скольких элементов состоит множество {1, {2, {3, 4}}}?
Говорят, что множество A содержится в множестве B, если каждый элемент A … B.
Обозначение ∅ используется для множества, состоящего из … элементов.
Какие из этих множеств являются конечными?
Установите соответствие между уравнениями на множествах и выводами,
Множество, состоящее из всех элементов, принадлежащих A или B, называется … этих двух множеств.
Симметрическая разность множеств A и B (A △ B) состоит из
Выберите все утверждения, верные для любых множеств
Множество, состоящее из пар (a, b), где a∈A, b∈B, называется … произведением множеств A и B.
В диаграмме Венна
Какое из следующих множеств имеет мощность, равную 5?
Мощность множества — это количество … в множестве.
Мощность пустого множества равна ….
Какие из следующих утверждений верны?
Установите соответствие между типами множеств и их мощностями:
Множества A и B равномощны, если существует … между их элементами.
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Теорема Кантора утверждает, что множество всех подмножеств множества A имеет … мощность, чем само множество A.
Какой метод используется для доказательства равномощности двух бесконечных множеств?
Какое из следующих множеств имеет мощность, равную 3?
Мощность множества определяется числом … в нем.
Мощность множества, содержащего только пустое множество, равна ….
Какие из следующих утверждений верны?
Установите соответствие между типами множеств и их мощностями:
Два множества называются равномощными, если между их элементами можно построить ….
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Теорема … гласит, что мощность множества всех подмножеств любого множества A больше мощности самого множества A.
Для доказательства того, что два бесконечных множества равномощны, используется метод…
На рынке продавались платья: 45 пышных, 50 с цветочками, 50 белого цвета, 20 белого цвета с цветочками, 20 пышных белого цвета, 25 пышных с цветочками, 15 пышных белого цвета с цветочками, 5 зеленых вытянутых, никогда не цветущих. Сколько платьев только белого цвета продавалось на рынке?
Какое из следующих утверждений верно для отношения эквивалентности?
Отношение «быть не меньше» (≥) на множестве действительных чисел является примером отношения … порядка
Отношение R на множестве A называется …, если для любых a, b из A, таких что aRb и bRa, следует, что a = b.
Какие из следующих утверждений верны для всех вполне упорядоченных множеств?
Установите соответствие между типами отношений и их свойствами:
Для доказательства утверждений, занумерованных натуральными числами, может использоваться принцип математической … .
Какое из следующих утверждений верно для фундированных множеств?
Выберите все верные утверждения:
Бинарное отношение, которое является рефлексивным, симметричным и транзитивным, называется отношением …
Какое из этих свойств не присуще отношению линейного порядка?
Какое из следующих утверждений верно для отношения эквивалентности?
Отношение «быть строго больше» (>) на множестве действительных чисел является примером отношения … порядка
Отношение R на множестве A называется …, если для любого a из A, aRa.
Какие из следующих утверждений верны для всех частично упорядоченных множеств?
Установите соответствие между типами отношений и их свойствами:
Принцип транфинитной математической индукции применим к утверждениям, занумерованным элементами … упорядоченного множества
Какое из следующих утверждений верно для всех вполне упорядоченных множеств?
Выберите все верные утверждения:
Бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным, называется отношением … порядка
Какое из этих свойств не присуще отношению эквивалентности?
Найдите сумму с помощью математической индукции: 1⋅1!+2⋅2!+…+2023⋅2023!+2024⋅2024!
Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует … элемент.
Теорема Цермело утверждает, что любое множество может быть вполне ….
Какие из следующих утверждений верны относительно аксиомы выбора?
Установите соответствие между утверждениями и их следствиями:
… Гамеля — это максимальное линейно независимое подмножество векторного пространства
Выберите все верные утверждения:
Аксиома выбора необходима для доказательства:
Аксиома выбора необходима для доказательства существования:
Лемма Цорна применима к:
Теорема Цермело утверждает, что:
Какие из следующих утверждений верно относительно леммы Цорна?
Для доказательства теоремы Цермело может быть использована лемма …
Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует максимальный … элемент.
Базис Гамеля — это максимальное линейно … независимое подмножество векторного пространства
Может ли базис Гамеля содержать векторы, которые не являются ортогональными?
Какое свойство базиса Гамеля делает его особенно полезным для линейной алгебры?
Какие основные свойства обладает множество, удовлетворяющее условиям леммы Цорна?
Компактные … часто рассматриваются в контексте леммы Цорна
В компании работает несколько программистов, умеющих программировать на C++, Python и Go. С++ знают 25 человек, Python – 19, Go – 24. С++ и Go знают 10 человек, С++ и Python – 6, Python и Go – 3. Все три языка знает 1 человек. Сколько программистов работают в компании?
Ординалы — это:
Какое из следующих утверждений о свойствах операций над мощностями верно?
Арифметика ординалов включает операции:
Какой ординал является первым предельным ординалом?
Установите соответствие между понятиями и их определениями:
Индуктивные определения используются для:
Выберите все верные утверждения:
Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью теоремы …
Какой метод может быть использован для доказательства свойств ординалов?
Ординал ω + 1 обозначает:
Какое из следующих утверждений о свойствах операций над ординалами верно?
Какой ординал следует непосредственно за 2ω?
Свойство «быть больше» для ординалов является:
Если X и Y — два вполне упорядоченных множества, то либо они изоморфны друг другу, либо ровно одно из них … начальному отрезку другого.
Выберите все верные утверждения:
Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью леммы …
Понятие «предельный ординал» используется для описания ординалов, которые:
Трансфинитная … может быть использована для алгоритмического построения множеств с любым порядковым типом.
В школе учится 70 человек. Среди них 27 человек занимаются танцами, 32 человека занимаются рукоделием, 22 занимаются спортом. Танцами занимается 10 человек, занимающихся рукоделием, рукоделием занимаются 6 спортсменов, а танцами 8 спортсменов, и танцами и рукоделием занимаются 3 спортсмена. Сколько человек не занимаются ничем?
Свойство «быть меньше» для ординалов является:
Какие из следующих высказываний являются тавтологией?
Высказывание «Если сегодня идет дождь, то я возьму зонт» является примером логической операции …
Операция, обозначаемая символом ¬, называется …
Какие из следующих пар высказываний являются эквивалентными?
Установите соответствие между логическими операциями и их обозначениями:
Логическая операция, подразумевающая логическое ИЛИ, называется …
Выберите все высказывания, которые всегда являются ложными:
Выберите все верные утверждения относительно импликации:
Операция, обозначаемая символом ↔, называется …
В логическом выражении (p → q) ∧ (¬p ∨ q), если p истинно и q ложно, то всё выражение …
Какое из следующих высказываний всегда ложно?
Высказывание «Если я поеду на работу на автобусе, то опоздаю» является примером логической операции …
Операция, обозначаемая символом ∧, называется …
Какие из следующих пар высказываний являются эквивалентными?
Установите соответствие между логическими операциями и их обозначениями:
Логическая операция, имеющая смысл ЕСЛИ И ТОЛЬКО ЕСЛИ, называется …
Выберите все высказывания, которые являются тавтологиями:
Выберите все верные утверждения относительно дизъюнкции:
Высказывание, истинное при любых значениях переменных, называется …
В логическом выражении (p ∧ q) ∨ (p ∧ ¬q), если p истинно и q ложно, то всё выражение …
В магазинной краже подозреваются четыре человека – A, В, С и D. Известно, что: Если A совершил кражу, то и В совершил кражу. Если В совершил кражу, то и С совершил кражу или А не совершал. Если D не совершал кражу, то A совершил, а С не совершал. Если D совершил кражу, то и A совершил кражу. Кто из подозреваемых совершил магазинную кражу?
Какое из следующих утверждений верно для языков первого порядка?
Квантор … обозначается символом ∀ и означает, что утверждение верно для всех элементов.
Квантор … обозначается символом ∃ и означает, что существует хотя бы один элемент, для которого верно утверждение.
Какое из следующих утверждений верно для интерпретаций в языках первого порядка?
Установите соответствие между элементами языка первого порядка и их ролями:
Формула ∀x x > 0 в контексте действительных чисел будет истинной для … чисел
Выберите все верные утверждения о формулах в языках первого порядка:
Выберите все верные утверждения о арифметических предикатах:
… в языке первого порядка может быть переменной, константой или функциональным символом от переменных.
В языках первого порядка, формула ∀x (P(x) → Q(x)) означает, что
Какое из следующих утверждений верно для формул в языках первого порядка?
Квантор существования в языках первого порядка обозначается символом … и используется для указания, что существует хотя бы один объект, удовлетворяющий условию.
Квантор всеобщности в языках первого порядка обозначается символом … и используется для указания, что утверждение верно для всех объектов домена.
Какие из следующих утверждений верны для термов в языках первого порядка?
Установите соответствие между элементами языка первого порядка и их ролями:
Формула ∀x x < 0 в контексте действительных чисел будет истинной для … чисел
Выберите все верные утверждения о предикатах в языках первого порядка:
Выберите все верные утверждения о функциональных символах в языках первого порядка:
… обладает носителем и значениями для символов предикатов и функций.
В языках первого порядка, формула ∃x (P(x) ∧ Q(x)) означает, что
Три подразделения А, В, С торговой фирмы стремились получить по итогам года максимальную прибыль. Экономисты высказали следующие предположения: Если А получит максимальную прибыль, то максимальную прибыль получат В и С. А и С получат или не получат максимальную прибыль одновременно. Необходимым условием получения максимальной прибыли подразделением С является получение максимальной прибыли подразделением В. По завершении года оказалось, что одно из трех предположений ложно, а остальные два истинны. Кто получил максимальную прибыль?
Какое из следующих утверждений верно для вычислимых функций?
Множество называется перечислимым, если его элементы можно вывести с помощью …
Множество называется …, если существует алгоритм, который для любого элемента может определить, принадлежит ли он этому множеству
Какие из следующих множеств являются перечислимыми?
Установите соответствие между понятиями и их определениями:
Теорема Поста утверждает, что если множество и его дополнение … , то это множество разрешимо.
Выберите все верные утверждения:
Какое из следующих множеств является разрешимым?
Какое из следующих утверждений верно для перечислимых множеств?
Множество называется …, если существует алгоритм, который по очереди выдает все его элементы и только их
Вычислимая функция — это функция, для которой существует … , вычисляющий её значение для любого входа.
Какие из следующих множеств являются разрешимыми?
Установите соответствие между понятиями и их определениями:
Теорема … утверждает, что множество и его дополнение являются перечислимыми, если и только если множество разрешимо
Выберите все верные утверждения:
Алгоритмом называется программа, написанная на … Тьюринга
Кто из этих исследователей занимался классической теорией алгоритмов?
Классическая теория алгоритмов описывает так называемые … функции.
Функция называется вычислимой, если существует …, который ее вычисляет
Утверждение “Неразрешимость проблемы остановки эквивалентна существованию перечислимого множества с неперечислимым дополнением” является следствием из теоремы
Рома, Олег и Саша нашли при раскопках вазу. Рассматривая удивительную находку, каждый высказал по два предположения. Это греческая ваза и изготовлена в V веке. Это финикийская ваза и изготовлена в III веке. Это не греческая ваза и изготовлена в IV веке. Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Когда была изготовлена ваза и где?
Проблема остановки программы заключается в вопросе:
Тьюринг доказал, что проблема остановки:
Проблема остановки демонстрирует, что:
Примером универсальной функции в реальном языке программирования является его …
Установите соответствие между понятиями и их описаниями:
Существует перечислимое множество с неперечислимым …
Выберите все верные утверждения:
Какой метод используется для доказательства неразрешимости проблемы остановки?
Установите соответствие между понятиями и их определениями:
Проблема остановки иллюстрирует, что:
Проблема остановки исследует вопрос:
Основной вывод из проблемы остановки состоит в том, что:
Установите соответствие между понятиями и их описаниями:
Существует … неразрешимое множество.
Примером … функции в реальном языке программирования является его интерпретатор.
Проблема остановки важна потому, что она:
Выберите все верные утверждения:
Существует … функция, принимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения.
При поломке ноутбука отец сказал «Память не может быть неисправной». Его сын предположил, что сломался процессор, а винчестер исправен. Мастер в ремонтном сервисе сказал, что с процессором все в порядке, а память неисправна. Оказалось, что двое из них сказали все верно, а третий – все неверно. Что сломалось в ноутбуке?
Какое из следующих чисел является простым?
Наибольший общий делитель (НОД) чисел 36 и 48 равен…
Минимальное натуральное число, которое делится на каждое из чисел 2, 3 и 5, это…
Какие из следующих утверждений верны?
Установите соответствие между понятиями и их определениями:
Деление с остатком числа 17 на 5 дает в остатке…
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Отношение «делится на» является примером отношения:
Для выполнения условия «остаток строго меньше делителя» в случае деления многочленов, сравниваются их …
Какое из следующих чисел является составным?
Наименьшее общее кратное (НОК) чисел 6 и 8 равно…
… числа — это числа, которые имеют ровно два различных натуральных делителя: единицу и само себя
Какие из следующих утверждений верны?
Установите соответствие между понятиями и их определениями:
Деление с остатком числа 23 на 4 дает в остатке…
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Найдите количество чисел от 1 до 2000, которые не делятся ни на 4, ни на 5.
Какой алгоритм используется для нахождения наибольшего общего делителя (НОД) двух чисел?
Основная теорема арифметики утверждает, что каждое натуральное число, большее 1, можно представить в виде произведения простых чисел, причем такое представление …, с точностью до порядка следования множителей.
Алгоритм Евклида основан на использовании деления с …
Какое из следующих утверждений верно для любых целых чисел a и b, где b ≠ 0?
Для чисел 1920 и 1080 НОД равен …
Какие из следующих утверждений верны в контексте основной теоремы арифметики?
Выберите все верные утверждения относительно алгоритма Евклида:
Лемма о разбиении единицы утверждает, что для любых … чисел a и b существуют такие целые числа x и y, что ax + by = 1
Диофантово уравнение ax + by = c имеет решение в целых числах, если и только если …
Какой алгоритм позволяет найти наибольший общий делитель двух натуральных чисел?
Основная теорема арифметики утверждает, что каждое натуральное число, большее 1, можно представить в виде произведения … чисел, причем такое представление единственно, с точностью до порядка следования множителей.
Принцип работы алгоритма Евклида основан на свойстве, что НОД(a, b) = НОД(b, r), где r обозначает … от деления a на b.
Какое из следующих утверждений верно для алгоритма Евклида?
Установите соответствие между понятиями и их определениями:
Наибольший общий делитель чисел 2560 и 1440, равен …
Выберите все верные утверждения о алгоритме Евклида:
Для каких значений c диофантово уравнение ax + by = c имеет решение?
Найдите наибольший общий делитель (НОД) для чисел 462 и 1071.
Установите соответствие между утверждениями и их значением в контексте алгоритма Евклида и основной теоремы арифметики:
Какой остаток получится при делении числа 15 на 4?
Если a ≡ b (mod m), то числа a и b имеют одинаковый остаток при делении на m. Это утверждение является определением сравнения по … m
Отношение «сравнимы по модулю n» является примером отношения:
Выберите все верные утверждения относительно арифметики остатков:
Установите соответствие между выражениями и их значениями по модулю 10:
Малая теорема Ферма гласит, что если p — простое число и a не делится на p, то ap-1 ≡ … (mod p).
Выберете все свойства, верные для отношения «сравнимы по модулю n»:
Выберите все верные утверждения, связанные с малой теоремой Ферма:
Какой остаток получится при делении числа 18 на 5?
Если a ≡ b (mod m), то числа a и b имеют одинаковый … при делении на m. Это утверждение является определением сравнения по модулю m
Выберите все верные утверждения относительно арифметики остатков:
Установите соответствие между выражениями и их значениями по модулю 10:
Малая теорема … утверждает, что для любого целого числа a и простого числа p, если a не делится на p, то ap-1 ≡ 1 (mod p).
a … b — остаток при делении а на b
Z/KZ называется … по модулю к
Чем малая теорема Ферма отличается от великой теоремы Ферма?
Какие приложения имеет малая теорема Ферма в криптографии?
Рассмотрим последовательность чисел: 3, 10, 17, 24, 31, …, где каждый последующий член больше предыдущего на 7. Найдите остаток от деления 1000-го члена этой последовательности на 13.
Какой метод является основой для системы шифрования RSA?
В криптографии функция, сложная для обращения без знания секретного ключа, называется …
Схема … позволяет двум сторонам безопасно обменяться секретным ключом
Какое утверждение верно для схемы шифрования RSA?
Установите соответствие между криптографическими понятиями и их описаниями:
Принцип шифрования в алгоритме … основан на применении малой теоремы Ферма.
Какой алгоритм является основой для схемы Диффи–Хеллмана?
Выберите все верные утверждения о криптографии:
… в криптографии нужны для преобразовании входных данных в уникальный набор символов фиксированной длины
Какое утверждение неверно для схемы Диффи–Хеллмана?
Какой алгоритм не используется непосредственно в криптографии?
В криптографии, метод «открытого ключа» относится к … шифрованию
Алгоритм шифрования … основывается на сложности задачи разложения больших чисел на простые множители
Установите соответствие между криптографическими алгоритмами и их характеристиками:
Малая теорема Ферма находит применение в криптографии для генерации больших … чисел
Какой метод является основой для генерации ключей в схеме Диффи–Хеллмана?
Принцип шифрования в алгоритме RSA основан на применении малой теоремы ….
Как расшифровывается аббревиатура RSA?
Пусть n — натуральное число, при делении на 5 дает остаток 3, а при делении на 7 дает остаток 4. Какой остаток дает число n при делении на 35?
Какой граф называется полным?
Что такое степень вершины в графе?
Как называется граф, в котором между любыми двумя вершинами существует путь?
Какие из следующих утверждений верны для деревьев?
Установите соответствие между типами графов и их характеристиками:
Что такое петля в теории графов?
Выберите все верные утверждения о свойствах графов:
Как называется путь в графе, который начинается и заканчивается в одной и той же вершине?
Какое из следующих утверждений верно для ориентированных графов?
Установите соответствие между понятиями и их определениями:
Какой граф называется ациклическим?
Что такое изолированная вершина в графе?
Как называется граф, в котором между любыми двумя вершинами существует не более одного пути?
Какие из следующих утверждений верны для ориентированных графов?
Что такое мультиграф?
Выберите все верные утверждения о свойствах графов:
Как называется граф, в котором возможно наличие петель и кратных рёбер?
Какое из следующих утверждений верно для деревьев?
Установите соответствие между понятиями и их определениями:
В графе G с 6 вершинами каждая вершина соединена с каждой другой вершиной. Сколько ребер содержит этот граф?
Установите соответствие между типами графов и их характеристиками:
Какой алгоритм используется для обхода всех вершин ориентированного графа?
При поиске в глубину, если граф содержит циклы, какое утверждение верно?
Какой структурой данных обычно пользуются при реализации алгоритма поиска в глубину?
Какой из следующих вариантов лучше всего описывает принцип работы алгоритма поиска в глубину?
Установите соответствие между типами ребер в ориентированном графе и их характеристиками при поиске в глубину:
Какое из следующих утверждений верно для алгоритма поиска в глубину?
… в графе называется путь, начинающийся и заканчивающийся в одной и той же вершине.
Выберите все верные утверждения о поиске в глубину:
Установите соответствие между этапами алгоритма поиска в глубину и их описанием:
Какой метод используется для предотвращения зацикливания алгоритма поиска в глубину в присутствии циклов в графе?
Какой алгоритм позволяет определить, есть ли в ориентированном графе цикл?
Какая структура данных не используется при реализации алгоритма поиска в глубину?
Какое из следующих утверждений неверно относительно алгоритма поиска в глубину?
Выберите все верные утверждения о поиске в глубину в ориентированных графах:
Какой метод используется для определения порядка обработки вершин в алгоритме поиска в глубину?
Какой аспект алгоритма поиска в глубину позволяет определить компоненты сильной связности в ориентированном графе?
Рассмотрим граф G с 6 вершинами и 7 ребрами. Какое минимальное количество ребер должно быть удалено из графа G, чтобы он не содержал циклов?
Какой алгоритм используется для нахождения компонент сильной связности в ориентированном графе?
Компоненты сильной … в графе – это подграфы, в которых каждая вершина достижима из другой вершину посредством направленного пути.
Установите соответствие между алгоритмами и их особенностями:
Граф, вершинами которого являются компоненты связности другого графа, называется его …
В графе, представленном матрицей смежности, элемент aij равен 0, если между вершинами i и j …
Выберите все верные утверждения относительно алгоритма поиска в ширину:
Какой алгоритм используется для нахождения кратчайшего пути от одной вершины до всех остальных в взвешенном графе без отрицательных весов рёбер?
Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в …, называется очередью
Алгоритм … можно интерпретировать как модифицированный алгоритм поиска в ширину, где взешенное ребро заменяется на путь из нескольких ребер.
Какой алгоритм не используется для нахождения компонент сильной связности?
… сильной связности в графе – это подмножества вершин, в которых каждая вершина достижима из другой вершину посредством направленного пути.
В графе, представленном матрицей смежности, элемент aij равен 1, если между вершинами i и j …
Выберите все верные утверждения о компонентах сильной связности:
Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в ширину, называется …
Алгоритм Дейкстры можно интерпретировать как модифицированный алгоритм поиска в …, где взешенное ребро заменяется на путь из нескольких ребер.
Рассмотрим граф G с 15 вершинами и 8 ребрами. Какое максимальное количество ребер может быть добавлено в граф G, чтобы он не содержал циклов?
Из скольких элементов состоит множество {1, 2, {3, 4}}?
Говорят, что множество A является … множества B, если каждый элемент A принадлежит B.
Обозначение ∅ используется для … множества.
Какие из этих множеств являются бесконечными?
Установите соответствие между уравнениями на множествах и выводами,
Множество, состоящее из всех элементов, принадлежащих A и B, называется … этих двух множеств.
Разность множеств A и B (A B) состоит из элементов,
Выберите все утверждения, верные для любых множеств
Множество, состоящее из пар (a, b), где a∈A, b∈B, называется декартовым … множеств A и B.
Диаграмма Венна используется для
Из скольких элементов состоит множество {1, {2, {3, 4}}}?
Говорят, что множество A содержится в множестве B, если каждый элемент A … B.
Обозначение ∅ используется для множества, состоящего из … элементов.
Какие из этих множеств являются конечными?
Установите соответствие между уравнениями на множествах и выводами,
Множество, состоящее из всех элементов, принадлежащих A или B, называется … этих двух множеств.
Симметрическая разность множеств A и B (A △ B) состоит из
Выберите все утверждения, верные для любых множеств
Множество, состоящее из пар (a, b), где a∈A, b∈B, называется … произведением множеств A и B.
В диаграмме Венна
Какое из следующих множеств имеет мощность, равную 5?
Мощность множества — это количество … в множестве.
Мощность пустого множества равна ….
Какие из следующих утверждений верны?
Установите соответствие между типами множеств и их мощностями:
Множества A и B равномощны, если существует … между их элементами.
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Теорема Кантора утверждает, что множество всех подмножеств множества A имеет … мощность, чем само множество A.
Какой метод используется для доказательства равномощности двух бесконечных множеств?
Какое из следующих множеств имеет мощность, равную 3?
Мощность множества определяется числом … в нем.
Мощность множества, содержащего только пустое множество, равна ….
Какие из следующих утверждений верны?
Установите соответствие между типами множеств и их мощностями:
Два множества называются равномощными, если между их элементами можно построить ….
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Теорема … гласит, что мощность множества всех подмножеств любого множества A больше мощности самого множества A.
Для доказательства того, что два бесконечных множества равномощны, используется метод…
На рынке продавались платья: 45 пышных, 50 с цветочками, 50 белого цвета, 20 белого цвета с цветочками, 20 пышных белого цвета, 25 пышных с цветочками, 15 пышных белого цвета с цветочками, 5 зеленых вытянутых, никогда не цветущих. Сколько только пышных платьев продавалось на рынке?
Какое из следующих утверждений верно для отношения эквивалентности?
Отношение «быть не меньше» (≥) на множестве действительных чисел является примером отношения … порядка
Отношение R на множестве A называется …, если для любых a, b из A, таких что aRb и bRa, следует, что a = b.
Какие из следующих утверждений верны для всех вполне упорядоченных множеств?
Установите соответствие между типами отношений и их свойствами:
Для доказательства утверждений, занумерованных натуральными числами, может использоваться принцип математической … .
Какое из следующих утверждений верно для фундированных множеств?
Выберите все верные утверждения:
Бинарное отношение, которое является рефлексивным, симметричным и транзитивным, называется отношением …
Какое из этих свойств не присуще отношению линейного порядка?
Какое из следующих утверждений верно для отношения эквивалентности?
Отношение «быть строго больше» (>) на множестве действительных чисел является примером отношения … порядка
Отношение R на множестве A называется …, если для любого a из A, aRa.
Какие из следующих утверждений верны для всех частично упорядоченных множеств?
Установите соответствие между типами отношений и их свойствами:
Принцип транфинитной математической индукции применим к утверждениям, занумерованным элементами … упорядоченного множества
Какое из следующих утверждений верно для всех вполне упорядоченных множеств?
Выберите все верные утверждения:
Бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным, называется отношением … порядка
Какое из этих свойств не присуще отношению эквивалентности?
В олимпиаде по математике участвовали 15 учащихся, по географии – 8, по литературе – 12. 4 ученика участвовали в олимпиадах по математике и географии, 5 – по математике и литературе, 3 – по географии и литературе. 2 ученика участвовали во всех трех олимпиадах. Сколько учеников участвовали только в олимпиаде по математике?
Аксиома выбора утверждает, что для любого семейства непустых множеств существует такая функция выбора, что она выбирает ровно один элемент из каждого множества. Это утверждение:
Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует … элемент.
Теорема Цермело утверждает, что любое множество может быть вполне ….
Какие из следующих утверждений верны относительно аксиомы выбора?
Установите соответствие между утверждениями и их следствиями:
… Гамеля — это максимальное линейно независимое подмножество векторного пространства
Выберите все верные утверждения:
Аксиома выбора необходима для доказательства:
Аксиома выбора необходима для доказательства существования:
Лемма Цорна применима к:
Теорема Цермело утверждает, что:
Какие из следующих утверждений верно относительно леммы Цорна?
Для доказательства теоремы Цермело может быть использована лемма …
Лемма Цорна утверждает, что если в частично упорядоченном множестве каждая цепь имеет верхнюю грань, то существует максимальный … элемент.
Базис Гамеля — это максимальное линейно … независимое подмножество векторного пространства
Может ли базис Гамеля содержать векторы, которые не являются ортогональными?
Какое свойство базиса Гамеля делает его особенно полезным для линейной алгебры?
Какие основные свойства обладает множество, удовлетворяющее условиям леммы Цорна?
Компактные … часто рассматриваются в контексте леммы Цорна
На полке находится 100 книг. Среди всех книг на полке 59 книг по физике, 71 книга на полке имеет объем больше 100 страниц. Сколько книг по физике имеет объем больше 100 страниц?
Ординалы — это:
Какое из следующих утверждений о свойствах операций над мощностями верно?
Арифметика ординалов включает операции:
Какой ординал является первым предельным ординалом?
Установите соответствие между понятиями и их определениями:
Индуктивные определения используются для:
Выберите все верные утверждения:
Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью теоремы …
Какой метод может быть использован для доказательства свойств ординалов?
Ординал ω + 1 обозначает:
Какое из следующих утверждений о свойствах операций над ординалами верно?
Какой ординал следует непосредственно за 2ω?
Свойство «быть больше» для ординалов является:
Если X и Y — два вполне упорядоченных множества, то либо они изоморфны друг другу, либо ровно одно из них … начальному отрезку другого.
Выберите все верные утверждения:
Теорему о том, что любое множество можно вполне упорядочить, можно доказать с помощью леммы …
Понятие «предельный ординал» используется для описания ординалов, которые:
Трансфинитная … может быть использована для алгоритмического построения множеств с любым порядковым типом.
В магазине испекли 300 пирожков. Среди них всего с мясом 116, с рисом 94 пирожка. Только с картофелем 30, только с мясом 58, только с рисом 42, только с картофелем и рисом 20, количество пирожков с картофелем и с мясом равно количеству пирожков с рисом и картофелем. Сколько пирожков со всеми тремя начинками сразу?
Какие из следующих высказываний являются тавтологией?
Высказывание «Если сегодня идет дождь, то я возьму зонт» является примером логической операции …
Операция, обозначаемая символом ¬, называется …
Какие из следующих пар высказываний являются эквивалентными?
Установите соответствие между логическими операциями и их обозначениями:
Логическая операция, подразумевающая логическое ИЛИ, называется …
Выберите все высказывания, которые всегда являются ложными:
Выберите все верные утверждения относительно импликации:
Операция, обозначаемая символом ↔, называется …
В логическом выражении (p → q) ∧ (¬p ∨ q), если p истинно и q ложно, то всё выражение …
Какое из следующих высказываний всегда ложно?
Высказывание «Если я поеду на работу на автобусе, то опоздаю» является примером логической операции …
Операция, обозначаемая символом ∧, называется …
Какие из следующих пар высказываний являются эквивалентными?
Установите соответствие между логическими операциями и их обозначениями:
Логическая операция, имеющая смысл ЕСЛИ И ТОЛЬКО ЕСЛИ, называется …
Выберите все высказывания, которые являются тавтологиями:
Выберите все верные утверждения относительно дизъюнкции:
Высказывание, истинное при любых значениях переменных, называется …
В логическом выражении (p ∧ q) ∨ (p ∧ ¬q), если p истинно и q ложно, то всё выражение …
Известно, что обе надписи на дверях либо истинны, либо ложны одновременно. Надпись на первой двери – «Клад за другой дверью», на второй двери – «Клада за этой дверью нет, а за другой – есть». Где находится клад?
Какое из следующих утверждений верно для языков первого порядка?
Квантор … обозначается символом ∀ и означает, что утверждение верно для всех элементов.
Квантор … обозначается символом ∃ и означает, что существует хотя бы один элемент, для которого верно утверждение.
Какое из следующих утверждений верно для интерпретаций в языках первого порядка?
Установите соответствие между элементами языка первого порядка и их ролями:
Формула ∀x x > 0 в контексте действительных чисел будет истинной для … чисел
Выберите все верные утверждения о формулах в языках первого порядка:
Выберите все верные утверждения о арифметических предикатах:
… в языке первого порядка может быть переменной, константой или функциональным символом от переменных.
В языках первого порядка, формула ∀x (P(x) → Q(x)) означает, что
Какое из следующих утверждений верно для формул в языках первого порядка?
Квантор существования в языках первого порядка обозначается символом … и используется для указания, что существует хотя бы один объект, удовлетворяющий условию.
Квантор всеобщности в языках первого порядка обозначается символом … и используется для указания, что утверждение верно для всех объектов домена.
Какие из следующих утверждений верны для термов в языках первого порядка?
Установите соответствие между элементами языка первого порядка и их ролями:
Формула ∀x x < 0 в контексте действительных чисел будет истинной для … чисел
Выберите все верные утверждения о предикатах в языках первого порядка:
Выберите все верные утверждения о функциональных символах в языках первого порядка:
… обладает носителем и значениями для символов предикатов и функций.
В языках первого порядка, формула ∃x (P(x) ∧ Q(x)) означает, что
На вопрос, кто из трех учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?
Какое из следующих утверждений верно для вычислимых функций?
Множество называется перечислимым, если его элементы можно вывести с помощью …
Множество называется …, если существует алгоритм, который для любого элемента может определить, принадлежит ли он этому множеству
Какие из следующих множеств являются перечислимыми?
Установите соответствие между понятиями и их определениями:
Теорема Поста утверждает, что если множество и его дополнение … , то это множество разрешимо.
Выберите все верные утверждения:
Какое из следующих множеств является разрешимым?
Какое из следующих утверждений верно для перечислимых множеств?
Множество называется …, если существует алгоритм, который по очереди выдает все его элементы и только их
Вычислимая функция — это функция, для которой существует … , вычисляющий её значение для любого входа.
Какие из следующих множеств являются разрешимыми?
Установите соответствие между понятиями и их определениями:
Теорема … утверждает, что множество и его дополнение являются перечислимыми, если и только если множество разрешимо
Выберите все верные утверждения:
Алгоритмом называется программа, написанная на … Тьюринга
Кто из этих исследователей занимался классической теорией алгоритмов?
Классическая теория алгоритмов описывает так называемые … функции.
Функция называется вычислимой, если существует …, который ее вычисляет
Утверждение “Неразрешимость проблемы остановки эквивалентна существованию перечислимого множества с неперечислимым дополнением” является следствием из теоремы
Катя, Таня и Лена решили пойти в кинотеатр. Каждая девочка высказала свои пожелания по поводу фильма: Я хочу посмотреть испанский боевик. Я не хочу смотреть испанскую комедию. Я хочу посмотреть американскую мелодраму. Каждая из них слукавила в одном из двух пожеланий. На какой фильм пошли девочки?
Проблема остановки программы заключается в вопросе:
Тьюринг доказал, что проблема остановки:
Проблема остановки демонстрирует, что:
Примером универсальной функции в реальном языке программирования является его …
Установите соответствие между понятиями и их описаниями:
Существует перечислимое множество с неперечислимым …
Выберите все верные утверждения:
Какой метод используется для доказательства неразрешимости проблемы остановки?
Установите соответствие между понятиями и их определениями:
Проблема остановки иллюстрирует, что:
Проблема остановки исследует вопрос:
Основной вывод из проблемы остановки состоит в том, что:
Установите соответствие между понятиями и их описаниями:
Существует … неразрешимое множество.
Примером … функции в реальном языке программирования является его интерпретатор.
Проблема остановки важна потому, что она:
Выберите все верные утверждения:
Существует … функция, принимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения.
В порту находятся три корабля: А, В и С. Известно, что истинны два высказывания: Если корабль A вышел в море, то корабль C – нет. В море вышел корабль B или корабль C, но не оба вместе. Какие корабли вышли в море?
Какое из следующих чисел является простым?
Наибольший общий делитель (НОД) чисел 36 и 48 равен…
Минимальное натуральное число, которое делится на каждое из чисел 2, 3 и 5, это…
Какие из следующих утверждений верны?
Установите соответствие между понятиями и их определениями:
Деление с остатком числа 17 на 5 дает в остатке…
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Отношение «делится на» является примером отношения:
Для выполнения условия «остаток строго меньше делителя» в случае деления многочленов, сравниваются их …
Какое из следующих чисел является составным?
Наименьшее общее кратное (НОК) чисел 6 и 8 равно…
… числа — это числа, которые имеют ровно два различных натуральных делителя: единицу и само себя
Какие из следующих утверждений верны?
Установите соответствие между понятиями и их определениями:
Деление с остатком числа 23 на 4 дает в остатке…
Какое из следующих утверждений верно?
Выберите все верные утверждения:
Рассмотрим числа от 1 до 100. Сколько существует чисел, которые не делятся на 2, 3 и 5?
Какой алгоритм используется для нахождения наибольшего общего делителя (НОД) двух чисел?
Основная теорема арифметики утверждает, что каждое натуральное число, большее 1, можно представить в виде произведения простых чисел, причем такое представление …, с точностью до порядка следования множителей.
Алгоритм Евклида основан на использовании деления с …
Какое из следующих утверждений верно для любых целых чисел a и b, где b ≠ 0?
Для чисел 1920 и 1080 НОД равен …
Какие из следующих утверждений верны в контексте основной теоремы арифметики?
Выберите все верные утверждения относительно алгоритма Евклида:
Лемма о разбиении единицы утверждает, что для любых … чисел a и b существуют такие целые числа x и y, что ax + by = 1
Диофантово уравнение ax + by = c имеет решение в целых числах, если и только если …
Какой алгоритм позволяет найти наибольший общий делитель двух натуральных чисел?
Основная теорема арифметики утверждает, что каждое натуральное число, большее 1, можно представить в виде произведения … чисел, причем такое представление единственно, с точностью до порядка следования множителей.
Принцип работы алгоритма Евклида основан на свойстве, что НОД(a, b) = НОД(b, r), где r обозначает … от деления a на b.
Какое из следующих утверждений верно для алгоритма Евклида?
Установите соответствие между понятиями и их определениями:
Наибольший общий делитель чисел 2560 и 1440, равен …
Выберите все верные утверждения о алгоритме Евклида:
Для каких значений c диофантово уравнение ax + by = c имеет решение?
Найдите наибольший общий делитель (НОД) для чисел 682 и 527.
Какой остаток получится при делении числа 15 на 4?
Если a ≡ b (mod m), то числа a и b имеют одинаковый остаток при делении на m. Это утверждение является определением сравнения по … m
Отношение «сравнимы по модулю n» является примером отношения:
Выберите все верные утверждения относительно арифметики остатков:
Установите соответствие между выражениями и их значениями по модулю 10:
Малая теорема Ферма гласит, что если p — простое число и a не делится на p, то ap-1 ≡ … (mod p).
Выберете все свойства, верные для отношения «сравнимы по модулю n»:
Выберите все верные утверждения, связанные с малой теоремой Ферма:
Какой остаток получится при делении числа 18 на 5?
Если a ≡ b (mod m), то числа a и b имеют одинаковый … при делении на m. Это утверждение является определением сравнения по модулю m
Выберите все верные утверждения относительно арифметики остатков:
Установите соответствие между выражениями и их значениями по модулю 10:
Малая теорема … утверждает, что для любого целого числа a и простого числа p, если a не делится на p, то ap-1 ≡ 1 (mod p).
a … b — остаток при делении а на b
Z/KZ называется … по модулю к
Чем малая теорема Ферма отличается от великой теоремы Ферма?
Какие приложения имеет малая теорема Ферма в криптографии?
Рассмотрим последовательность чисел: 1, 4, 7, 10, 13, …, где каждый последующий член больше предыдущего на 3. Найдите остаток от деления 500-го члена этой последовательности на 5.
Какой метод является основой для системы шифрования RSA?
В криптографии функция, сложная для обращения без знания секретного ключа, называется …
Схема … позволяет двум сторонам безопасно обменяться секретным ключом
Какое утверждение верно для схемы шифрования RSA?
Установите соответствие между криптографическими понятиями и их описаниями:
Принцип шифрования в алгоритме … основан на применении малой теоремы Ферма.
Какой алгоритм является основой для схемы Диффи–Хеллмана?
Выберите все верные утверждения о криптографии:
… в криптографии нужны для преобразовании входных данных в уникальный набор символов фиксированной длины
Какое утверждение неверно для схемы Диффи–Хеллмана?
Какой алгоритм не используется непосредственно в криптографии?
В криптографии, метод «открытого ключа» относится к … шифрованию
Алгоритм шифрования … основывается на сложности задачи разложения больших чисел на простые множители
Установите соответствие между криптографическими алгоритмами и их характеристиками:
Малая теорема Ферма находит применение в криптографии для генерации больших … чисел
Какой метод является основой для генерации ключей в схеме Диффи–Хеллмана?
Принцип шифрования в алгоритме RSA основан на применении малой теоремы ….
Как расшифровывается аббревиатура RSA?
Найдите наименьшее натуральное число, которое дает остаток 4 при делении на 6, остаток 5 при делении на 7 и остаток 6 при делении на 8.
Какой граф называется полным?
Что такое степень вершины в графе?
Как называется граф, в котором между любыми двумя вершинами существует путь?
Какие из следующих утверждений верны для деревьев?
Установите соответствие между типами графов и их характеристиками:
Что такое петля в теории графов?
Выберите все верные утверждения о свойствах графов:
Как называется путь в графе, который начинается и заканчивается в одной и той же вершине?
Какое из следующих утверждений верно для ориентированных графов?
Установите соответствие между понятиями и их определениями:
Какой граф называется ациклическим?
Что такое изолированная вершина в графе?
Как называется граф, в котором между любыми двумя вершинами существует не более одного пути?
Какие из следующих утверждений верны для ориентированных графов?
Что такое мультиграф?
Выберите все верные утверждения о свойствах графов:
Как называется граф, в котором возможно наличие петель и кратных рёбер?
Какое из следующих утверждений верно для деревьев?
Установите соответствие между понятиями и их определениями:
В графе G с 8 вершинами каждая вершина соединена с каждой другой вершиной. Сколько ребер содержит этот граф?
Какой алгоритм используется для обхода всех вершин ориентированного графа?
При поиске в глубину, если граф содержит циклы, какое утверждение верно?
Какой структурой данных обычно пользуются при реализации алгоритма поиска в глубину?
Какой из следующих вариантов лучше всего описывает принцип работы алгоритма поиска в глубину?
Установите соответствие между типами ребер в ориентированном графе и их характеристиками при поиске в глубину:
Какое из следующих утверждений верно для алгоритма поиска в глубину?
… в графе называется путь, начинающийся и заканчивающийся в одной и той же вершине.
Выберите все верные утверждения о поиске в глубину:
Установите соответствие между этапами алгоритма поиска в глубину и их описанием:
Какой метод используется для предотвращения зацикливания алгоритма поиска в глубину в присутствии циклов в графе?
Какой алгоритм позволяет определить, есть ли в ориентированном графе цикл?
Какая структура данных не используется при реализации алгоритма поиска в глубину?
Какое из следующих утверждений неверно относительно алгоритма поиска в глубину?
Выберите все верные утверждения о поиске в глубину в ориентированных графах:
Какой метод используется для определения порядка обработки вершин в алгоритме поиска в глубину?
Какой аспект алгоритма поиска в глубину позволяет определить компоненты сильной связности в ориентированном графе?
Рассмотрим граф G с 11 вершинами и 18 ребрами. Какое минимальное количество ребер должно быть удалено из графа G, чтобы он не содержал циклов?
Какой алгоритм используется для нахождения компонент сильной связности в ориентированном графе?
Компоненты сильной … в графе – это подграфы, в которых каждая вершина достижима из другой вершину посредством направленного пути.
Установите соответствие между алгоритмами и их особенностями:
Граф, вершинами которого являются компоненты связности другого графа, называется его …
В графе, представленном матрицей смежности, элемент aij равен 0, если между вершинами i и j …
Выберите все верные утверждения относительно алгоритма поиска в ширину:
Какой алгоритм используется для нахождения кратчайшего пути от одной вершины до всех остальных в взвешенном графе без отрицательных весов рёбер?
Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в …, называется очередью
Алгоритм … можно интерпретировать как модифицированный алгоритм поиска в ширину, где взешенное ребро заменяется на путь из нескольких ребер.
Какой алгоритм не используется для нахождения компонент сильной связности?
… сильной связности в графе – это подмножества вершин, в которых каждая вершина достижима из другой вершину посредством направленного пути.
В графе, представленном матрицей смежности, элемент aij равен 1, если между вершинами i и j …
Выберите все верные утверждения о компонентах сильной связности:
Структура данных, используемая для хранения вершин, еще не успевших получить свой уровень в алгоритме поиска в ширину, называется …
Алгоритм Дейкстры можно интерпретировать как модифицированный алгоритм поиска в …, где взешенное ребро заменяется на путь из нескольких ребер.
Рассмотрим граф G с 10 вершинами. Известно, что в графе 4 вершины имеют степень 3, а остальные вершины имеют степень 2. Сколько компонент связности содержит граф G?
Учащимся было необходимо написать 3 контрольные работы. Первую или вторую контрольные работы успешно написали 33 учащихся, первую или третью – 31 учащийся, вторую или третью – 32 учащихся. Не менее двух контрольных работ выполнили 20 учащихся. Сколько учащихся успешно решили только одну контрольную работу?
В классе 35 учеников. Каждый из них увлекается хотя бы одним видом спорта: хоккеем, футболом и теннисом. Всеми тремя видами спорта увлекается 6 учеников, хоккеем и футболом – 15 учеников, хоккеем и теннисом – 13 учеников, теннисом и футболом – 9 учеников. Сколько учеников увлекаются только одним видом спорта?
На рынке продавались платья: 45 пышных, 50 с цветочками, 50 белого цвета, 20 белого цвета с цветочками, 20 пышных белого цвета, 25 пышных с цветочками, 15 пышных белого цвета с цветочками, 5 зеленых вытянутых, никогда не цветущих. Сколько всего платьев продавалось на рынке?
В олимпиаде по математике участвовали 15 учащихся, по географии – 8, по литературе – 12. 4 ученика участвовали в олимпиадах по математике и географии, 5 – по математике и литературе, 3 – по географии и литературе. 2 ученика участвовали во всех трех олимпиадах. Сколько учеников участвовали только в олимпиаде по географии?
В музыкальном кружке обучается 20 человек. 11 из них любят классическую музыку, а 12 – современную музыку. Сколько человек любят только классическую музыку?
На ферме пасли коз и козлов. Козлов всего 100, безрогих белых козлов 30, белых козлов с рогами 45, черных не рогатых козлов 20, черных рогатых коз 15, белых не рогатых коз 75, всего коз 125, всего рогатых коз и козлов 95. Сколько черных рогатых козлов пасли на ферме?
Найдите количество решений системы уравнений: ¬x1+x2=1 ¬x2+x3=1 … ¬x9+x10=1, где x1,…,x10 – неизвестные логические величины
В банке произошло преступление. Стали известны два высказывания: Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал. Если Иванов не участвовал, то Сидоров не участвовал. Определите участника преступления, исходя из этих высказываний.
Рома хочет узнать, какая погода будет завтра. В прогнозе погоды он услышал несколько высказываний: Если не будет ветра, то будет пасмурная погода без дождя. Если будет дождь, то будет пасмурно и без ветра. Если будет пасмурная погода, то будет дождь и не будет ветра. Определите, какая погода будет завтра.
Три свидетеля аварии сообщили сведения о скрывшемся преступнике. Высказывания каждого свидетеля приведены ниже. Преступник был на белом «Рено» Преступник уехал на синей «Тойоте» Машина была точно не белая, и по всей видимости, это был «Форд». Когда удалось отыскать машину, выяснилось, что в каждом из высказываний был верен только один из параметров автомобиля. Какая и какого цвета была машина у нарушителя?
В интервале от 1 до 1000 найдите количество чисел, которые делятся на 4 или 6, но не делятся на 12.
Установите соответствие между утверждениями и их значением в контексте алгоритма Евклида и основной теоремы арифметики:
Найдите наименьшее общее кратное (НОК) для чисел 234 и 221.
Укажите наименьшее натуральное число, которое дает остаток 3 при делении на 4, остаток 4 при делении на 5 и остаток 5 при делении на 6.
Пусть n — наименьшее натуральное число, которое при делении на 5 дает остаток 2, при делении на 6 дает остаток 3. Найдите остаток от деления n на 6.
Установите соответствие между типами графов и их характеристиками:
В графе G с 7 вершинами каждая вершина соединена с двумя другими вершинами. Сколько ребер содержит этот граф?
Рассмотрим граф G с 15 вершинами и 8 ребрами. Какое максимальное количество ребер может быть добавлено в граф G, чтобы он не содержал циклов?
Рассмотрим граф G с 8 вершинами. Каждая вершина имеет степень 4. Сколько компонент связности содержит граф G?