metod_15.03.04_atppp_moas_2016 (1016590), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Его смысл выражается словами: совокупность, собрание, класс, набор, команда и т.д. Этот смыслпоясняется многочисленными примерами. Так, можно говорить о множествевсех учащихся 5-го класса, о множестве всех жителей Волгограда, о множествевсех натуральных чисел, о множестве корней данного уравнения. Основательтеории множеств немецкий математик Георг Кантор (1845–1918) так определилмножество – «многое, мыслимое как единое, целое».Множества обозначаются прописными буквами латинского алфавита А, В,С, …О предметах, составляющих множество, говорят, что они принадлежатэтому множеству или являются его элементами.

Множества, элементами которых являются числа, называются числовыми множествами.Множество может быть задано перечислением всех его элементов в произвольном порядке. Такое множество называют конечным. Мы будем рассматривать только конечные множества.Множество, в котором нуль элементов, называют пустым.Над множествами, как и над числами, производят операции. Рассмотрим некоторые из них: пересечение, объединение и разность.^ Пересечение множествВозьмем множество X, состоящее из букв а, б, в, г, д, и множествоY,состоящееизбуквг,д,е,ж:X = {а, б, в, г, д}, Y= {г, д, е, ж}.Эти множества имеют общие элементы гид.

Множества X и Y называются пересекающимися множествами. Множество общих элементов X и Y называют пересечением множеств X и Y и обозначают с помощью знака :Х Y={г, д} (рис.1).Пусть множество А = {1, 3, 5}. Множества А и X не имеют ни одного общего элемента. В таком случае множества А и X называются непересекающимися множествами. Пересечением множеств А и X является пустое множество:А  Х=  (рис. 2).Пересечением множеств называется новое множество, состоящееиз элементов, принадлежащих одновременно нескольким множествамРис.

1Рис. 2^ Объединение множествЕсли из элементов множеств X и Y составить новое множество, состоящееиз всех элементов этих множеств и не содержащее других элементов, то получится объединение множеств Х и Y, которое обозначают с помощью знака :X и Y= {а, б, в, г, д, е, ж) (рис. 4)Объединение множеств А и X не является пустым:А X = {1, 3, 5, а, б, в, г, д) (рис.

5).Объединением множеств называется новое множество, состоящее из элементов, принадлежащих хотя бы одному из множеств.Рис. 4Рис. 3РазностьРазность множеств X и Y — это множество всех элементов из X, не являющихся элементами из Y.Разность обозначают Х\Y = {а, б, в} (рис. 5).Рис. 5^ 1.3. Из истории кругов ЭйлераЧасто множество изображают кругами, эти круги обычно называют «кругами Эйлера» по имени величайшего математика Леонарда Эйлера.Леонард Эйлер (Euler) (1707 – 1783 г.г.) – математик, механик, физик иастроном.

По происхождению швейцарец, а работал в основном в Росси и в Германии. В 1726 году был приглашен в Петербургскую АН и в 1727 году переехалв Россию. В 1741 – 1766 годах работал в Берлине, член Берлинской АН. Эйлер –ученый необычайной широты интересов и творческой продуктивности. Авторсвыше 800 работ по математическому анализу, дифференциальной геометрии,теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др., оказавших значительное влияние на развитие науки.Одним из первых, кто разрабатывал метод решения задач с помощью кругов Эйлера, был выдающийся немецкий математик и философ Готфрид Вильгельм Лейбниц (1646 – 1716).

В его черновых набросках были обнаружены рисунки с такими кругами. Затем этот метод довольно основательно развил швей-царский математик Леонард Эйлер (1707 – 1783). Он долгие годы работал в Петербургской Академии наук. К этому времени относятся его знаменитые«Письма к немецкой принцессе», написанные в период с 1761 по 1768 год. В некоторых из этих «Писем…» Эйлер как раз и рассказывает о кругах, которые«очень подходят для того, чтобы облегчить наши размышления».

После Эйлераэтот же метод разрабатывал чешский математик Бернард Больцано (1781 – 1848).Только в отличие от Эйлера он рисовал не круговые, а прямоугольныесхемы. Методом кругов пользовался и немецкий математик Эрнест Шредер(1841 – 1902). Этот метод широко используется в книге «Алгебра логики». Нонаибольшего расцвета графические методы достигли в сочинениях английскогологика Джона Венна (1843 – 1923). С наибольшей полнотой этот метод изложеним в книге «Символическая логика», изданной в Лондоне в 1881 году.

В честьВенна вместо кругов Эйлера соответствующие рисунки называют иногда диаграммами Венна; в некоторых книгах их называют также диаграммами (или кругами) Эйлера – Венна.Решение задач, связанных с обработкой множеств.Задача 1. На олимпиаде по математике, в которой участвовало 62 человек,первую задачу решили 34 участника, вторую задачу – 32 участников, третью задачу – 31 участников, первую и вторую задачи – 18 участников, первую и третьюзадачи – 15 участников, вторую и третью задачи – 14 участников. Шесть участников не решили ни одной задачи. Сколько участников решили только по однойзадаче?Задача 2.

В студенческой группе английский язык изучают 22 студент,немецкий язык – 18 студентов, французский язык – 14 студентов, английский илинемецкий – 30 студентов, английский или французский – 29 студентов, немецкийили французский – 25 студента. Ровно два языка изучают 15 студентов. Сколькостудентов изучают только один иностранный язык?Задача 3. . На подготовительных курсах слушатели изучают иностранныеязыки: английский, немецкий и французский. Известно, что английский илинемецкий изучают 84 слушателя, английский или французский – 92, немецкийили французский – 67, английский и немецкий – 12, английский и французский– 9, немецкий и французский – 6 слушателей.

Сколько слушателей изучают английский язык?Задача 4. На подготовительных курсах слушатели изучают иностранныеязыки : английский, немецкий и французский. Известно, что английский илинемецкий изучают 82 слушателя, английский или французский – 90, немецкийили французский – 65, английский и немецкий-– 24, английский и французский– 11, немецкий и французский – 8 слушателей. Сколько слушателей изучаютнемецкий язык?Задача 5. На подготовительных курсах слушатели изучают иностранныеязыки : английский, немецкий и французский. Известно, что английский илинемецкий изучают 84 слушателя, английский или французский – 92, немецкийили французский – 67, английский и немецкий-32, английский и французский –9, немецкий и французский – 6 слушателей.

Сколько слушателей изучают французский язык?Занятие 5 – практическое занятие № 7 (интерактивное). Защита домашнейработы по теории множеств.Занятие проводится в интерактивной форме по методике «семинар-конференция).Основы комбинаторикиОсновные правила комбинаторики.Комбинаторика (комбинаторный анализ) – раздел дискретной математики,в котором изучаются объекты, составленные из элементов конечных множеств.Одним из основных видов комбинаторных задач являются перечислительные задачи.

В этих задачах речь идет о выборе определенного количества элементов изнекоторого множества с соблюдением тех или иных условий и требуется подсчитать число способов, которыми можно осуществить такой выбор.Напомним некоторые обозначения из теории множеств.2AA– множество всех подмножеств множества A.– число элементов (мощность) конечного множества A.A1  A2  An– прямое (декартово) произведение множеств A1 , A2 ,, An .Элементами декартова произведения являются последовательности вида x1 , x2 ,, xn  ,где x1  A1 , x2  A2 ,, xn  An . При A1  A2  An  A получаетсядекартова степень A n множества A.

Если элементы множества A считать буквами алфавита, то элементы декартовой степени можно рассматривать как слова,они в этом случае записываются в виде x1 x2  xn .Буквой E будем обозначать двухэлементное множество 0,1 .Символомотмечается конец доказательства.Решение комбинаторных задач1. Имеется n1 разных книг одного автора, n2 – второго и n3 – третьего.Каким числом способов можно выбратьа) одну книгу?б) две книги разных авторов?в) три книги разных авторов?2. Каким числом способов можно заполнить анкету, содержащую n вопросов, если на каждый вопрос можно ответитьа) “да” или “нет”?б) “да”, “нет”, “не знаю”?3. Сколько слов длины n можно составить, если в алфавите q букв? Сколькосреди них палиндромов (слов, читающихся одинаково слева направо и справаналево)?4.

Сколько матриц с m строками и n столбцами можно составить изэлементов 0 и 1 ?5. Сколько слов длины n в q–буквенном алфавите, в которых любые двесоседние буквы различны?6. Каким числом способов можно на обычной шахматной доске разместитьбелую и черную ладьи так, чтобы они не атаковали друг друга?Занятие 2 – лекция № 7. Различные комбинации элементов в комбинаторике.Перестановки и сочетанияВ простейших комбинаторных задачах требуется подсчитать число способов выбрать k элементов из n–элементного множества.

То, что получается врезультате выбора, называется выборкой из n по k или (n,k)–выборкой.Понятие выборки отличается от понятия подмножества. Первое отличиесостоит в том, что в выборках может допускаться повторение элементов. Этоозначает, что в выборку может входить несколько экземпляров одного и того жеэлемента. В этом случае говорят, что рассматриваются выборки с повторениями.Другое отличие – выборки могут быть упорядоченными или неупорядоченными.Упорядоченность означает, что выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, считаются различными.

Если же такиевыборки считаются одинаковыми, то говорят, что рассматриваются неупорядоченные выборки. Упорядоченные выборки называют перестановками (или размещениями), неупорядоченные – сочетаниями. Таким образом, имеется четыреосновных типа выборок: перестановки (без повторений), перестановки с повторениями, сочетания (без повторений) и сочетания с повторениями.Подсчитаем число выборок каждого типа.

Множеством, из которого делается выбор, будем считать множество чисел I n  1,2,, n .Перестановки с повторениями. Перестановки с повторениями из n поk – это последовательности длины k, состоящие из элементов множества I n , тоесть попросту элементы множества I nk . Из теоремы 1 поэтому следуетТеорема 3. Число (n,k)– перестановок с повторениями равно n k .Перестановки. Обозначим число перестановок из n по k через Pn, k .Теорема 4.Pn, k n!n  k !.Д о к а з а т е л ь с т в о. В качестве первого элемента перестановки можетбыть выбран любой из n элементов множества I n . Поскольку повторения недопустимы, второй элемент можно выбрать n  1 способами, третий n  2 способами и т.д. Применяя обобщенное правило произведения, получаемPn, k  n n  1 n  k  1 n!.n  k !В частности, при k  n получается формула для числа перестановок всех nэлементов:Pn, n  n!Сочетания.

Сочетания из n по k, то есть неупорядоченные выборки безповторений, это просто k–элементные подмножества n–элементного множества. n kЧисло (n,k)–сочетаний обозначается через Cnk или   .Теорема 5. nn!.  k  k ! n  k  !Д о к а з а т е л ь с т в о. Выписывая элементы (n,k)–сочетания в некоторомпорядке, получаем (n,k)–перестановку. Поскольку k элементов можно упорядочить k ! способами , то из каждого сочетания можно образовать k ! различных n k n kперестановок.

Из всех   сочетаний таким образом получится k !  перестановок. Ясно, что каждая перестановка будет при этом получена точно один раз. n kСледовательно, Pn, k  k !  . Применяя формулу для числа перестановок, получаем утверждение теоремы. В качестве простейшего примера применения формулы для числа сочетаний рассмотрим следующую задачу.Задача 1. Определить число слов длины n в алфавите E, содержащих в точности k единиц.Р е ш е н и е .

Характеристики

Список файлов учебной работы