Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Классификация алгоритмов поиска

Форма №3

	Нехай матриця A має розмірність m´n, а матриця B — розмірність m´k (m n). Тоді:	а	б	в	г	г
а)розмірність матриці-добутку C=AB буде дорівнювати m´k, елементи її обчислюються за формулою ;
б)розмірність матриці-добутку C=AB буде дорівнювати n´k, елементи її обчислюються за формулою ;
в)розмірність матриці-добутку C=AB буде дорівнювати m´m;
г) виконати множення неможливо.
	Три вектори будуть лінійно-залежними у випадку, якщо:	а	б	в	г	а
а)вони належать до дво-вимірного простору;
б)їх лінійна комбінація дорівнює ненульовому вектору;
в)їх лінійна комбінація дорівнює нульовому вектору тільки коли усі коефіцієнти комбінації дорівнюють нулю;
г) вони є направляючими векторами мимобіжних прямих.
	Функція попиту, яка зображена на малюнку, задовольняє умовам:	а	б	в	г	г
а) f '(x) > 0 і f ''(x) < 0;
б) f '(x) < 0 і f ''(x) > 0;
в) f '(x) < 0 і f ''(x) < 0;
г) f '(x) > 0 і f ''(x) > 0.
	Яка з наступних виробничих функцій від x та y задана неявно?	а	б	в	г	в
а)
б)
в)
г)
	Гранична ефективність ресурсу x виробничої функції y= 3x3 +2 x	а	б	в	г	а
а)зростає для додатних значень ресурсу;
б)не визначена для додатних значень ресурсу;
в)зростає для значень x на всій числовій осі;
г) спадає для значень x на всій числовій осі.
	Виробнича функція y= 3x3 +2 x	а	б	в	г	б
а)спадає на всій числовій осі;
б)зростає на всій числовій осі;
в)змінює спадання на зростання в точці x= -2;
г) змінює зростання на спадання в точці x= -2.
	Виробнича функція y= 3x3 +2 x має наступну властивість:	а	б	в	г	г
а)досягає мінімуму в точці x= -2;
б) досягає мінімуму в точці x= 0;
в) досягає максимуму в точці x= 1;
г) екстремумів не має.
	x дорівнює	а	б	в	г	в
а)4
б)-4
в)-2
г) 2
	Розв’язок системи лінійних рівнянь АХ = В можна отримати за формулою:	а	б	в	г	в
а)
б)
в)
г)
	Яке з наведених нижче значень буде власним значенням матриці ?	а	б	в	г	а
а) 1;
б)2;
в)-2;
г) -1.
		а	б	в	г
а)
б)
в)
г)
	Яке з наведених нижче значень буде власним значенням матриці ?	а	б	в	г	б
а)-1;
б)3;
в)2;
г) -2.
	Яке з наведених нижче значень буде власним значенням матриці ?	а	б	в	г	г
а)-1;
б)-6;
в)6;
г) -3.
	Зміна обсягу виробленої за час t продукції задається формулою u(t)=e3t. Продуктивність праці у момент часу t=4 складає:	а	б	в	г	б
а)12;
б)3e12;
в) e12;
г) 16.
	Зміна обсягу виробленої за час t продукції задається формулою u(t)=t4-t2. Продуктивність праці у момент часу t=2 складає:	а	б	в	г	в
а)12;
б)16;
в)28;
г) 20.
	Залежність між витратами виробництва y та обсягом продукції x, яка випускається, виражається формулою y =50 x -0,05 x 3. Граничні витрати при обсягу продукції x = 10 од. дорівнюють	а	б	в	г	а
а)35 гр.од.;
б)45 гр.од.;
в)40 гр.од.;
г) 30 гр.од.
	Залежність між витратами виробництва y та обсягом продукції x, яка випускається, виражається формулою y =60 x -0,1 x 2. Граничні витрати при обсягу продукції x = 10 од. дорівнюють	а	б	в	г	в
а)590 гр.од.;
б)50 гр.од.;
в)40 гр.од.;
г) 45 гр.од..
	Залежність між витратами виробництва y та обсягом продукції x, яка випускається, виражається формулою y =50 x 2-0,25 x 3. Граничні витрати при обсягу продукції x = 10 од. дорівнюють	а	б	в	г	б
а)4750 гр.од.;
б)925 гр.од.;
в)1000 гр.од.;
г) 5000 гр.од..
	Обсяг продукції u, вироблений бригадою може бути описаний рівнянням u=-5/6t3+15/2t2+100t+50 (од.), 1≤t≤8 (t – робочий час у годинах). Тоді продуктивність праці за годину до її закінчення дорівнює	а	б	в	г	в
