Алгоритм Форда-Фалкерсона.

Вход: транспортная сеть , заданная матрицей (), где = (, ), , , пропускных способностей, или каким-нибудь другим способом.

(Начинаем с нулевого потока.)

for е ∈ E do f(e) := 0;

(Фаза 1.)

Удаляем все метки вершин;

Помечаем источник;

while вершина t не помечена и существует непомеченная вершина v do

помечаем вершину v;

od;

if сток не помечен then конец: максимальный поток построен;

(Фаза 2.)

v:= t; u:= d_v;

while v ≠ s do

if b_v = ″+″ then f(u,v):= f(u,v)+ ∆_t

else f(u,v):= f(u,v)− ∆_t;

v:= u

od;

Возврат на фазу1.

Выход: максимальный потокf.

6а. ВАРИАНТЫ ЗАДАЧ ДЛЯ ГРУПП ПО НАПРАВЛЕНИЮ ″БИЗНЕС-ИНФОРМАТИКА″

ТЕМА ″ТРАНСПОРТНЫЕ СЕТИ″

Транспортная сеть задана списком дуг , где – начало дуги, – конец дуги, а – пропускная способность дуги.

1. Построить все -разрезы сети;

2. Используя помечающий алгоритм, построить максимальный поток сети и вычислить его значение.

3.

ГРУППА БИЗНЕС-ИНФОРМАТИКА 2 КУРС 2011∕ 2012 УЧ. ГОД
ВАРИАНТ	ФИО	Оценка
ЭКОНОМФАК
	Валиева Эльвира
	Гильмутдинова Фарида
	Гилязова Эльвира
	Залялиева Динара
	Исмоилова Фируза
	Каримуллин Алмаз
	Коган Илья
	Крылов Сергей
	Лабутин Евгений
	Мошкова Наталья
	Мухаметшина Лиля
	Сибгатуллина Дина
	Скарлыгина Диана
	Хайруллина Эвилина
	Хайсарова Резеда
	Шамсутдинова Айшна
ВМК (ВМиИТ)
	Калита Екатерина
	Латыпова Наиля
	Мухамедова Алина
	Трушина Екатерина
	Слухов Андрей
	Шакиров Ренат

 

ВАРИАНТ 1	ВАРИАНТ 2	ВАРИАНТ 3	ВАРИАНТ 4	ВАРИАНТ 5	ВАРИАНТ 6
ВАРИАНТ 7	ВАРИАНТ 8	ВАРИАНТ 9	ВАРИАНТ 10	ВАРИАНТ 11	ВАРИАНТ 12
ВАРИАНТ 13	ВАРИАНТ 14	ВАРИАНТ 15	ВАРИАНТ 16	ВАРИАНТ 17	ВАРИАНТ 18
ВАРИАНТ 19	ВАРИАНТ 20	ВАРИАНТ 21	ВАРИАНТ 22	ВАРИАНТ 23	ВАРИАНТ 24

6б. ВАРИАНТЫ ЗАДАЧ ДЛЯ ГРУПП ПО СПЕЦИАЛЬНОСТИ ″МАТЕМАТИЧЕСКИЕ МЕТОДЫ В ЭКОНОМИКЕ″

ТЕМА ″ТРАНСПОРТНЫЕ СЕТИ″

Транспортная сеть задана списком дуг , где – начало дуги, – конец дуги, а – пропускная способность дуги.

1. Построить все -разрезы сети;

2. Используя помечающий алгоритм, построить максимальный поток сети и вычислить его значение.

 

ГРУППА ЭКОНОМ. КИБЕРНЕТИКА 2 КУРС 2011∕ 2012 УЧ. ГОД
ВАРИАНТ	ФИО	Оценка
	Ахметзянова Лилия
	Билалова Лейла
	Вафина Альфинур
	Гараева Гульшат
	Глебова Валерия
	Зюмрва Елена
	Крылов Сергей
	Райхлина Екатерина
	Савельева Маргарита
	Салихова Айназ
	Титоренко Роман
	Тубольцева Ксения
	Фейсханов Алмаз
	Цуканова Ольга
	Чудаева Алина
	Шайдулова Софья
	Яковлева Екатерина

7.ЗАДАЧИ по теме ″РЕКУРСИВНЫЕ ФУНКЦИИ″.

1. Доказать, что следующие функции примитивно рекурсивны:

1) (где − константа)

2)

3) (где )

4)

5)

6) (где )

7)

8)

9)

10)

11) , ;

12) | ;

13 )

14)

15) − функции алгебры логики (отрицание, дизъюнкция, конъюнкция), где чётные числа трактуются как , а нечётные как , т.е.

16) − произвольная функция алгебры логики;

17) где примитивно рекурсивная функция, ;

18) где примитивно рекурсивная функция, ;

19) (здесь );

20) rest (, ) (здесь rest(, ) );

21) (при фиксированном );

22) (при фиксированном , );

23) (, ) наибольший общий делитель чисел и (здесь (, ) = 0);

24) [ , ] наименьшее общее кратное чисел и (здесь [ , = [ , ] 0);

25) − число сочетаний из по (здесь 0 при );

26)

27)

где , , , примитивно рекурсивные функции от переменных .

 

2. Применяя операцию примитивной рекурсии к функциям и , определить функцию и записать её в аналитической форме:

1) , ;

2) , ;

3) , ;

4) , ;

5) , ;

6) , ;

7) , ;

8) ,

9)

10)

 

3. Вычислить соответствующую функцию, применяя операцию минимизации. Результаты представить в аналитической форме:

 

1) [| −3| = 0];

2) [| − | = 0];

3) [| − | = 0];

4) [ − = 0];

5) [| − |= 0];

6) [| − | = 0];

7) [| − | = 0];

8) [| − | = 0];

9) [| − | = 0];

10) [| − | = 0];

11) [| − | = 0];

12) [| − | = 0];

13) [| − | = 0];

14) [| − | = 0].

 

4. Доказать, что следующие функции частично рекурсивны:

 

1) нигде не определённая функция;

2)

3)

4)

6) функция, определённая только при , ,…, .

5. Найти примитивно рекурсивную функцию, из которой однократным применением операции минимизации можно получить частично рекурсивную функцию :

1) ;

2) ;

3) ;

4)

5) ;

6) ;

7) ;

8) ;

9) .

8. ЗАДАЧИ ПО ТЕМЕ ″МАШИНЫ ТЬЮРИНГА″

1. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 220, № 1.1.) Установить, применима ли машинаТьюринга , заданная программой , к слову . Если применима, найти рельтат применения. Предполагается, что − начальное, − заключительное состояния машины, а начальная конфигурация.

a) б) в)

a) б) в)

a) б) в)

 

2. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 220-221, идея из № 1.2.) Построить машину в алфавите , , которая:

a) применима к любой непустой ленте (т.е. останавливается лишь в том случае, если хотя бы в одной из ячеек записан символ ; зона действия − бесконечная слева и справа от начальной обозреваемой ячейки);

б) применима к словам вида и не применима к словам вида ;

в) применима только к словам вида ();

г) применима к словам вида () и не применима к словам вида , если .

 

3. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 221, № 1.3.) По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:

 

⇐ Предыдущая123

Поделиться:

Воспользуйтесь поиском по сайту: