[Udemy] Алгоритм X Dancing Links сборки пентамимо на C# (Евгений Волосатов)
Цена:
312.4
![[?IMG]](proxy14p.php?image=https%3A%2F%2Fi106.fastpic.ru%2Fbig%2F2018%2F1209%2F86%2F53e33f6f52ab8d009262891d6b1cf586.png&hash=4a24de94c62fe1ab75f72997adf9d295&v=4)
? Теоретическое и практическое знакомство с гениальным 'Алгоритмом икс' Дональда Кнута с примерами
?
Чему вы научитесь?
Поймут суть алгоритма X для быстрого поиска решений
Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links
Требования
Логическое мышление
Основы языка программирования C#
Описание
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее.
В первой части курса 'Теория' мы разберём принцип работы алгоритма, выполним его построчно 'ручками' на конкретном примере, чтобы лучше понять, как он устроен и как работает.
Во второй части курса 'Практика' мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации 'Алгоритма Икс' Дональда Кнута. и напишем весь алгоритм.
Во третьей части курса 'Пентамимо' мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво.
Если вам нравятся алгоритмы - обязательно пройдите этот курс, не пожалеете.
Какова целевая аудитория?
Для любителей алгоритмов
Для инженеров и программистов
Для студентов с лабораторкой по Dancing Links
Что входит в курс?
4 часа видео
Материалы курса
14 лекций - 04:07:25
Теория - 32:04
Что такое Dancing Links - 08:35
В этой серии уроков мы познакомимся с гениальным 'алгоритмом X' Дональда Кнута — Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей.
3. Приложить интересную картинку на тему урока.
Работа алгоритма - 12:43
На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже).
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Напишите своё мнение по поводу данного урока.
3. Самостоятельно рассмотреть варианты поиска решения.
4. Приложить скриншот проработанного алгоритма.
Двусвязный список с удалением - 10:46
На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Нарисовать циклический список из 4 элементов ABCD.
3. Проработать весь алгоритм самостоятельно.
4. Приложить скриншот проработанного алгоритма.
5. * Продемонстрировать удаление/восстановление всех элементов.
Практика - 01:54:55
Расширение хоровода - 24:08
На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать новый проект AlgorithmX.
3. Создать новый класс Cell().
4. Добавить необходимые переменные и конструктор в классе Cell().
5. Избавиться от статика в классе Program().
6. Реализовать функцию test() в классе Program().
7. Реализовать функцию InsertLeft() в классе Cell().
8. Доработать конструктор в классе Cell().
9. Доработать функцию test() в классе Program(), использовав InsertLeft().
10. Приложить скриншот результата.
Заголовки столбцов - 12:17
На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить новые переменные в классе Cell().
3. Доработать в конструктор класса Cell() начальные значение новых переменных.
4. Реализовать функцию InsertUp() в классе Cell().
5. Создать класс Header() с необходимыми переменными.
6. Заменить переменную name на header в классе Cell().
7. Добавить конструктор в классе Header().
8. Доработать функцию test() в классе Program(), использовав InsertUp() и Header().
9. Приложить скриншот результата.
Единичная матрица - 25:01
На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать класс Dance() с необходимыми переменными.
3. Добавить конструктор в классе Dance().
4. Модифицировать тип переменной name в классе Header().
5. Реализовать функцию AddRow() в классе Dance().
6. Реализовать функцию start() в классе Program(), использовав класс Dance().
7. Приложить скриншот результата.
8. * Добавить все 12 строчек по образцу.
Как ссылки пошли впляс - 21:15
На этом уроке мы реализуем заготовку функции Dance() в классе Dance().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить все 12 строчек в матрицу.
3. Реализовать функцию Dance() в классе Dance().
4. Создать заглушки для функций Cover/Uncover().
5. Добавить вывод текущего шага в функции Dance().
6. Приложить скриншот результата.
Открытие/закрытие столбцов - 32:14
На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить номер строки в классе Cell().
3. Доработать функцию AddRow() в классе Dance().
4. Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел.
5. Реализовать функции Cover/Uncover() в классе Dance().
6. Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов.
7. Приложить скриншот результата.
Пентамимо - 01:40:26
Фигуры из пентамимо - 18:16
На этом уроке мы приступаем к решению олимпиадной задачи 'Пентамино', заполнив массив всеми вариантами расположения фигур.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать структуру Figure() и Variant().
3. Создать класс Pentaminos().
4. Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos().
5. Создать функцию startPent() в классе Program().
6. Проверить заполнение массива всеми вариантами фигур.
7. Приложить скриншот результата.
8. ** Доработать функцию startPent() для решения поставленной задачи.
9. *** Реализовать генератор всевозможных расположений фигур.
Фигуры в консоли - 14:59
На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть, что происходит в процессе работы алгоритма.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать функцию Show() в классе Figure().
3. Добавить в классе Figure() строку символов фигур.
4. Доработать функцию startPentamino() в классе Program() для отображения фигур.
5. Реализовать перегрузку функции Show() в классе Figure() для более короткой записи.
6. Использовать короткую запись в функции startPentamino() класса Program().
7. Приложить скриншот результата.
8. * Вывести все 12 фигур в консоли.
Матрица Пентагона - 15:55
На этом уроке мы завершим реализацию функции поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино.
3. Дождаться завершения работы алгоритма и написать время ожидания.
4. Приложить скриншот результата.
Пентагон в деталях - 09:40
На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Исправить ошибку прошлого урока связанную с nr++.
3. Использовать отображение генерации расположения вариантов фигур через функцию Show().
4. Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш.
5. Реализовать функцию Hide() в классе Figure().
6. Использовать функцию Hide() вместо Console.Clear().
7. Приложить скриншот результата.
Пентагон ищет решение - 22:01
На этом уроке мы визуализируем поиск решения Пентамино с использованием yield.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Модифицировать функцию Dance() в классе Dance(), чтобы она возвращала IEnumerable.
3. Воспользоваться возвращаемым IEnumerable для визуализации текущего состояния поиска решений.
4. Модифицировать работу рекурсии с использованием yield return.
5. Создать структуру FigureRow для хранения расположения фигуры на поле.
6. Использовать динамический список для хранения объектов FigureRow.
7. Добавить конструктор для удобства добавления информации в список.
8. Сделать структуру FigureRow глобальной.
9. Реализовать функции Show/Hide() с параметром FigureRow.
10. Добавить задержку между отображением/стиранием текущего состояния поиска решения.
11. Приложить скриншот результата.
12. * Дождаться окончания поиска решений.
Десятикратная оптимизация - 19:35
В завершение знакомства с гениальным 'алгоритмом X' Дональда Кнута — Dancing Links,
мы оптимизируем наш алгоритм поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Оптимизировать функцию Dance() в классе Dance().
3. Реализовать счётчик количество найденных вариантов.
4. Реализовать счётчик времени потраченного на поиск решений.
5. Поэкспериментировать с разными размерами поля.
6. Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма.
7. Приложить скриншот результата.
8. *** Реализовать решение Судоку, используя данный алгоритм.
9. *** Реализовать решение Парад Ферзей, используя данный алгоритм.
О преподавателе
Евгений Волосатов
Магистр математики и информатики, C#, Java, PHP программист
Я — Игромистр.
Моё призвание — показать пошаговый процесс создания игровых и прикладных программ, с нуля до результата.
Меня зовут Волосатов Евгений Витольдович, мне 40 лет, живу в Литве,
закончил Вильнюсский государственный университет магистром математики и информатики, также имею педагогическое образование.
За плечами сотни различных проектов на C#, Java, PHP, ASP.NET, SQL и т.д.
Всю свою сознательную жизнь я пишу программы и обучаю этому других.
14 лекций - 04:07:25
Теория - 32:04
Что такое Dancing Links - 08:35
В этой серии уроков мы познакомимся с гениальным 'алгоритмом X' Дональда Кнута — Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей.
3. Приложить интересную картинку на тему урока.
Работа алгоритма - 12:43
На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже).
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Напишите своё мнение по поводу данного урока.
3. Самостоятельно рассмотреть варианты поиска решения.
4. Приложить скриншот проработанного алгоритма.
Двусвязный список с удалением - 10:46
На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Нарисовать циклический список из 4 элементов ABCD.
3. Проработать весь алгоритм самостоятельно.
4. Приложить скриншот проработанного алгоритма.
5. * Продемонстрировать удаление/восстановление всех элементов.
Практика - 01:54:55
Расширение хоровода - 24:08
На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать новый проект AlgorithmX.
3. Создать новый класс Cell().
4. Добавить необходимые переменные и конструктор в классе Cell().
5. Избавиться от статика в классе Program().
6. Реализовать функцию test() в классе Program().
7. Реализовать функцию InsertLeft() в классе Cell().
8. Доработать конструктор в классе Cell().
9. Доработать функцию test() в классе Program(), использовав InsertLeft().
10. Приложить скриншот результата.
Заголовки столбцов - 12:17
На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить новые переменные в классе Cell().
3. Доработать в конструктор класса Cell() начальные значение новых переменных.
4. Реализовать функцию InsertUp() в классе Cell().
5. Создать класс Header() с необходимыми переменными.
6. Заменить переменную name на header в классе Cell().
7. Добавить конструктор в классе Header().
8. Доработать функцию test() в классе Program(), использовав InsertUp() и Header().
9. Приложить скриншот результата.
Единичная матрица - 25:01
На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать класс Dance() с необходимыми переменными.
3. Добавить конструктор в классе Dance().
4. Модифицировать тип переменной name в классе Header().
5. Реализовать функцию AddRow() в классе Dance().
6. Реализовать функцию start() в классе Program(), использовав класс Dance().
7. Приложить скриншот результата.
8. * Добавить все 12 строчек по образцу.
Как ссылки пошли впляс - 21:15
На этом уроке мы реализуем заготовку функции Dance() в классе Dance().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить все 12 строчек в матрицу.
3. Реализовать функцию Dance() в классе Dance().
4. Создать заглушки для функций Cover/Uncover().
5. Добавить вывод текущего шага в функции Dance().
6. Приложить скриншот результата.
Открытие/закрытие столбцов - 32:14
На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover().
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Добавить номер строки в классе Cell().
3. Доработать функцию AddRow() в классе Dance().
4. Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел.
5. Реализовать функции Cover/Uncover() в классе Dance().
6. Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов.
7. Приложить скриншот результата.
Пентамимо - 01:40:26
Фигуры из пентамимо - 18:16
На этом уроке мы приступаем к решению олимпиадной задачи 'Пентамино', заполнив массив всеми вариантами расположения фигур.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Создать структуру Figure() и Variant().
3. Создать класс Pentaminos().
4. Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos().
5. Создать функцию startPent() в классе Program().
6. Проверить заполнение массива всеми вариантами фигур.
7. Приложить скриншот результата.
8. ** Доработать функцию startPent() для решения поставленной задачи.
9. *** Реализовать генератор всевозможных расположений фигур.
Фигуры в консоли - 14:59
На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть, что происходит в процессе работы алгоритма.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать функцию Show() в классе Figure().
3. Добавить в классе Figure() строку символов фигур.
4. Доработать функцию startPentamino() в классе Program() для отображения фигур.
5. Реализовать перегрузку функции Show() в классе Figure() для более короткой записи.
6. Использовать короткую запись в функции startPentamino() класса Program().
7. Приложить скриншот результата.
8. * Вывести все 12 фигур в консоли.
Матрица Пентагона - 15:55
На этом уроке мы завершим реализацию функции поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино.
3. Дождаться завершения работы алгоритма и написать время ожидания.
4. Приложить скриншот результата.
Пентагон в деталях - 09:40
На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Исправить ошибку прошлого урока связанную с nr++.
3. Использовать отображение генерации расположения вариантов фигур через функцию Show().
4. Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш.
5. Реализовать функцию Hide() в классе Figure().
6. Использовать функцию Hide() вместо Console.Clear().
7. Приложить скриншот результата.
Пентагон ищет решение - 22:01
На этом уроке мы визуализируем поиск решения Пентамино с использованием yield.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Модифицировать функцию Dance() в классе Dance(), чтобы она возвращала IEnumerable.
3. Воспользоваться возвращаемым IEnumerable для визуализации текущего состояния поиска решений.
4. Модифицировать работу рекурсии с использованием yield return.
5. Создать структуру FigureRow для хранения расположения фигуры на поле.
6. Использовать динамический список для хранения объектов FigureRow.
7. Добавить конструктор для удобства добавления информации в список.
8. Сделать структуру FigureRow глобальной.
9. Реализовать функции Show/Hide() с параметром FigureRow.
10. Добавить задержку между отображением/стиранием текущего состояния поиска решения.
11. Приложить скриншот результата.
12. * Дождаться окончания поиска решений.
Десятикратная оптимизация - 19:35
В завершение знакомства с гениальным 'алгоритмом X' Дональда Кнута — Dancing Links,
мы оптимизируем наш алгоритм поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
1. Внимательно прослушать и просмотреть видео.
2. Оптимизировать функцию Dance() в классе Dance().
3. Реализовать счётчик количество найденных вариантов.
4. Реализовать счётчик времени потраченного на поиск решений.
5. Поэкспериментировать с разными размерами поля.
6. Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма.
7. Приложить скриншот результата.
8. *** Реализовать решение Судоку, используя данный алгоритм.
9. *** Реализовать решение Парад Ферзей, используя данный алгоритм.
О преподавателе
Евгений Волосатов
Магистр математики и информатики, C#, Java, PHP программист
Я — Игромистр.
Моё призвание — показать пошаговый процесс создания игровых и прикладных программ, с нуля до результата.
Меня зовут Волосатов Евгений Витольдович, мне 40 лет, живу в Литве,
закончил Вильнюсский государственный университет магистром математики и информатики, также имею педагогическое образование.
За плечами сотни различных проектов на C#, Java, PHP, ASP.NET, SQL и т.д.
Всю свою сознательную жизнь я пишу программы и обучаю этому других.