Итак, продолжаем читать книгу
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с такими структурами данных, как массив и связный список. Массив может быть охарактеризован, как непрерывная последовательность элементов одного типа в памяти. Он поддерживает быстрый доступ O(1) к элементам по индексу, но удаление и вставка занимают больше времени - O(n). Список же состоит из узлов, где каждый узел связан с последующим или предыдущим (в случае односвязного списка) или с последующим и предыдущим (в случае двусвязного списка). Операция вставки и удаления в связном списке довольно просты, если у нас есть ссылка на удаляемый элемент O(1), но чтения элемента по индекс занимает больше времени - O(n). Кроме того, в этой главе мы познакомились с сортировкой вставками, которая выполняется за квадратичное время.
В следующей главе "3. Рекурсия" мы познакомимся поближе с понятиями рекурсии и стека. Концепция рекурсивного вызова является одним из подходов к построению итеративных алгоритмов. Стек же является базовой концепцией выполнения программ в современных вычислительных системах. Оба понятия важны для понимания программистом.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с такими структурами данных, как массив и связный список. Массив может быть охарактеризован, как непрерывная последовательность элементов одного типа в памяти. Он поддерживает быстрый доступ O(1) к элементам по индексу, но удаление и вставка занимают больше времени - O(n). Список же состоит из узлов, где каждый узел связан с последующим или предыдущим (в случае односвязного списка) или с последующим и предыдущим (в случае двусвязного списка). Операция вставки и удаления в связном списке довольно просты, если у нас есть ссылка на удаляемый элемент O(1), но чтения элемента по индекс занимает больше времени - O(n). Кроме того, в этой главе мы познакомились с сортировкой вставками, которая выполняется за квадратичное время.
В следующей главе "3. Рекурсия" мы познакомимся поближе с понятиями рекурсии и стека. Концепция рекурсивного вызова является одним из подходов к построению итеративных алгоритмов. Стек же является базовой концепцией выполнения программ в современных вычислительных системах. Оба понятия важны для понимания программистом.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
❤2
Для тех, кто хочет глубже понять рекурсию, немного задач на подумать:
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
ru.wikibooks.org
Рекурсия
Исходный вариант статьи (В. В. Пупышев, «Рекурсия: плохо или хорошо?») опубликован в журнале «Потенциал».
Опрос по рекурсии придумать не получилось, поэтому вот вам несколько шуток про рекурсию, убедитесь, что вы их понимаете:
"Чтобы понять рекурсию, надо понять рекурсию."
"Определение рекурсии в энциклопедии: Рекурсия: см. рекурсия."
Коктейль «рекурсивный»: 30% водки, 60% коктейля «рекурсивный».
Завтра начнем следующую главу :)
#книжный_клуб #алгоритмы
"Чтобы понять рекурсию, надо понять рекурсию."
"Определение рекурсии в энциклопедии: Рекурсия: см. рекурсия."
Коктейль «рекурсивный»: 30% водки, 60% коктейля «рекурсивный».
Завтра начнем следующую главу :)
#книжный_клуб #алгоритмы
😁3👍2
Итак, продолжаем читать книгу
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с понятиями стека и рекурсии. Стек можно представить в виде стопки тарелок, которые вы кладете одна на другую одной рукой. Извлечь можно только верхний элемент, положить новый элемент можно тоже только на верх стека. Интерпретатор использует стек для хранения последовательности вызова вложенных функций. Вызываем первую функцию - кладем указатель на неё и её параметры на верх стека. Внутри этой функции вызываем функцию - кладем её указатель и параметры поверх предыдщуих. Выходим из функции - убираем из стека верхние параметры, соответствующие функции.
Кроме этого, мы рассмотрели определение рекурсии. Рекурсия характеризуется тем, что мы вызываем некую функцию, а затем во время её исполнения снова вызываем её же. Часто это необходимо, когда решение исходной задачи требует решения сходной подзадачи. К примеру, задача: разобрать матрешку. Нам необходимо выполнить следующую "функцию":
Надеюсь, это хоть как-то проясняет рекурсию.
В следующей главе "4. Быстрая сортировка" мы познакомимся с алгоритмом быстрой сортировки и с понятиями оценки в лучшем, среднем и худшем случаях. Быстрая сортировка является одним из часто используемых на практике алгоритмов.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
#книжный_клуб #алгоритмы
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с понятиями стека и рекурсии. Стек можно представить в виде стопки тарелок, которые вы кладете одна на другую одной рукой. Извлечь можно только верхний элемент, положить новый элемент можно тоже только на верх стека. Интерпретатор использует стек для хранения последовательности вызова вложенных функций. Вызываем первую функцию - кладем указатель на неё и её параметры на верх стека. Внутри этой функции вызываем функцию - кладем её указатель и параметры поверх предыдщуих. Выходим из функции - убираем из стека верхние параметры, соответствующие функции.
Кроме этого, мы рассмотрели определение рекурсии. Рекурсия характеризуется тем, что мы вызываем некую функцию, а затем во время её исполнения снова вызываем её же. Часто это необходимо, когда решение исходной задачи требует решения сходной подзадачи. К примеру, задача: разобрать матрешку. Нам необходимо выполнить следующую "функцию":
разобрать_матрешку (матрешка):
если разбирается
внешняя_матрешка = открыть_внешнюю_матрешку()
внутренняя_матрешка = извлечь_внутреннюю_матрешку()
вернуть внешняя_матрешка +
разобрать_матрешку (внутренняя_матрешка)
иначе
вернуть матрешка
Надеюсь, это хоть как-то проясняет рекурсию.
В следующей главе "4. Быстрая сортировка" мы познакомимся с алгоритмом быстрой сортировки и с понятиями оценки в лучшем, среднем и худшем случаях. Быстрая сортировка является одним из часто используемых на практике алгоритмов.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Какова временная сложность быстрой сортировки в худшем случае?
Anonymous Quiz
20%
O(n)
29%
O(n log n)
28%
O(n^2)
8%
O(n!)
15%
Посмотреть ответы
Итак, продолжаем читать книгу
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с парадигмой "разделяй и властвуй", с алгоритмом быстрой сортировки и оценками для среднего и худшего случая. Парадигма разделяй и властвуй предлагает подход к решению задач, когда задача разбивается на более мелкие задачи, которые решают схожим подходом. Пример этого подхода - быстрая сортировка: данные делятся барьерным элементом, остальные элементы размещаются слева от барьерного, если они меньше его, справа - если больше. Затем, к элементам слева и справа применяется тот же алгоритм: выбирается барьерный элемент и т.д. Интересно заметить, что количество действий будет разным в разных случаях. В худшем случае будет O(n^2), но в среднем - O(n log n).
В следующей главе "4. Хеш-таблицы" мы познакомимся поближе с понятиям...кхм...хеш-таблиц. Оно является значимым для понимания работы со словарями и их ограничений. Ну а словари в программировании используются повсеместно.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с парадигмой "разделяй и властвуй", с алгоритмом быстрой сортировки и оценками для среднего и худшего случая. Парадигма разделяй и властвуй предлагает подход к решению задач, когда задача разбивается на более мелкие задачи, которые решают схожим подходом. Пример этого подхода - быстрая сортировка: данные делятся барьерным элементом, остальные элементы размещаются слева от барьерного, если они меньше его, справа - если больше. Затем, к элементам слева и справа применяется тот же алгоритм: выбирается барьерный элемент и т.д. Интересно заметить, что количество действий будет разным в разных случаях. В худшем случае будет O(n^2), но в среднем - O(n log n).
В следующей главе "4. Хеш-таблицы" мы познакомимся поближе с понятиям...кхм...хеш-таблиц. Оно является значимым для понимания работы со словарями и их ограничений. Ну а словари в программировании используются повсеместно.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
❤2
Немного продвинутого материала для тех, кто хочет понять, как работает хэш-таблица в python (в интерпретаторе cpython). Собственно, ссылка на комментарий в коде:
https://github.com/python/cpython/blob/main/Objects/dictobject.c#L261
#hash
https://github.com/python/cpython/blob/main/Objects/dictobject.c#L261
#hash
GitHub
cpython/Objects/dictobject.c at main · python/cpython
The Python programming language. Contribute to python/cpython development by creating an account on GitHub.
Немного про книжный клуб. Мы почти дошли до середины книги. Следующая неделя - для догоняющих. Через неделю начнем новую главу про графы.
#книжный_клуб #алгоритмы
#книжный_клуб #алгоритмы
Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с хэш-функциями. Они позволяют за константное время находить адрес ячейки, соответствующей определенному значение. Иными словами, любое значение трансформируется хэш-функцией в почти уникальный ключ.
Пусть есть хэш-фунция h(x), тогда могут иметь место следующие равенства:
h("cat") = 2
h("dog") = 4
h("mouse") = 1
И каждый раз, когда мы будем вызывать h к данным словам, мы будем получать те же значения. Хорошие хэш-функции должны генерировать уникальные значения. Если же хэш-функция выдает значение, которое уже встречалось, к примеру, h("bird") = 4, то такая ситуация называется коллизией. Хэш-функции широко применяются в программировании, в python на них построены словари.
В следующей главе "6. Поиск в ширину" мы познакомимся с графами. Графы это мегаполезная структура, которая вам точно рано или поздно пригодится. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Кроме этого, мы узнаем про алгоритм поиска в ширину - один из базовых алгоритмов на графах.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
В предыдущей главе мы познакомились с хэш-функциями. Они позволяют за константное время находить адрес ячейки, соответствующей определенному значение. Иными словами, любое значение трансформируется хэш-функцией в почти уникальный ключ.
Пусть есть хэш-фунция h(x), тогда могут иметь место следующие равенства:
h("cat") = 2
h("dog") = 4
h("mouse") = 1
И каждый раз, когда мы будем вызывать h к данным словам, мы будем получать те же значения. Хорошие хэш-функции должны генерировать уникальные значения. Если же хэш-функция выдает значение, которое уже встречалось, к примеру, h("bird") = 4, то такая ситуация называется коллизией. Хэш-функции широко применяются в программировании, в python на них построены словари.
В следующей главе "6. Поиск в ширину" мы познакомимся с графами. Графы это мегаполезная структура, которая вам точно рано или поздно пригодится. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Кроме этого, мы узнаем про алгоритм поиска в ширину - один из базовых алгоритмов на графах.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Какова временная сложность поиска в ширину на графе с V вершин и E ребер?
Anonymous Quiz
44%
O(V*E)
2%
O(V-E)
19%
O(V+E)
10%
O(V)
24%
Посмотреть ответы
Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с графами и поиском в ширину. Граф является довольно простой, но мощной абстракцией. Граф представляет собой набор вершин и ребер, соединяющих эти вершины. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Алгоритм поиска в ширину позволяет совершить обход графа из некой заданной начальной вершины. Обход графа происходит поуровнево: сначала просматриваются все вершины, достижимые из текущей (1ый уровень), затем просматриваются все вершины, достижимые из вершин первого уровня, и т.д.
В следующей главе "7. Алгоритм Дейкстры" мы познакомимся с алгоритмом нахождения кратчайшего пути во взвешенном графе (в графе, у которого ребра имеют веса). Подобные алгоритмы очень часто применяются на практике. К примеру, если вам необходимо добраться из города А в город Д, а проехать к последнему вы можете через один из городов Б, В, Г, то алгоритм нахождения кратчайшего пути поможет вам найти....кратчайший путь.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
В предыдущей главе мы познакомились с графами и поиском в ширину. Граф является довольно простой, но мощной абстракцией. Граф представляет собой набор вершин и ребер, соединяющих эти вершины. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Алгоритм поиска в ширину позволяет совершить обход графа из некой заданной начальной вершины. Обход графа происходит поуровнево: сначала просматриваются все вершины, достижимые из текущей (1ый уровень), затем просматриваются все вершины, достижимые из вершин первого уровня, и т.д.
В следующей главе "7. Алгоритм Дейкстры" мы познакомимся с алгоритмом нахождения кратчайшего пути во взвешенном графе (в графе, у которого ребра имеют веса). Подобные алгоритмы очень часто применяются на практике. К примеру, если вам необходимо добраться из города А в город Д, а проехать к последнему вы можете через один из городов Б, В, Г, то алгоритм нахождения кратчайшего пути поможет вам найти....кратчайший путь.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
👍2
Какой алгоритм лучше подходит для поиска кратчайшего пути во взвешенном графе?
Anonymous Quiz
60%
Алгоритм Дейкстры
28%
Алгоритм поиска в ширину
12%
Посмотреть ответы
Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с алгоритмом Дейкстры. Этот алгоритм позволяет найти кратчайший путь во взвешенном графе. На каждом шаге алгоритм выбирает новую вершину, переходит по кратчайшему пути, а затем пересчитывает стоимости маршрутов к соседним вершинам - если более кратчайший существует, то обновляем стоимости маршрутов для соседних вершин. И так, пока не будет найдет итоговый маршрут. Описание - так себе, поэтому если у вас получится сделать получше, пишите в комментариях.
В следующей главе "8. Жадные алгоритмы" мы познакомимся с понятием жадности. Мы узнаем, как можно решать задачи, для которых оптимальные алгоритмы работают слишком долго. Примеры такой задачи - построение оптимального маршрута через несколько точек. Жадные алгоритмы построены на удивительно простой концепции, которая, однако, позволяет достигать достаточно хороших результатов.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
В предыдущей главе мы познакомились с алгоритмом Дейкстры. Этот алгоритм позволяет найти кратчайший путь во взвешенном графе. На каждом шаге алгоритм выбирает новую вершину, переходит по кратчайшему пути, а затем пересчитывает стоимости маршрутов к соседним вершинам - если более кратчайший существует, то обновляем стоимости маршрутов для соседних вершин. И так, пока не будет найдет итоговый маршрут. Описание - так себе, поэтому если у вас получится сделать получше, пишите в комментариях.
В следующей главе "8. Жадные алгоритмы" мы познакомимся с понятием жадности. Мы узнаем, как можно решать задачи, для которых оптимальные алгоритмы работают слишком долго. Примеры такой задачи - построение оптимального маршрута через несколько точек. Жадные алгоритмы построены на удивительно простой концепции, которая, однако, позволяет достигать достаточно хороших результатов.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
В чем заключается жадность жадных алгоритмов?
Anonymous Quiz
21%
Пытаются решить задачу, используя больше вычислительной мощности
51%
Вместо глобально оптимального решения ищут оптимальные решения на каждом шаге
16%
Преобразуют исходную задачу в задачу меньшей размерности, которую они могут решить за один присест
12%
Посмотреть ответы
Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с понятием жадности в алгоритмах. Что такое жадность? Жадность - это свойство механизма принятия решений на каждом шаге алгоритма. На каждом шаге алгоритма решение принимается так, чтобы как можно больше приблизиться к цели на этом шаге. К примеру, пусть вам надо доехать из Великого Новгорода во Владивосток. Вы можете либо продумать свой маршрут полностью и получить что-то типа Новгород - Москва - Владивосток, либо применить жадную стратегию и из Новгорода поехать в город, который ближе всего к Владивостоку. Из второго города снова поехать в город, который ближе всего к Владивостоку. В конечном счета у вас может получиться такой маршрут: Новгород - Сыктывкар - Красноярск - Владивосток. Этот маршрут займет больше времени, но он все равно будет достаточно хорош. Иными словами, жадные алгоритмы пытаются оптимально выбирать на каждом шаге, надеясь, что общее решение тоже будет достаточно хорошим (но это не гарантировано).
В следующей главе "9. Динамическое программирование" мы познакомимся с новым подходом к решению задач. И да, с программированием в общепринятом смысле динамическое не связано. Как я уже написал, динамическое программирование представляет ещё один подход к задачами. В этом подходе задача разбивается на подзадачи сходной структуры, которые затем и решаются. Задачи на динамическое программирование довольно часто можно встретить на собеседованиях.
Эту главу я предлагаю читать пару недель. Тема довольно большая, я крайне рекомендую ознакомиться с дополнительными материалами для более глубокого понимания. Если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). Через пару недель я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
В предыдущей главе мы познакомились с понятием жадности в алгоритмах. Что такое жадность? Жадность - это свойство механизма принятия решений на каждом шаге алгоритма. На каждом шаге алгоритма решение принимается так, чтобы как можно больше приблизиться к цели на этом шаге. К примеру, пусть вам надо доехать из Великого Новгорода во Владивосток. Вы можете либо продумать свой маршрут полностью и получить что-то типа Новгород - Москва - Владивосток, либо применить жадную стратегию и из Новгорода поехать в город, который ближе всего к Владивостоку. Из второго города снова поехать в город, который ближе всего к Владивостоку. В конечном счета у вас может получиться такой маршрут: Новгород - Сыктывкар - Красноярск - Владивосток. Этот маршрут займет больше времени, но он все равно будет достаточно хорош. Иными словами, жадные алгоритмы пытаются оптимально выбирать на каждом шаге, надеясь, что общее решение тоже будет достаточно хорошим (но это не гарантировано).
В следующей главе "9. Динамическое программирование" мы познакомимся с новым подходом к решению задач. И да, с программированием в общепринятом смысле динамическое не связано. Как я уже написал, динамическое программирование представляет ещё один подход к задачами. В этом подходе задача разбивается на подзадачи сходной структуры, которые затем и решаются. Задачи на динамическое программирование довольно часто можно встретить на собеседованиях.
Эту главу я предлагаю читать пару недель. Тема довольно большая, я крайне рекомендую ознакомиться с дополнительными материалами для более глубокого понимания. Если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). Через пару недель я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная, успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Небольшой апдейт: опрос по динамическому программированию будет в следующие выходные. Тема довольно сложная, постраюсь позже расписать её, как сам понял.
Для тех, кто хочет глубже углубиться, есть неплохая книга:
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание
Рекомендую именно третье издание, оно может быть найдено в файлах вк (https://vk.com/docs) в формате djvu.
Для тех, кто хочет глубже углубиться, есть неплохая книга:
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание
Рекомендую именно третье издание, оно может быть найдено в файлах вк (https://vk.com/docs) в формате djvu.
Что представляет собой метод динамического программирования?
Anonymous Quiz
76%
Разбиение сложной задачи на более простые и сохранение их результатов для дальнейшего использования.
1%
Решение задачи путём последовательного перебора всех возможных вариантов.
15%
Использование только рекурсивных алгоритмов для решения задач, представленных в виде графов.
7%
Решение задачи путём последовательного перебора всех возможных вариантов.
Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
В предыдущей главе мы познакомились с понятием динамического программирования. Что такое динамическое программирование? Это способ решать задачи, разбивая их на схожие подзадачи. Решение подзадач мы запоминаем и используем для конструирования общего решения. К примеру. Пусть нам нужно посчитать, сколько есть путей из города A в город Z. Мы знаем, к примеру, что до города Z можно добраться из городов X и Y. То есть, теперь нам надо посчитать сколькими способами можно добраться до городов X и Y. Это ведь точно те же задачи, только поменьше! Решая такие задачи "поменьше" и занося результаты их решений в таблицу, мы потом сможем решить и всю задачу.
В следующей главе "10. Алгоритм k ближайших соседей" мы познакомимся с одним из мощных и простых алгоритмов машинного обучения. В этом алгоритме используется довольно естественный подход - мы категоризируем новый предмет по другим предметам с похожими признаками. Рассматриваемый алгоритм прост и мощен, поэтому я крайне рекомендую с ним познакомиться.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная (мы её почти закончили!), успехов в прочтении :)
#книжный_клуб #алгоритмы
В предыдущей главе мы познакомились с понятием динамического программирования. Что такое динамическое программирование? Это способ решать задачи, разбивая их на схожие подзадачи. Решение подзадач мы запоминаем и используем для конструирования общего решения. К примеру. Пусть нам нужно посчитать, сколько есть путей из города A в город Z. Мы знаем, к примеру, что до города Z можно добраться из городов X и Y. То есть, теперь нам надо посчитать сколькими способами можно добраться до городов X и Y. Это ведь точно те же задачи, только поменьше! Решая такие задачи "поменьше" и занося результаты их решений в таблицу, мы потом сможем решить и всю задачу.
В следующей главе "10. Алгоритм k ближайших соседей" мы познакомимся с одним из мощных и простых алгоритмов машинного обучения. В этом алгоритме используется довольно естественный подход - мы категоризируем новый предмет по другим предметам с похожими признаками. Рассматриваемый алгоритм прост и мощен, поэтому я крайне рекомендую с ним познакомиться.
Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.
Книжка несложная (мы её почти закончили!), успехов в прочтении :)
#книжный_клуб #алгоритмы
Telegram
Учим Питон (Чат)
Курс с нуля: https://stepik.org/course/58852/
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Курсы для прохождения: https://docs.google.com/document/d/1N-SxSRbe5eaV3z4BEknNVB1G7EKgtfdgVmTyy-q95fY/edit?usp=sharing
Правила: https://vk.com/@learnpythonforfun-pravila-gruppy-i-chatov
Опрос по десятой главе книги Грокаем алгоритмы.
Пусть дано 12 точек: 6 точек типа A и 6 точек типа B. Нужно классифицировать новую точку по алгоритму k ближайших соседей, где k = 4. Все точки типа A располагаются на расстоянии 4 от новой точки, все точки типа B располагаются на расстоянии 3 или 2. Какой тип у новой точки?
#книжный_клуб #алгоритмы
Пусть дано 12 точек: 6 точек типа A и 6 точек типа B. Нужно классифицировать новую точку по алгоритму k ближайших соседей, где k = 4. Все точки типа A располагаются на расстоянии 4 от новой точки, все точки типа B располагаются на расстоянии 3 или 2. Какой тип у новой точки?
#книжный_клуб #алгоритмы