Частное Учебное Заведение Институт Делового Администрирования Private Educational Institution Institute of Business Managment

8. Материал семинарских занятий 8.1 Введение в комбинаторику При изучении курса математической статистики приходится использовать методы одного из разделов математики, который хотя формально и не относится к высшей, вузовской математике, но, к сожалению, не изучается в средней школе. Этот раздел – комбинаторика, “наука о способах подсчета вариантов”. Эта наука имеет тот же, примерно 300 летний возраст, что и сама статистика. Комбинаторика – сверстница теории вероятностей, теоретического фундамента прикладной статистики. Как и в древней, в современной статистике невозможно обойтись без навыков просчитывать в уме или, по крайней мере, быстро, по простым формулам, варианты событий, размещений предметов, значений величин и т.п. Замечание о расчетах в уме сделано не случайно. Знание основ комбинаторики позволит хотя бы оценивать числа вариантов и соотношения между ними также “профессионально” как и делаете это вы, оценивая возраст встреченного человека. В этом плане комбинаторику можно называть “логикой вариантов” и это будет вполне резонно ­– в этой науке больше чистой логики, чем математики. Для демонстрации необходимости знаний комбинаторики и в качестве первой практической задачи рассмотрим несколько простых, практических вопросов.  Вам, очевидно, известно, что внутренний, “машинный” язык компьютера люди построили по образу и подобия человеческого языка: буквы, слова, предложения. Обстоятельства надежности записи и чтения на этом языке привели к решению сделать компьютерный язык предельно бедным. В нем всего две буквы (“0” и “1”, “+ " и “–”, “да” и “нет”, ­– в зависимости от физического процесса записи), всегда 8 букв в слове, отсутствует пробел между словами (это была бы третья буква). И вот возникает вопрос ­– а сколько вариантов у машинного слова, т.е. у одного байта? Еще проще – если одним байтом записывать числа, то сколько положительных целых чисел можно охватить 1 байтом? В поисках ответа можно терпеливо выписывать все возможные варианты слов из 8 нулей и единиц: 00000000, 00000001, 00000010 и т.д. до 11111111. Но ведь это долго и надо быть уверенным, что ничего не пропустили! Так вот – законы комбинаторики позволяют мгновенно ­решить эту задачу и получить ответ – вариантов записи байта ровно 256. Это чисто практический вопрос – ведь компьютер с возможностью считать в целых числах от –128 до 127 никто не купит. Ну, если целые числа хранить в 2-х машинных словах, в 2-х байтах или в 16 “разрядах”.? Уж это новое число вариантов никто не согласится вычислять простым перебором! А ответ комбинаторики все тот же прост – в этом случае есть возможность работать с целыми числами от –32768 до 32767. Оказывается, что эти числа не надо запоминать, поскольку алгоритм их расчетов очень прост и посилен человеку, осилившему только арифметику.  Рассмотрим второй пример решения практического вопроса с использованием правил комбинаторики. Пусть решается вопрос об установлении проводной связи между 25 предприятиями фирмы по следующему принципу – каждое предприятие должно иметь отдельный канал связи со всеми остальными. Сколько таких каналов придется установить в фирме? Для решения вопроса можно нарисовать выпуклый 25–угольник и провести в нем все диагонали, пересчитав в конце их число и не забыв добавить число сторон. Человек, знающий комбинаторику, во-первых, не сделает ошибки –2524=600 каналов. Во-вторых, он мгновенно укажет верный ответ – всего требуется 300 каналов. Комментарии излишни… Для освоения наиболее популярных применений комбинаторики нам потребуется использовать, по крайней мере, два ее основных понятия ­– перестановки и сочетания. Перестановками называют операции над упорядоченным рядом из n различных объектов, в процессе которых “списочный состав” ряда не изменяется, но “места” объектов в этом ряду изменяются от варианта к варианту. Не будем тратить время на обоснование расчетной формулы для произвольного n, а попробуем найти число перестановок в ряду из 1, 2 и 3 предметов. Воспользуемся для этого простенькой схемой: n=1 A 1 вариант. n=2 AB BA 12= 2 варианта. n=3 ABC ACB BCA BAC CAB CBA 123= 6 вариантов. Можно доказать строго, что в общем случае число перестановок в ряду из n элементов составит {8–1} Сочетаниями называют операции над множеством из n различных объектов, в процессе которых образуют подмножества из k элементов, взятых из исходного множества, так, чтобы варианты подмножеств отличались друг от друга хотя бы одним элементом. Опустим доказательство формулы для расчета числа сочетаний из n по k в общем виде и приведем лишь примеры для числа сочетаний из 3 по 2 и из 5 по 3.  Элементы исходного множества A, B, C. Варианты подмножеств: AB, AC, BC – всего три.  Элементы исходного множества A, B, C, D, E. Варианты подмножеств: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE – всего десять. В общем случае число вариантов сочетаний или просто – число сочетаний из n по k определяется по формуле = {8–2} Существует еще один способ вычисления числа сочетаний из n по k – с использованием коэффициентов в развернутой форме бинома (p+q)n. В самом деле, например, при n=3 коэффициенты при степенях разложения составляют 1, 3, 3, 1 – а это и есть сочетания из 3 по 0, 1, 2, 3 и 4 элементов. Известна также схема простого расчета биномиальных коэффициентов, которая носит названия треугольника Паскаля: Для n 1 1 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 1 7 21 35 35 21 7 1 7 Первый элемент любого основания равен 1, второй – номеру основания, а все последующие – сумме двух "вышестоящих".

Похожие:

	Psychological mechanisms of rolegram of the professor of a higher... В статье предпринята попытка определить и раскрыть механизмы формирования ролевого репертуара преподавателя высшей педагогической...		Учебной дисциплины «Управление продажами» дополнительной профессиональной... В основу курса положен реальный опыт работы автора на протяжении более 15 лет в иностранных fmcg компаниях и теоретические работы...
	Учебной дисциплины «Трейд-маркетинг» дополнительной профессиональной... Курс также акцентирует внимание слушателей на основных инструментах трейд-маркетинга. В основу курса положен опыт работы автора на...		Франко-Российский институт делового администрирования Меняется ли Ваша жизнь, если дорогу перебегает черная кошка? Верите ли Вы в удачу, если на экзамене попался билет под номером 13?...
	Радюхина Наталия Юрьевна Учебное заведение: гоу сош №684 «Берегиня»... Учебное заведение: гоу сош №684 «Берегиня» Московского района г. Санкт-Петербурга		Программа по формированию навыков безопасного поведения на дорогах... Образование (учебное заведение, год окончания, специальность по диплому): Владимирский гос педагогический институт имени П. И. Лебедева-Полянского,...
	Исследование возглавлялось директором Norlan Norton Institute Дэвидом... До недавнего времени такой системы не существовало вообще, пока Balanced Scorecard не открыла новые перспективы и не изменила воззрения...		«московский финансово-правовой институт» «moscow institute of finance and law» Ноу впо "Московский финансово-правовой институт" (далее институт), порядок приема на работу и увольнения работников, основные права...
	Программа по формированию навыков безопасного поведения на дорогах... Алла Ганнадьевна Дементьева – мва, кандидат экономических наук, зам декана факультета международного бизнеса и делового администрирования,...		Повторение раздела «Фонетика» Муниципальное общеобразовательное бюджетное учебное заведение «Восточненская сош»
	Учебное заведение Самостоятельные занятия (работа над коллективными и индивидуальными проектами, курсовые работы)		Инструкция пользователя Skype for Business Для того что бы установить и настроить клиент Skype For Business на вашем пк, вы можете воспользоваться инструкцией на сайте Дирекции...
	Одобрено кафедрой «Государственно-частное партнерство», протокол... В. С. Осипов – к э н., старший научный сотрудник сектора «Государственно-частное партнерство» фгбун институт экономики ран		Технологический университет таджикистана факультет делового администрирования... Цели и задачи, основные направления воспитательной работы в современной школе. Создание и развитие воспитательной системы школы....
	Проекта Учебное заведение Муниципальное бюджетное общеобразовательное учреждение «Средняя образовательная школа №1» г. Тарко-Сале, Пуровского...		Первое высшее техническое учебное заведение россии Направление подготовки: 190600 Эксплуатация транспортно-технологических машин и комплексов