Что такое выборка в комбинаторике? объяснить различие между размещениями и сочетаниями, выборками с повторениями и без. привести примеры

  • ID: 38793 
  • 4 страницы

Фрагмент работы:

Билет №8. Факультет ИВТ (ДО) Курс 1 Семестр 2

Что такое выборка в комбинаторике? Объяснить различие между размещениями и сочетаниями, выборками с повторениями и без. Привести примеры.

Ответ:

Выборкой объема из элементов множества = {1, 2, 3, ..., n}, [image] называется набор, состоящий из элементов множества .

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

Пример. Пусть задано множество [image].

[image]

[image]

[image]

[image]

Какие существуют классические задачи, для решения которых применяются графы (краткая характеристика)? Что позволяет найти алгоритм Дейкстры?

Ответ:

К классическим задачам, решаемым с применением графов, относится задача коммивояжера. В ней требуется осуществить обход всех населенных пунктов, посещая каждый по разу, так, чтобы пройденное расстояние было минимальным. Также к классическим задачам относится задача о ранце – необходимо уложить в ранец максимальное количество вещей исходя из того, что общий вес вещей ограничен. Задача нахождения минимального остова возникает при проектировании линий электропередач, трубопроводов, дорог и т.д., когда требуется заданные центры (вершины графа) соединить некоторой системой каналов связи таким образом, чтобы любые два центра были связаны непосредственно или через другие каналы, и чтобы общая длина (стоимость) каналов связи была минимальной. С помощью графов решается задача о нахождении кратчайшего пути из одного пункта в другой.

Алгоритм Дейкстры находит кратчайшее расстояние от одной фиксированной вершины до другой и указывает сам путь, длина которого равна этому расстоянию.