а)165 од./год.;
б)300 од./год.;
в)82,5 од./год.;
г) 90 од./год..
	Обсяг продукції u, вироблений бригадою може бути описаний рівнянням u=-5/6t3+15/2t2+100t+50 (од.), 1≤t≤8 (t – робочий час у годинах). Тоді швидкість зміни продуктивності праці за годину до її закінчення дорівнює	а	б	в	г	б
а) 20 од./год2.;
б)-20 од./год2.;
в)-30 од./год2.;
г) 30 од./год2..
	Обсяг продукції u, вироблений бригадою може бути описаний рівнянням u=-5/6t3+15/2t2+100t+50 (од.), 1≤t≤8 (t – робочий час у годинах). Тоді продуктивність праці через годину після початку роботи дорівнює	а	б	в	г	а
а)112,5 од./год.;
б)225 од./год.;
в)100 од./год.;
г) 300 од./год..
	Обсяг продукції u, вироблений бригадою може бути описаний рівнянням u=-5/6t3+15/2t2+100t+50 (од.), 1≤t≤8 (t – робочий час у годинах). Тоді швидкість зміни продуктивності праці через годину після її початку дорівнює	а	б	в	г	г
а)-15 од./год2.;
б)-10 од./год2.;
в)15 од./год2.;
г) 10 од./год2..
	Продуктивність праці виробничої ланки описується функцією f(t) = -3t2 + 14t+100 (од./год.). Обсяг виробленої ланкою продукції з другої по третю годину праці дорівнює:	а	б	в	г	б
а)110 од.;
б)116 од.;
в)92 од.;
г) 5 од..
	Продуктивність праці виробничої ланки описується функцією f(t) = -3t2 + 14t+100 (од./год.). Обсяг виробленої ланкою продукції з третьої по п’яту годину праці дорівнює:	а	б	в	г	в
а)100 од.;
б)320 од.;
в)194 од.;
г) 169 од..
	Задача лінійного програмування може бути розв’язана графічно	а	б	в	г	в
а)лише задачі, що мають обмеження у вигляді системи нерівностей, які містять дві змінні;
б)лише задачі в канонічній формі, система обмежень яких містить n невідомих і m лінійно-незалежних відношень, причому n-m=2;
в)або задачі, що мають обмеження у вигляді системи нерівностей, які містять дві змінні, або задачі в канонічній формі, система обмежень яких містить n невідомих і m лінійно-незалежних відношень, причому n-m=2;
г) лише задачі в канонічній формі, система обмежень яких містить n невідомих і m лінійно-незалежних відношень, причому m - n =2.
	Оптимальний розв’язок задачі лінійного програмування може знаходитись	а	б	в	г	б
а)всередині області допустимих розв’язків;
б) або в вершині багатогранника розв’язків, або в любій точці, яка є випуклою лінійною комбінацією вершин багатогранника розв’язків, в яких цільова функція досягає оптимуму;
в) тільки в одній з вершин багатогранника розв’язків;
г) немає вірної відповіді.
	Вказати невірну відповідь на питання: Напрям зростання цільової функції z(x)=c1x1+c2x2	а	б	в	г	г
а)вказує вектор з координатами (c1; c2);
б) вказує вектор-градієнт цільової функції;
в)вказує вектор с координатами ;
г) вказує повна похідна цільової функції.
	Умови, які накладаються на невідомі величини задачі лінійного програмування і записуються у вигляді рівностей або нерівностей, утворюють:	а	б	в	г	б
а) розв’язок задачі;
б) область припустимих розв’язків;
в) канонічну форму моделі;
г) узагальнену форму моделі.
	Опорний план задачі лінійного програмування на максимум буде оптимальним, якщо у симплекс-таблиці всі оцінки Δ j будуть:	а	б	в	г	а
а) невід’ємні;
б)строго більше нуля;
в)дорівнювати нулю;
г) не більше нуля.
	Задача лінійного програмування на максимум має єдиний оптимальний план, якщо в індексному рядку симплекс-таблиці, що містить оптимальний план:	а	б	в	г	а
а) всі оцінки вільних змінних додатні;
б) серед оцінок є хоча б одна нульова оцінка, що відповідає вільній змінній;
в) всі оцінки вільних змінних від’ємні;
г) хоча б одна вільна змінна має від’ємну оцінку.
	Задача лінійного програмування не буде мати допустимих планів, якщо у оптимальному розв’язку відповідної М-задачі:	а	б	в	г	в
