Введение в алгоритмы

5.1. На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству их решили проводить вдоль дорог. Каким образом провести телефонные линии, чтобы их общая длина была минимальной? Ниже приведена матрица расстояний между бытовками: элемент а_ij таблицы равен 0, если i-я и j-я бытовка не соединены дорогой напрямую, в противном случае а_ij равно расстоянию между соответствующими бытовками.

5.2. Из города А в город Б ведут несколько дорог (карту см. на рис. ниже). Найдите число маршрутов автомобильного путешествия из А в Б, учитывая, что при движении автомобиль должен все время приближаться к Б.

Основные алгебраические структуры.

6.1. Обозначим через В₂ множество, состоящее из нулевой  матрицы  и четырех «матричных единиц» , , , .

а) Проверить, что В₂ является полугруппой относительно умножения.

б) Составить таблицу Кэли для полугруппы В₂.

6.2. а) Доказать, что преобразования ,  и  составляют порождающее множество полугруппы всех преобразований на трехэлементном множестве.

б) Выяснить, существует ли для полугруппы  двухэлементное порождающее множество?

6.3. Определить, какие из следующих отображений  группы (Z,+) в себя являются гомоморфизмами: а) ; б) ; в)  г) .

6.4. Найти порядок элемента  группы S₅.

6.5. Найти свободные коммутативные полугруппы над { b } и над { a, b }.

6.6. Выяснить, образуют ли идеал необратимые элементы следующих колец: а) Z₉; б) Z₁₂; в) Z₁₆.

6.7. Найти все делители нуля в кольцах: а) Z₉; б) Z₁₂; в) Z₈; г) Z.

6.8. Решить в поле Z₅ следующую систему уравнений: