- •1. Булевы функции двух переменных.
- •2. Булевы функции: эквивалентность и сумма по модулю два. Таблицы истинности, комбинационные схемы, изображение базисных элементов.
- •3. Булевы функции: Штрих шеффера и стрелка Пирса.
- •4. Совднф и совкнф. 5. 6. Построение их по таблице истинности
- •7. Карты карно и их связь с таблицами истинности
- •8. Построение сднф по карте карно. 9. Построение скнф по карте карно
- •10. Построение булевой формулы по комбинационной схеме
- •11. Упрощение булевых формул
- •12. Исключение лишних членов при упрощении булевых формул.
- •13. Конституенты и импликанты и их роль в алгебре логики.
- •14. Минимизация булевой функции методом квайна.
- •15. Минимизация булевой функции по методу блейка
- •Минимизация булевой функции по методу нельсона
- •Функциональная полнота систем логических функций. 19. Примеры функционально полных систем
- •20. Основные понятия исчисления предикатов.
- •21. Алгебра предикатов: операции отрицания, конъюнкции и дизъюнкции.
- •22. Алгебра предикатов: операции импликации и эквивалентности.
- •!!!!!!!«Эквивалентность – не нашел!»!!!!!!!
- •23. Понятие квантора. Двойственность кванторов.
- •24. Применение кванторов в исчислении предикатов – не нашел!
- •25. Характеристическая функция принадлежности для обычных и нечетких множеств.
- •26. Понятие нечеткого подмножества
- •27. Включение, равенство, дополнение и пересечение нечетких множеств
- •28. Объединение, разность, возведение в степень нечетких множеств
- •29. Разность и симметрическая разность нечетких множеств
- •30. Понятие нечеткого отношения. Проекция и носитель нечеткого отношения
- •31. Объединение, пересечение и алгебраическое произведение двух нечетких отношений.
- •32. Алгебраическая сумма и симметрическая разность двух нечетких отношений
- •33. Композиция двух нечетких отношений.
- •40. Ориентированные и неориентировапнные графы. Деревья.
- •41. Способы задания графов
- •42. Задание графа матрицей Инцидентности.
- •43. Задание графа матрицей смежности.
- •44. Задача о кратчайшем пути на графе с ребрами единичной длины.
- •45. Построение графа наименьшей длины
- •46. Транспортные сети. Основные понятия.
- •47. Задача о наибольшем потоке в транспортной сети.
- •48. Понятие алгебраической системы
- •50. Строки символов как примеры полугрупп и моноидов - ????????????????.
- •51. Понятие группы.
- •52. Подгруппы. Построение подгрупп заданной группы.-???????????????????
- •54. Группа подстановки.
- •55. Группа с операцией сложения по модулю m - ????????????
- •56/ Группа с операцией умножения по модулю m - ????????????
- •57. Кольца.
- •58. Поля.
- •59. Поле галуа.
- •60 Многочлены над полями галуа??????????
- •61. Изоморфизм и гомоморфизм - ????????????
46. Транспортные сети. Основные понятия.
Транспортной сетью называется конечный граф без петель, у которого:
1) существует одна и только одна такая вершина Хо, что Г-1xo = Æ (эта вершина называется входом сети);
2) существует одна и только одна такая вершина z, что Гz = Æ (она называется выходом сети);
3) каждой дуге графа и отнесено целое число с(и), называемое пропускной способностью дуги и.
С понятием транспортной сети тесно связано понятие потока. Пусть х — произвольная вершина. Обозначим
Ux- — множество дуг, заходящих в х, а через Ux+ — множество дуг, выходящих из х. Потоком по транспортной сети называется функция j(u), удовлетворяющая условиям:
Функцию j(u) можно рассматривать как количество вещества, протекающего (в единицу времени) по дуге и=(х, у) от х к у. Согласно условию (7-1) это количество вещества не может превышать пропускной способности дуги с (u). Согласно условию (7-2) в каждой вершине х, отличной от входа x0 и выхода z, количество притекающего вещества равно количеству вытекающего. Следовательно, вещество не может накапливаться ни в одной вершине транспортной сети за исключением входа и выхода. А это означает, что поток, выходящий из входной вершины x0 в точности равен потоку, входящему в выходную вершину z:
Величина j(z) называется величиной потока транспортной сети.
н а рисунке приведен пример транспортной сети. Цифры в разрывах дуг означают пропускную способность дуги. Стрелки указывают направление потоков, а цифры около стрелок — величину потока. К анализу транспортных сетей сводятся многие задачи, возникающие при планировании поставок, распределении товаров между потребителями и т. п.
47. Задача о наибольшем потоке в транспортной сети.
Транспортная задача (классическая) - задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.
Затем требуется определить опорный план и путем последовательных операций найти оптимальное решение. Опорный план можно найти методом "северо-западного угла" или методом "наименьшего элемента".
Метод северо-западного угла (диагональный). На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из Аi или полностью удовлетворяется потребность Вj.
Одним из способов решения задачи является метод минимального (наименьшего) элемента Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями. Алгоритм решения:
Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел.
Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.