http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=KrotserВикиконспекты - Вклад участника [ru]2026-06-11T20:00:07ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=24321Сортировка выбором2012-06-07T12:22:35Z<p>Krotser: /* Реализация */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
Вариант 1.<br />
SelectionSort(a)<br />
for i = 0 to n - 2<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if a[j] < a[min]<br />
min = j;<br />
swap(a[i], a[min]);<br />
<br />
Вариант 2.<br />
SelectionSort(a)<br />
for i = 0 to n - 2<br />
for j = i + 1 to n - 1<br />
if a[i] > a[j]<br />
swap(a[i], a[j]);<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=24319Сортировка выбором2012-06-07T12:22:18Z<p>Krotser: /* Реализация */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
Вариант 1.<br />
SelectionSort(a)<br />
for i = 0 to n - 2<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if a[j] < a[min]<br />
min = j;<br />
swap(a[i], a[min]);<br />
// Массив x отсортирован<br />
<br />
Вариант 2.<br />
SelectionSort(a)<br />
for i = 0 to n - 2<br />
for j = i + 1 to n - 1<br />
if a[i] > a[j]<br />
swap(a[i], a[j]);<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=24318Сортировка выбором2012-06-07T12:16:51Z<p>Krotser: /* Реализация */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
Вариант 1.<br />
// Входной массив a, содержащий n элементов.<br />
for i = 0 to n - 2<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if a[j] < a[min]<br />
min = j;<br />
swap(a[i], a[min]);<br />
// Массив x отсортирован<br />
<br />
Вариант 2.<br />
for i = 0 to n - 2<br />
for j = i + 1 to n - 1<br />
if a[i] > a[j]<br />
swap(a[i], a[j]);<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=24317Сортировка выбором2012-06-07T12:13:50Z<p>Krotser: /* Реализация */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
Вариант 1.<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 2<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
Вариант 2.<br />
for i = 0 to n - 2<br />
for j = i + 1 to n - 1<br />
if x[i] > x[j]<br />
swap(x[i], x[j]);<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=24287Сортировка выбором2012-06-07T07:52:55Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
Вариант 1.<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 2<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
Вариант 2.<br />
for i = 0 to n - 2<br />
for j = i + 1 to n - 1<br />
if x[i] > x[j]<br />
swap(x[i], x[j]);<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22631Сортировка выбором2012-05-22T07:44:08Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22630Сортировка выбором2012-05-22T07:41:33Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом, будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22629Сортировка выбором2012-05-22T07:40:59Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом, будет получен массив отсортированный по неубыванию.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элемент<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элемент<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элемент<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22593Сортировка выбором2012-05-20T20:14:05Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
1. Находим номер минимального элемента из текущего массива.<br />
<br />
2. Меняем минимальный элемент с первым элементом массива.<br />
<br />
3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>5</tex> элементов <tex>5, 4, 1, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| Массив<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим минимальный элемент {{---}} '''1''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент текущего массива<br />
|-<br />
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Находим минимальный элемент {{---}} '''2''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент текущего массива<br />
|-<br />
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим минимальный элемент {{---}} '''3''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент текущего массива<br />
|-<br />
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''<br />
|style="background-color:#FFF;padding:2px 10px"| Находим минимальный элемент {{---}} '''4''' <br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент текущего массива<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22588Сортировка выбором2012-05-20T19:48:11Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
1. Находим номер минимального элемента из текущего массива.<br />
<br />
2. Меняем минимальный элемент с первым элементом массива.<br />
<br />
3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
{| style="background-color:#CCC;margin:0.5px"<br />
!style="background-color:#EEE"| До<br />
!style="background-color:#EEE"| После<br />
!style="background-color:#EEE"| Описание шага<br />
|-<br />
|colspan=3|''Первый проход (проталкиваем второй элемент — '''''2''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''5 2''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 5''' 4 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Алгоритм сравнивает второй элемент с первым и меняет их местами.<br />
|-<br />
|colspan=3|''Второй проход (проталкиваем третий элемент — '''''4''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''5 4''' 3 1 <br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 5''' 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Сравнивает третий со вторым и меняет местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 4''' 5 3 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
|-<br />
|colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''5 3''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 4 '''3 5''' 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''4 3''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 4''' 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 3''' 4 5 1<br />
|style="background-color:#FFF;padding:2px 10px"| Второй и первый отсортированы, swap не требуется<br />
<br />
|-<br />
|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''1''''')''<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''5 1'''<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 4 '''1 5'''<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет пятый и четвертый местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''4 1''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 3 '''1 4''' 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет четвертый и третий местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''3 1''' 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| 2 '''1 3''' 4 5 <br />
|style="background-color:#FFF;padding:2px 10px"| Меняет третий и второй местами<br />
|-<br />
|style="background-color:#FFF;padding:2px 10px"| '''2 1''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| '''1 2''' 3 4 5<br />
|style="background-color:#FFF;padding:2px 10px"| Меняет второй и первый местами. Массив отсортирован.<br />
|}<br />
<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22585Сортировка выбором2012-05-20T19:21:14Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]]<br />
<br />
1. Находим номер минимального элемента из текущего массива.<br />
<br />
2. Меняем минимальный элемент с первым элементом массива.<br />
<br />
3. Если текущий массив пуст, то данный массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из текущего массива.<br />
<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for i = 0 to n - 1<br />
min = i;<br />
for j = i + 1 to n - 1<br />
if x[j] < x[min]<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22565Сортировка выбором2012-05-20T12:16:43Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|240px|Пример работы алгоритма для последовательности из 6 элементов]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22564Сортировка выбором2012-05-20T12:16:30Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|256px|Пример работы алгоритма для последовательности из 6 элементов]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22560Сортировка выбором2012-05-20T12:11:26Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|256px|Пример работы алгоритма]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22559Сортировка выбором2012-05-20T12:10:11Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|280px|Пример работы алгоритма]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Selection_sort.png&diff=22558Файл:Selection sort.png2012-05-20T12:09:28Z<p>Krotser: загружена новая версия «Файл:Selection sort.png»: Пошаговый пример сортировки выбором</p>
<hr />
<div>Пример сортировки выбором</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22556Сортировка выбором2012-05-20T12:05:23Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|300px|Пример работы алгоритма]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
'''Пример'''<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Selection_sort.png&diff=22554Файл:Selection sort.png2012-05-20T12:03:11Z<p>Krotser: загружена новая версия «Файл:Selection sort.png»: Пример работы сортировки выбором</p>
<hr />
<div>Пример сортировки выбором</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22551Сортировка выбором2012-05-20T11:54:15Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|150px|Пример работы алгоритма]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
=== Пример ===<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22550Сортировка выбором2012-05-20T11:52:51Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
[[file:Selection_sort.png|thumb|200px|Пример]]<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
=== Пример ===<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22549Сортировка выбором2012-05-20T11:50:44Z<p>Krotser: /* Пример */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
== Пример ==<br />
[[file:Selection_sort.png|thumb|200px|Пример]]<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22548Сортировка выбором2012-05-20T11:47:20Z<p>Krotser: /* Пример */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.<br />
<br />
Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент. <br />
<br />
[[Файл:Selection_sort.png]]<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Selection_sort.png&diff=22547Файл:Selection sort.png2012-05-20T11:43:38Z<p>Krotser: Пример сортировки выбором</p>
<hr />
<div>Пример сортировки выбором</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22543Сортировка выбором2012-05-20T11:05:27Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
== Пример ==<br />
<br />
Пусть дана последовательность из 5 элементов.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22542Сортировка выбором2012-05-20T11:03:06Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
0. Назовем элементы массива списком.<br />
<br />
1. Находим номер минимального элемента из текущего списка.<br />
<br />
2. Меняем минимальный элемент с первым элементом списка.<br />
<br />
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22541Сортировка выбором2012-05-20T10:49:28Z<p>Krotser: /* Задача сортировки */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по неубыванию.<br />
<br />
== Алгоритм ==<br />
<br />
1. Находим номер минимального элемента из массива.<br />
<br />
2. Меняем минимальный элемент с первым.<br />
<br />
3. Новый массив начинается со следующего элемента, так как все предыдущие элементы уже отсортированы. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22540Сортировка выбором2012-05-20T10:47:59Z<p>Krotser: /* Задача сортировки */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел. <br />
<br />
'''На выходе''' отсортированная последовательность по возрастанию.<br />
<br />
== Алгоритм ==<br />
<br />
1. Находим номер минимального элемента из массива.<br />
<br />
2. Меняем минимальный элемент с первым.<br />
<br />
3. Новый массив начинается со следующего элемента, так как все предыдущие элементы уже отсортированы. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22539Сортировка выбором2012-05-20T10:46:15Z<p>Krotser: /* Задача сортировки */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' отсортированная последовательность (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
1. Находим номер минимального элемента из массива.<br />
<br />
2. Меняем минимальный элемент с первым.<br />
<br />
3. Новый массив начинается со следующего элемента, так как все предыдущие элементы уже отсортированы. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22532Сортировка выбором2012-05-20T09:49:54Z<p>Krotser: /* Алгоритм */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' перестановка данной последовательности (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
1. Находим номер минимального элемента из массива.<br />
<br />
2. Меняем минимальный элемент с первым.<br />
<br />
3. Новый массив начинается со следующего элемента, так как все предыдущие элементы уже отсортированы. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22280Сортировка выбором2012-05-13T12:38:42Z<p>Krotser: /* Литература */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' перестановка данной последовательности (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
Шаг 1. Выбираем минимальный элемент из текущего массива.<br />
<br />
Шаг 2. Ставим его на первое место.<br />
<br />
Шаг 3. Новый массив начинается со следующего элемента. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22279Сортировка выбором2012-05-13T12:37:21Z<p>Krotser: /* Литература */</p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' перестановка данной последовательности (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
Шаг 1. Выбираем минимальный элемент из текущего массива.<br />
<br />
Шаг 2. Ставим его на первое место.<br />
<br />
Шаг 3. Новый массив начинается со следующего элемента. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сортировки]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22278Сортировка выбором2012-05-13T12:35:04Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' перестановка данной последовательности (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
Шаг 1. Выбираем минимальный элемент из текущего массива.<br />
<br />
Шаг 2. Ставим его на первое место.<br />
<br />
Шаг 3. Новый массив начинается со следующего элемента. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]<br />
<br />
== Литература ==<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика, алгоритмы и структуры данных]]<br />
[[Категория: Сортировка]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=22277Дискретная математика, алгоритмы и структуры данных2012-05-13T12:27:10Z<p>Krotser: /* Сортировка */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Степень отношений]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Композиция отношений|Композиция отношений. Обратное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Транзитивный остов]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[КНФ]]<br />
*[[Полином Жегалкина]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Сокращенная и минимальная ДНФ]]<br />
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<br />
<br />
== Алгоритмы сжатия ==<br />
*[[Алгоритм Хаффмана]]<br />
*[[Алгоритм LZW]]<br />
*[[Алгоритмы LZ77 и LZ78]]<br />
*[[Преобразование Барроуза-Уиллера]]<br />
*[[Обратное преобразование Барроуза-Уиллера]]<br />
*[[Преобразование MTF]]<br />
*[[Расстояние Хэмминга]]<br />
*[[Избыточное кодирование, код Хэмминга]]<br />
*[[Неравенство Крафта]]<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Комбинаторика ==<br />
*[[Комбинаторные объекты]]<br />
*[[Лексикографический порядок]]<br />
*[[Формула включения-исключения]]<br />
*[[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
*[[Получение номера по объекту]]<br />
*[[Получение объекта по номеру]]<br />
*[[Получение следующего объекта]]<br />
*[[Коды Грея]]<br />
*[[Коды Грея для перестановок]]<br />
*[[Цепные коды]]<br />
*[[Правильные скобочные последовательности]]<br />
*[[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
*[[Таблица инверсий]]<br />
*[[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
*[[Теорема Кэли]]<br />
*[[Матричное представление перестановок]]<br />
*[[Задача о минимуме/максимуме скалярного произведения]]<br />
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
*[[Производящая функция]]<br />
<br />
== [[Динамическое программирование]] ==<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула Байеса]]<br />
*[[Формула полной вероятности]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Задача о двух конвертах]]<br />
<br />
== [[Марковская цепь|Марковские цепи]] ==<br />
<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Саморасширяющийся массив]]<br />
* [[Массив с увеличением/уменьшением размера]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Список]]<br />
* [[Персистентный стек]]<br />
* [[Персистентный дек]]<br />
<br />
== Приоритетные очереди ==<br />
<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[Анализ реализации с ранговой эвристикой | Анализ реализации с ранговой эвристикой]]<br />
<br />
== Деревья поиска ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Splay-дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Рандомизированное бинарное дерево поиска]]<br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеширование]]<br />
* [[Открытое и закрытое хеширование]]<br />
* [[Поиск свободного места при закрытом хешировании]]<br />
* [[Хеширование кукушки]]<br />
* [[Двойное хеширование]]<br />
* [[Перехеширование. Амортизационный анализ]]<br />
* [[Фильтр Блума]]<br />
* [[Универсальное семейство хеш-функций]]<br />
<br />
== Сортировка ==<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Сортировка вставками]]<br />
* [[Сортировка подсчетом]]<br />
* [[Сортировка подсчетом сложных объектов]]<br />
* [[Цифровая сортировка]]<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-й порядковой статистики за линейное время]]<br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
* [[Быстрая сортировка]]<br />
<br />
== [[Сортирующие сети]] ==<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Вещественный двоичный поиск]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<br />
* [[Фундаментальные циклы графа]]<br />
* [[Дерево, эквивалентные определения]]<br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* Следствия теоремы Хватала: <br />
** [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Двойственный граф планарного графа]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]<br />
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]<br />
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]<br />
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]<br />
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм A*]]<br />
* [[Алгоритм Джонсона]]<br />
<br />
== Остовные деревья ==<br />
* [[Лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
== Задача о паросочетании ==<br />
* [[Теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Лемма о сложении потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
<br />
== Поиск подстроки в строке ==<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Автомат для поиска образца в тексте]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
<br />
== Словарные структуры данных ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
<br />
=== Суффиксный массив ===<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Метод двоичного подъема]]<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
<br />
== Матроиды ==<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Жадный алгоритм поиска базы минимального веса]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Лемма о паросочетании в графе замен]]<br />
* [[Лемма о единственном паросочетании в графе замен]]<br />
* [[Граф замен для двух матроидов]]<br />
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
* [[Теорема Эдмондса-Лоулера]]<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
==Теория расписаний==<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22276Сортировка выбором2012-05-13T12:22:27Z<p>Krotser: </p>
<hr />
<div>'''Сортировка выбором''' (англ. '''selection sort''') - это простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).<br />
<br />
== Задача сортировки ==<br />
'''На входе''' последовательность из <tex>n</tex> чисел (<tex>x_1, x_2, ..., x_n</tex>). <br />
<br />
'''На выходе''' перестановка данной последовательности (<tex>{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}</tex>) таким образом, что для ее членов выполняется <tex>{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}</tex>.<br />
<br />
== Алгоритм ==<br />
<br />
Шаг 1. Выбираем минимальный элемент из текущего массива.<br />
<br />
Шаг 2. Ставим его на первое место.<br />
<br />
Шаг 3. Новый массив начинается со следующего элемента. Перейти к шагу 1, если массив не пустой.<br />
<br />
== Реализация ==<br />
// Входной массив x, содержащий n элементов.<br />
for (i = 0 to n - 1)<br />
int min = i;<br />
for (j = i + 1 to n - 1)<br />
if (x[j] < x[min])<br />
min = j;<br />
swap(x[i], x[min]);<br />
// Массив x отсортирован</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Krotser&diff=22274Участник:Krotser2012-05-13T12:03:29Z<p>Krotser: </p>
<hr />
<div>Сергей Кротов, группа 1537<br />
<br />
*[[Неравенство Макмиллана]]<br />
<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
<br />
*[[Сортировка выбором]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC&diff=22263Сортировка выбором2012-05-13T11:36:50Z<p>Krotser: Новая страница: «== Редактирование ==»</p>
<hr />
<div>== Редактирование ==</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0,_%D0%94%D0%9F_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0%D0%BC&diff=16725Задача коммивояжера, ДП по подмножествам2012-01-14T23:19:45Z<p>Krotser: /* Динамическое программирование по подмножествам (по маскам) */</p>
<hr />
<div>'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?<br />
<br />
== Варианты решения ==<br />
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.<br />
<br />
Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.<br />
<br />
==== Перебор перестановок ====<br />
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.<br />
<br />
==== Динамическое программирование по подмножествам (по маскам) ====<br />
<br />
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.<br />
<br />
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G=(V,E)</tex> <tex> N </tex><br />
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.<br />
<br />
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.<br />
<br />
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.<br />
<br />
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).<br />
<br />
*Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex> и <tex>mask = 0</tex>). <br />
*Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат.<br />
*Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).<br />
<br />
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.<br />
<br />
Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.<br />
<br />
== Реализация ==<br />
//Все переменные используются из описания алгоритма, inf = бесконечность<br />
d[0][0] = 0;<br />
for i = 0 to n - 1<br />
for mask = 0 to mask = 2 ** n - 1<br />
for j = 0 to n - 1<br />
if j-ий бит mask == 1<br />
if w(i, j) существует<br />
d[i][mask] = min(d[i][mask], d[j][mask - 2 ** n] + w(i, j);<br />
else<br />
d[i][mask] = inf;<br />
print d[0][2 ** n - 1];<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]<br />
<br />
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]<br />
<br />
== Литература ==<br />
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3<br />
<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0,_%D0%94%D0%9F_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0%D0%BC&diff=16445Задача коммивояжера, ДП по подмножествам2012-01-13T01:41:10Z<p>Krotser: </p>
<hr />
<div>'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?<br />
<br />
== Варианты решения ==<br />
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.<br />
<br />
Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.<br />
<br />
==== Перебор перестановок ====<br />
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.<br />
<br />
==== Динамическое программирование по подмножествам (по маскам) ====<br />
<br />
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.<br />
<br />
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G=(V,E)</tex> <tex> N </tex><br />
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.<br />
<br />
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.<br />
<br />
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.<br />
<br />
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).<br />
<br />
Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex>, <tex>mask = 0</tex>). Для остальных состояний перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).<br />
<br />
То есть, <tex>d[i][mask]</tex> считается по следующему правилу:<br />
<br />
<tex> d[i][mask] =<br />
\begin{cases}<br />
0, &\text{if }i = 0\text{ and }mask = 0 \\<br />
\min\limits_{j:\text{ }mask_j=1,\text{ }(i, j) \in E} \begin{Bmatrix} w(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\<br />
\infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and } j:\text{ }mask_j=1,\text{ }(i, j) \notin E<br />
\end{cases}<br />
</tex><br />
<br />
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.<br />
<br />
Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.<br />
<br />
== Реализация ==<br />
//Все переменные используются из описания алгоритма, inf = бесконечность<br />
d[0][0] = 0;<br />
for i = 0 to n - 1<br />
for mask = 0 to mask = 2 ** n - 1<br />
for j = 0 to n - 1<br />
if j-ий бит mask == 1<br />
if w(i, j) существует<br />
d[i][mask] = min(d[i][mask], d[j][mask - 2 ** n] + w(i, j);<br />
else<br />
d[i][mask] = inf;<br />
print d[0][2 ** n - 1];<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]<br />
<br />
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]<br />
<br />
== Литература ==<br />
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3<br />
<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=16438Неравенство Макмиллана2012-01-13T01:27:17Z<p>Krotser: </p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.<br />
<br />
Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N \in \mathbb N</tex>: <tex>(P_1+P_2+...P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.<br />
<br />
Вот пример для однозначного кода со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<br />
<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые различны (соответствует определению однозначности).<br />
<br />
Подставим <tex>a=b=\frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{n_i}</tex> получим <tex>2^{-n_i}</tex>. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N \le N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[[Неравенство Крафта]]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=16434Неравенство Макмиллана2012-01-13T01:12:21Z<p>Krotser: /* Неравенство Макмиллана */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.<br />
<br />
Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N \in \mathbb N</tex>: <tex>(P_1+P_2+...P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.<br />
<br />
Вот пример для однозначного кода со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<br />
<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые различны (соответствует определению однозначности).<br />
<br />
Подставим <tex>a=b=\frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{n_i}</tex> получим <tex>2^{-n_i}</tex>. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N \le N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[[Неравенство Крафта]]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=16426Неравенство Макмиллана2012-01-13T00:28:53Z<p>Krotser: </p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.<br />
<br />
Представим сумму всех слов (кодируемых через <tex>a</tex> и <tex>b</tex>) и возведем эту сумму в степень <tex>N</tex> (любое натуральное число): <tex>(P_1+P_2+...P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.<br />
<br />
Вот пример для однозначного кода со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:<br />
<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые (слова) различны (соответствует определению однозначности).<br />
<br />
Подставим <tex>a=b=\frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{n_i}</tex> получим <tex>2^{-n_i}</tex>. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_k})^N \le N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[[Неравенство Крафта]]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14576Неравенство Макмиллана2011-12-15T04:11:12Z<p>Krotser: /* Ссылки */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[[Неравенство Крафта]]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14569Неравенство Макмиллана2011-12-15T03:35:22Z<p>Krotser: /* Неравенство Макмиллана */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14568Неравенство Макмиллана2011-12-15T03:33:57Z<p>Krotser: /* Неравенство Макмиллана */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня "Программирование: теоремы и задачи".<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Крафта{{---}}Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта{{---}}Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14563Неравенство Макмиллана2011-12-15T03:01:09Z<p>Krotser: /* Неравенство Макмиллана */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным в книге А. Шеня.<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Крафта{{---}}Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex>, то есть <tex>a,ba,bb</tex> и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Крафта{{---}}Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта{{---}}Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14562Неравенство Макмиллана2011-12-15T02:45:31Z<p>Krotser: /* Ссылки */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным А. Шенем.<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Крафта{{---}}Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь (ещё более странное на первый взгляд действие) возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</tex>) и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Крафта{{---}}Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта{{---}}Макмиллана.<br />
}}<br />
<br />
== Ссылки ==<br />
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BA%D0%BC%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D0%B0&diff=14561Неравенство Макмиллана2011-12-15T02:38:30Z<p>Krotser: /* Неравенство Макмиллана */</p>
<hr />
<div>== Необходимые определения ==<br />
{{Определение <br />
|definition=<br />
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.}}<br />
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.<br />
<br />
{{Определение <br />
|definition=<br />
'''Кодом''' для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символ.}}<br />
{{Определение<br />
|definition=Код называется '''однозначным''', если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.<br />
}}<br />
<br />
== Неравенство Макмиллана ==<br />
{{Теорема<br />
|statement=<br />
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \le 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого однозначно декодируемого кода.<br />
|proof=<br />
Докажем теорему способом, приведенным А. Шенем.<br />
<br />
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Крафта{{---}}Макмиллана.<br />
<br />
Так как нет разницы из чего составлять коды, то вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex>. Запишем формально сумму всех кодовых слов как алгебраическое выражение <tex>P_1+P_2+...P_k</tex> (многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь (ещё более странное на первый взгляд действие) возведём это в степень <tex>N</tex> (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах: <tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.<br />
<br />
Например, для кода со словами <tex>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</tex>) и для <tex>N=2</tex> получаем <tex>(a+ba+bb)^2</tex><tex>=</tex><br />
<br />
<tex>=(a+ba+bb)\times{(a+ba+bb)}=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.</tex> Не случайно в этом примере все одночлены в правой части различны (если не переставлять переменные): так будет для любого однозначно декодируемого кода, ведь по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.<br />
<br />
Далее подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex> (выражение из неравенства Крафта{{---}}Макмиллана). Оценим правую часть сверху, сгруппировав слова по длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<N\times{\max(n_i)}</tex> и это верно при любом <tex>N</tex>. Если основание степени в левой части больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта{{---}}Макмиллана.<br />
}}<br />
<br />
== Ссылки == <br />
[[Неравенство Крафта]]<br />
<br />
== Литература ==<br />
''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0,_%D0%94%D0%9F_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0%D0%BC&diff=13770Задача коммивояжера, ДП по подмножествам2011-12-01T15:27:10Z<p>Krotser: </p>
<hr />
<div>'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости. Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?<br />
<br />
== Варианты решения ==<br />
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.<br />
<br />
Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.<br />
<br />
==== Перебор перестановок ====<br />
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.<br />
<br />
==== Динамическое программирование по подмножествам (по маскам) ====<br />
<br />
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.<br />
<br />
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G=(V,E)</tex> <tex> N </tex><br />
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.<br />
<br />
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.<br />
<br />
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.<br />
<br />
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).<br />
<br />
Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex>, <tex>mask = 0</tex>). Для остальных состояний перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).<br />
<br />
То есть, <tex>d[i][mask]</tex> считается по следующему правилу:<br />
<br />
<tex> d[i][mask] =<br />
\begin{cases}<br />
0, &\text{if }i = 0\text{ and }mask = 0 \\<br />
min_{j: mask_j=1, (i, j) \in E} \begin{Bmatrix} w(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\<br />
\infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and set of possible transitions is empty}<br />
\end{cases}<br />
</tex><br />
<br />
где, <tex> \text {and ---}</tex> и, <tex>\text {or ---} </tex> или, <tex>\text {set of possible transitions is empty ---}</tex> множество возможных переходов пусто.<br />
<br />
<br />
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.<br />
<br />
Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.<br />
<br />
== Реализация ==<br />
//Все переменные используются из описания алгоритма, inf = бесконечность<br />
d[0][0] = 0;<br />
for i = 0 to n - 1<br />
for mask = 0 to mask = 2 ** n - 1<br />
for j = 0 to n - 1<br />
if j-ий бит mask == 1<br />
if w(i, j) существует<br />
d[i][mask] = min(d[i][mask], d[j][mask - 2 ** n] + w(i, j);<br />
else<br />
d[i][mask] = inf;<br />
print d[0][2 ** n - 1];<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]<br />
<br />
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]<br />
<br />
== Литература ==<br />
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3<br />
<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0,_%D0%94%D0%9F_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0%D0%BC&diff=13769Задача коммивояжера, ДП по подмножествам2011-12-01T14:41:59Z<p>Krotser: </p>
<hr />
<div>'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости. Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?<br />
<br />
== Варианты решения ==<br />
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.<br />
<br />
Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.<br />
<br />
==== Перебор перестановок ====<br />
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.<br />
<br />
==== Динамическое программирование по подмножествам (по маскам) ====<br />
<br />
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.<br />
<br />
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G?=?(V,?E)</tex> <tex> N </tex><br />
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.<br />
<br />
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.<br />
<br />
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.<br />
<br />
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>mask</tex> - подмножество вершин исходного графа, которые осталось посетить).<br />
<br />
Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>mask = 0</tex>). Для остальных состояний перебираем все возможные переходы из <tex>i</tex>-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).<br />
<br />
То есть, <tex>d[i][mask]</tex> считается по следующему правилу:<br />
<br />
<tex> d[i][mask] =<br />
\begin{cases}<br />
0, &\text{if }i = 0\text{ and }mask = 0 \\<br />
min_{j: mask_j=1, (i, j) \in E} \begin{Bmatrix} w(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\<br />
\infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and set of possible transitions is empty}<br />
\end{cases}<br />
</tex><br />
<br />
где, <tex> \text {and ---}</tex> и, <tex>\text {or ---} </tex> или, <tex>\text {set of possible transitions is empty ---}</tex> множество возможных переходов пусто.<br />
<br />
<br />
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.<br />
<br />
Для того, чтобы восстановить сам пут, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.<br />
<br />
== Реализация ==<br />
//Все переменные используются из описания алгоритма, inf = бесконечность<br />
d[0][0] = 0;<br />
for i = 0 to n - 1<br />
for mask = 0 to mask = 2 ** n - 1<br />
for j = 0 to n - 1<br />
if j-ий бит mask == 1<br />
if w(i, j) существует<br />
d[i][mask] = min(d[i][mask], d[j][mask - 2 ** n] + w(i, j);<br />
else<br />
d[i][mask] = inf;<br />
print d[0][2 ** n - 1];<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]<br />
<br />
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]<br />
<br />
== Литература ==<br />
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3<br />
<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>Krotserhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0,_%D0%94%D0%9F_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0%D0%BC&diff=13753Задача коммивояжера, ДП по подмножествам2011-12-01T04:51:51Z<p>Krotser: /* Реализация */</p>
<hr />
<div>'''Задача о коммивояжере''' (англ. '''Travelling - salesman problem, TSP''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.<br />
<br />
== Формулировка задачи ==<br />
Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?<br />
<br />
== Варианты решения ==<br />
В теории алгоритмов NP-полная (NPC, NP-complete) задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Cтатус NP-полных задач пока что неизвестен. Для их решения до настоящего времени не разработано алгоритмов с полиномиальным временем работы, но и не доказано, что для какой-то из них алгоритмов не существует. Этот так называемый вопрос P<tex>\neq</tex>NP с момента своей постановки в 1971 году стал одним из самых трудных в теории вычислительных систем.<br />
<br />
Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.<br />
==== Перебор перестановок ====<br />
<br />
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O(N!)</tex>.<br />
<br />
==== Динамическое программирование по подмножествам (по маскам) ====<br />
<br />
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.<br />
<br />
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе <tex> G = (V, E)</tex> <tex> N </tex><br />
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> p(i, j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.<br />
<br />
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости - путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>S = 0 </tex>.<br />
<br />
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.<br />
<br />
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>mask</tex> - подмножество вершин исходного графа, которые осталось посетить).<br />
<br />
Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>mask = 0</tex>). Для остальных состояний перебираем все возможные переходы из <tex>i</tex>-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).<br />
<br />
То есть, <tex>d[i][mask]</tex> считается по следующему правилу:<br />
<br />
<tex> d[i][mask] =<br />
\begin{cases}<br />
0, &\text{if }i = 0\text{ and }mask = 0 \\<br />
min_{j: mask_j=1, (i, j) \in E} \begin{Bmatrix} p(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\<br />
\infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and set of possible transitions is empty}<br />
\end{cases}<br />
</tex><br />
<br />
где, <tex> \text {and ---}</tex> и, <tex>\text {or ---} </tex> или, <tex>\text {set of possible transitions is empty ---}</tex> множество возможных переходов пусто.<br />
<br />
<br />
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> - стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины.<br />
<br />
Восстановить сам цикл несложно. Для этого воспользуемся соотношением <tex> d[i][mask] = p(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.<br />
<br />
Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.<br />
<br />
== Реализация ==<br />
//Все переменные используются из описания алгоритма, inf = бесконечность<br />
inputData(); //считывание данных<br />
d[0][0] = 0;<br />
for i = 0 to n - 1<br />
for mask = 0 to mask = 2 ^ n - 1<br />
for j = 0 to n - 1<br />
if j-ий бит mask == 1<br />
if p(i, j) существует<br />
d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);<br />
else<br />
d[i][mask] = inf;<br />
writeData(); // запись данных, ответ хранится в d[0][2 ^ n - 1]<br />
<br />
== Ссылки == <br />
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]<br />
<br />
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]<br />
<br />
== Литература ==<br />
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3<br />
<br />
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]</div>Krotser