- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
-
Методический пример.
-
Найти все строки в файле grep.txt, начинающихся с символа «+».
grep -Pr "^[+]" r:\grep.txt
-
Найти все строки в файле grep.txt, в формате одна цифра символ “+” одна цифра.
grep -Pr "[0-9]\+[0-9]" r:\grep.txt
grep -Pr "\d\+\d" r:\grep.txt
-
Найти все строки в файле grep.txt, в формате +x-xxx-xxxxxxx, где x – это цифра.
grep -Pr "^(\+)(\d{1})(\-)(\d{3})(\-)(\d{7})$" r:\grep.txt
-
Найти все строки в файле grep.txt, в содержащие цифру с точкой.
grep -Pr "^([+-]?)(\d+)(\.?)(\d*)$" r:\grep.txt
-
Контрольная распечатка.
grep -Pr "^[+]" r:\grep.txt
+7-123-7654321
+7-123-7654321
+7-123-7654521
+7-123-1234567
+7-123-765432111
+7-926-5550001
+MGUPI
+6777
grep -Pr "[0-9]\+[0-9]" r:\grep.txt
11+1
5+2
33+8
grep -Pr "\d\+\d" r:\grep.txt
11+1
5+2
33+8
grep -Pr "^(\+)(\d{1})(\-)(\d{3})(\-)(\d{7})$" r:\grep.txt
+7-123-7654321
+7-123-7654321
+7-123-7654521
+7-123-1234567
+7-926-5550001
grep -Pr "^([+-]?)(\d+)(\.?)(\d*)$" r:\grep.txt
-17.98
+6777
22.08
-
Отчет по практической работе.
Отчет оформляется в соответствии с требованиями, предъявляемыми к оформлению лабораторных работ в вузе, и должен содержать:
-
Титульный лист.
-
Наименование и цель работы.
-
Исходные данные варианта задания.
-
Полученное регулярное выражение.
-
Контрольная распечатка.
Замечание: листы отчета должны быть скреплены.
-
Контрольные вопросы.
Что такое регулярное выражение?
Какие действия выполняет команда grep?
Что такое мета символы?
Что такое модификаторы?
Правила регулярного выражения?
-
Варианты заданий.
Вариант задания определяется по последней цифре в зачётной книжке.
-
Регулярное выражение для поиска всех URL адресов содержащих в названии первой директории слова it-6 или it6 или it-5 или it5, в следующем виде: “http://www.mgupi.ru/xxx(it-6 или it6 или it-5 или it5)xxx/index.php”, причём символы x означают любые буквы, которых может и не быть.
-
Регулярное выражение для поиска всех URL адресов содержащих в названии 3-го поддомена слова it-6 или it6 или it-5 или it5, в следующем виде: “http:// xxx(it-6 или it6 или it-5 или it5)xxx.mgupi.ru/main/index.php”, причём символы x означают любые буквы, которых может и не быть.
-
Регулярное выражение для поиска всех URL адресов в следующем виде: “http:// xxx.mgupi.ru/xxx”, причём символы x означают любые буквы, которых может и не быть.
-
Регулярное выражение для поиска всех ip-адресов в диапазоне от 172.22.50.0 до 172.22.116.255.
-
Регулярное выражение для поиска всех ip-адресов в диапазоне от 192.168.10.0 до 192.168.112.255.
-
Регулярное выражение для поиска всех e-mail адресов содержащих в качестве домена 3-го уровня слово “it” и две или одну цифру, в следующем виде: “xxx@xx{слово it две или одна цифра}xxx.mgupi.ru”, причём символы x означают любые буквы, которых может и не быть.
-
Регулярное выражение для поиска всех e-mail адресов содержащих в качестве имени пользователя слова it6 или it5 и две или одну цифру в имени 2-го домена, по следующему формату: “xxx(it6 или it5)xxx@xxx{две или одна цифра}xxx.ru”, причём символы x означают любые буквы, которых может и не быть.
-
Регулярное выражение для поиска всех телефонных номеров c кодом 916 или 903 или 926 в формате +x-(916 или 903 или 926)-xxxxxxx, где x – это одна цифра.
-
Регулярное выражение для поиска всех e-mail адресов содержащих в качестве имени пользователя семь цифр, а в домене 2-го уровня слова it6 или it5, в следующем виде: “ddddddd@xxx(it6 или it5)xxx.xxx.ru”, причём символы x означают любые буквы, которых может и не быть, а d – это одна цифра.
-
Регулярное выражение для поиска всех ip-адресов в диапазоне от 10.131.37.0 до 10.131.158.255.