а) всі штучні змінні дорівнюють нулю;
б) хоча б одна штучна змінна дорівнює нулю;
в) хоча б одна штучна змінна відмінна від нуля;
г) немає вірної відповіді.
	Деякі допустимі плани Х* та У* будуть оптимальними планами відповідних взаємно двоїстих задач лінійного програмування, якщо:	а	б	в	г	а
а) z(Х*)=f(У*);
б) z(Х*)≥f(У*);
в) z(Х*)≤f(У*);
г) z(Х*)≠f(У*).
	Для задачі лінійного програмування на знаходження максимуму на деякому кроці отримали наступну симплекс-таблицю: Сбаз Хбаз Аі0   -6         Х1 Х2 Х3 Х4 Х5 Х6   Х3   -5/3 5/3   -1/3       Х5   -1/3 -2/3   1/3       Х6   -1 -9           Δj   -11/3 8/3   5/3     З даної таблиці випливає, що опорний розв’язок:	а	б	в	г	а
а)(0; 0; 12; 0; 8; 114) є оптимальним;
б)(11/3; 8/3; 0; 5/3; 0; 0) є оптимальним;
в)(0; 0; 12; 0; 8; 114) не є оптимальним;
г) (11/3; 8/3; 0; 5/3; 0; 0) не є оптимальним.
	Для задачі лінійного програмування на знаходження максимуму на деякому кроці отримали наступну симплекс-таблицю: Сбаз Хбаз Аі0   -6         Х1 Х2 Х3 Х4 Х5 Х6   Х3   -5/3 5/3   -1/3       Х5   -1/3 -2/3   1/3       Х6   -1 -9           Δj   -11/3 8/3   5/3     З даної таблиці випливає, що:	а	б	в	г	б
а)опорний план (0; 0; 12; 0; 8; 114) є оптимальним;
б)задача не має оптимального розв’язку;
в)необхідно виконати ще один крок симплекс-методу;
г) (11/3; 8/3; 0; 5/3; 0; 0) не є оптимальним.
	Для задачі лінійного програмування на знаходження максимуму на деякому кроці отримали наступну симплекс-таблицю: Сбаз Хбаз Аі0     -1   -1 Х1 Х2 Х3 Х4 Х5   Х1           -1   Х4       -3       Х2       -1       Δj             З даної таблиці випливає, що:	а	б	в	г	б
а)задача має альтернативні розв’язки;
б)опорний розв’язок (3; 2; 0; 1; 0) є оптимальним;
в) опорний розв’язок (0; 0; 1; 0; 1) є оптимальним;
г) опорний розв’язок (2; 1; 0; 1; 0) є оптимальним.
	Для задачі лінійного програмування на знаходження максимуму на деякому кроці отримали наступну симплекс-таблицю: Сбаз Хбаз Аі0     -1     Х1 Х2 Х3 Х4 Х5   Х1           -1   Х4       -3       Х2       -1       Δj             З даної таблиці випливає, що:	а	б	в	г	в
а)задача має єдиний оптимальний розв’язок;
б) опорний розв’язок (0; 0; 1; 0; 0) є оптимальним;
в)задача має альтернативний розв’язок;
г) опорний розв’язок (2; 1; 0; 1; 0) є оптимальним.
	Транспортна задача має допустимий план, якщо і тільки якщо:	а	б	в	г	б
а)
б)
в)
г)
	Транспортна задача задана наступною розподільчою таблицею   Дана модель є:	а	б	в	г	в
а) збалансованою;
б)закритою;
в)відкритою;
г) гармонійною.
	Транспортна задача задана наступною розподільчою таблицею   Дана модель є:	а	б	в	г	а
а)не збалансованою;
б)з рівними сумарними потребами і пропозиціями;
в)закритою;
г) збалансованою.
	У наступну транспортну таблицю             Пропо-зиція   10 2 2 10 11     12 10 7 15 9 20     5 4 14 16 5 18   попит           щоб опорний план був не вироджений необхідно:	а	б	в	г	б
а)додати перевезення 5 одиниць вантажу у клітинку (1;3);
б) додати перевезення 5 одиниць вантажу у клітинку (1;2);
в) додати перевезення 5 одиниць вантажу у клітинку (3;2);
г) додати перевезення 5 одиниць вантажу у клітинку (1;1);
	У наступну транспортну таблицю             Пропо-зиція   10 5 2 10 2 11     12 10 7 5 9 20     5 4 14 16 5 18   попит           щоб опорний план був не вироджений необхідно:	а	б	в	г	а
а) додати перевезення 10 одиниць вантажу у клітинку (2;4);
б) додати перевезення 10 одиниць вантажу у клітинку (3;3);
в) додати перевезення 10 одиниць вантажу у клітинку (3;2);
г) додати перевезення 10 одиниць вантажу у клітинку (2;1).
	При побудові опорного плану транспортної задачі в клітинці (1;1) тариф замінили на дуже велике число М. Такий метод застосовують, якщо:	а	б	в	г	б
а)необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача рівно а одиниць вантажу;
б) необхідно розв’язати задачу з забороною перевезення від першого постачальника до першого споживача;
в) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не більше а одиниць вантажу;
г) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не менше а одиниць вантажу.
	При побудові опорного плану транспортної задачі у клітинку (1;1) вносять а одиниць вантажу, а надалі її вважають вільною з як завгодно великим тарифом М. Такий метод застосовують, якщо:	а	б	в	г	а
а) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача рівно а одиниць вантажу;
б) необхідно розв’язати задачу з забороною перевезення від першого постачальника до першого споживача;
в) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не більше а одиниць вантажу;
г) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не менше а одиниць вантажу.
	При побудові опорного плану транспортної задачі зменшують запаси першого постачальника і потреби першого споживача на а одиниць вантажу, які додають до елемента х 11 в оптимальному розв’язку. Такий метод застосовують, якщо:	а	б	в	г	г
а) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача рівно а одиниць вантажу;
б) необхідно розв’язати задачу з забороною перевезення від першого постачальника до першого споживача;
в) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не більше а одиниць вантажу;
г) необхідно розв’язати задачу з перевезенням від першого постачальника до першого споживача не менше а одиниць вантажу.
	Оберіть пару розв’язків даної і двоїстої до неї задач:	а	б	в	г	б
а)Х=(29/7; 16/7; 0), У=(1/2; 1/2; 1/2);
б) Х=(29/7; 16/7; 0), У=(5/7; 0; 6/7);
в) Х=(26/7; 17/7; 1/2), У=(5/7; 0; 6/7);
г) Х=(26/7; 17/7; 1/2), У=(1/2; 1/2; 1/2).
	Оберіть пару розв’язків даної і двоїстої до неї задач:	а	б	в	г	а
а) Х=(29/7; 16/7; 0), У=(5/7; 0; 6/7);
б) Х=(26/7; 17/7; 1/2), У=(5/7; 0; 6/7);
в) Х=(29/7; 16/7; 0), У=(1/2; 1/2; 1/2);
г) Х=(26/7; 17/7; 1/2), У=(1/2; 1/2; 1/2).
	Оберіть пару розв’язків даної і двоїстої до неї задач:	а	б	в	г	б
а) Х=(29/7; 16/7; 0), У=(1/2; 1/2; 1/2);
б) Х=(29/7; 16/7; 0), У=(5/7; 0; 6/7);
в) Х=(26/7; 17/7; 1/2), У=(5/7; 0; 6/7);
г) Х=(26/7; 17/7; 1/2), У=(1/2; 1/2; 1/2).
	Оберіть пару розв’язків даної і двоїстої до неї задач:	а	б	в	г	а
а) Х=(29/7; 16/7; 0), У=(5/7; 0; 6/7);
б) Х=(26/7; 17/7; 1/2), У=(5/7; 0; 6/7);
в) Х=(29/7; 16/7; 0), У=(1/2; 1/2; 1/2);
г) Х=(26/7; 17/7; 1/2), У=(1/2; 1/2; 1/2).
	Оберіть задачу, двоїсту до даної:	а	б	в	г	г
а)
б)
в)
г)
	Оберіть задачу двоїсту до даної:	а	б	в	г	в
а)
б)
в)
г)

Классификация алгоритмов поиска

Под файлом будем понимать последовательность элементов, которые называются записями. С каждой записью r (i) связан ключ k (i), который используется для идентификации записи.

Алгоритм поиска – это алгоритм, который в заданном файле ищет запись с заданным ключом. Результатом работы алгоритма является сама запись или указатель на неё. Может оказаться, что поиск в файле по данному ключу закончится неудачей. Иногда в случае неудачного поиска нужно добавить новую запись с данным ключом.

Определение 1. Поиск, при котором файл располагается в основной памяти, называется внутренним поиском. Если же часть или весь файл располагается во внешней памяти, поиск называется внешним.

Определение 2. Поиск называется статическим, если содержимое файла не меняется. Динамический поиск предполагает, что в файл вставляются элементы или удаляются из него.

Алгоритмы поиска можно подразделить на:

 внешние и внутренние (по способу размещения данных в памяти);

 статические и динамические;

 основанные на сравнении ключей или на цифровых свойствах этих ключей (аналогично сортировкам сравнения и распределяющим сортировкам);

 использующие сами ключи или их образы.