Учим Питон

Еще немного про книгу "Грокаем алгоритмы". Эта книга для начинающих и подойдет для ознакомления с темой алгоритмов. Один из плюсов - алгоритмы уже реализованы для нескольких языков и их можно посмотреть на гитхаб: https://github.com/egonSchiele/grokking_algorithms Начинаем читать с главы "1. Знакомство с алгоритмами". Читаем её до следующих выходных. Вопросы можно задавать в нашем чате в телеграмме: https://t.me/learnpythonforfun_chat. #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы узнали, что такое бинарный поиск. Бинарный поиск позволяет найти нужный элемент, отсекая на каждом шаге половину элементов. Чтобы достичь этого, бинарный поиск полагается на свойство упорядоченности элементов в коллекции. Иными словами, если мы берем случайный элемент в массиве и знаем, что наш элемент больше выбранного, то нам не зачем хранить элементы меньше (левее) выбранного. Мы отсекаем ненужные элементы и повторяем операцию на оставшихся элементах, пока не останется один элемент. Этот элемент либо будет искомым, либо будет отличным от искомого. Последнее будет означать, что искомый элемент не содержится в коллекции. В следующей главе мы познакомимся ближе с понятиями списка, массива и сортировки. Все эти понятия крайне важны для программиста и постоянно используются. В следующую неделю мы читаем главу "2 Сортировка выбором". Опять же, читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с такими структурами данных, как массив и связный список. Массив может быть охарактеризован, как непрерывная последовательность элементов одного типа в памяти. Он поддерживает быстрый доступ O(1) к элементам по индексу, но удаление и вставка занимают больше времени - O(n). Список же состоит из узлов, где каждый узел связан с последующим или предыдущим (в случае односвязного списка) или с последующим и предыдущим (в случае двусвязного списка). Операция вставки и удаления в связном списке довольно просты, если у нас есть ссылка на удаляемый элемент O(1), но чтения элемента по индекс занимает больше времени - O(n). Кроме того, в этой главе мы познакомились с сортировкой вставками, которая выполняется за квадратичное время. В следующей главе "3. Рекурсия" мы познакомимся поближе с понятиями рекурсии и стека. Концепция рекурсивного вызова является одним из подходов к построению итеративных алгоритмов. Стек же является базовой концепцией выполнения программ в современных вычислительных системах. Оба понятия важны для понимания программистом. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы

Для тех, кто хочет глубже понять рекурсию, немного задач на подумать: https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Опрос по рекурсии придумать не получилось, поэтому вот вам несколько шуток про рекурсию, убедитесь, что вы их понимаете: "Чтобы понять рекурсию, надо понять рекурсию." "Определение рекурсии в энциклопедии: Рекурсия: см. рекурсия." Коктейль «рекурсивный»: 30% водки, 60% коктейля «рекурсивный». Завтра начнем следующую главу :) #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с понятиями стека и рекурсии. Стек можно представить в виде стопки тарелок, которые вы кладете одна на другую одной рукой. Извлечь можно только верхний элемент, положить новый элемент можно тоже только на верх стека. Интерпретатор использует стек для хранения последовательности вызова вложенных функций. Вызываем первую функцию - кладем указатель на неё и её параметры на верх стека. Внутри этой функции вызываем функцию - кладем её указатель и параметры поверх предыдщуих. Выходим из функции - убираем из стека верхние параметры, соответствующие функции. Кроме этого, мы рассмотрели определение рекурсии. Рекурсия характеризуется тем, что мы вызываем некую функцию, а затем во время её исполнения снова вызываем её же. Часто это необходимо, когда решение исходной задачи требует решения сходной подзадачи. К примеру, задача: разобрать матрешку. Нам необходимо выполнить следующую "функцию": разобрать_матрешку (матрешка): если разбирается внешняя_матрешка = открыть_внешнюю_матрешку() внутренняя_матрешка = извлечь_внутреннюю_матрешку() вернуть внешняя_матрешка + разобрать_матрешку (внутренняя_матрешка) иначе вернуть матрешка Надеюсь, это хоть как-то проясняет рекурсию. В следующей главе "4. Быстрая сортировка" мы познакомимся с алгоритмом быстрой сортировки и с понятиями оценки в лучшем, среднем и худшем случаях. Быстрая сортировка является одним из часто используемых на практике алгоритмов. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с парадигмой "разделяй и властвуй", с алгоритмом быстрой сортировки и оценками для среднего и худшего случая. Парадигма разделяй и властвуй предлагает подход к решению задач, когда задача разбивается на более мелкие задачи, которые решают схожим подходом. Пример этого подхода - быстрая сортировка: данные делятся барьерным элементом, остальные элементы размещаются слева от барьерного, если они меньше его, справа - если больше. Затем, к элементам слева и справа применяется тот же алгоритм: выбирается барьерный элемент и т.д. Интересно заметить, что количество действий будет разным в разных случаях. В худшем случае будет O(n^2), но в среднем - O(n log n). В следующей главе "4. Хеш-таблицы" мы познакомимся поближе с понятиям...кхм...хеш-таблиц. Оно является значимым для понимания работы со словарями и их ограничений. Ну а словари в программировании используются повсеместно. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы

Немного продвинутого материала для тех, кто хочет понять, как работает хэш-таблица в python (в интерпретаторе cpython). Собственно, ссылка на комментарий в коде: https://github.com/python/cpython/blob/main/Objects/dictobject.c#L261 #hash

Немного про книжный клуб. Мы почти дошли до середины книги. Следующая неделя - для догоняющих. Через неделю начнем новую главу про графы. #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с хэш-функциями. Они позволяют за константное время находить адрес ячейки, соответствующей определенному значение. Иными словами, любое значение трансформируется хэш-функцией в почти уникальный ключ. Пусть есть хэш-фунция h(x), тогда могут иметь место следующие равенства: h("cat") = 2 h("dog") = 4 h("mouse") = 1 И каждый раз, когда мы будем вызывать h к данным словам, мы будем получать те же значения. Хорошие хэш-функции должны генерировать уникальные значения. Если же хэш-функция выдает значение, которое уже встречалось, к примеру, h("bird") = 4, то такая ситуация называется коллизией. Хэш-функции широко применяются в программировании, в python на них построены словари. В следующей главе "6. Поиск в ширину" мы познакомимся с графами. Графы это мегаполезная структура, которая вам точно рано или поздно пригодится. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Кроме этого, мы узнаем про алгоритм поиска в ширину - один из базовых алгоритмов на графах. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с графами и поиском в ширину. Граф является довольно простой, но мощной абстракцией. Граф представляет собой набор вершин и ребер, соединяющих эти вершины. С помощью графов можно описывать самые разные сущности: маршруты, социальные связи, взаимодействия молекул и т.д. Алгоритм поиска в ширину позволяет совершить обход графа из некой заданной начальной вершины. Обход графа происходит поуровнево: сначала просматриваются все вершины, достижимые из текущей (1ый уровень), затем просматриваются все вершины, достижимые из вершин первого уровня, и т.д. В следующей главе "7. Алгоритм Дейкстры" мы познакомимся с алгоритмом нахождения кратчайшего пути во взвешенном графе (в графе, у которого ребра имеют веса). Подобные алгоритмы очень часто применяются на практике. К примеру, если вам необходимо добраться из города А в город Д, а проехать к последнему вы можете через один из городов Б, В, Г, то алгоритм нахождения кратчайшего пути поможет вам найти....кратчайший путь. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы

Итак, продолжаем читать книгу Бхаргава А. - Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. В предыдущей главе мы познакомились с алгоритмом Дейкстры. Этот алгоритм позволяет найти кратчайший путь во взвешенном графе. На каждом шаге алгоритм выбирает новую вершину, переходит по кратчайшему пути, а затем пересчитывает стоимости маршрутов к соседним вершинам - если более кратчайший существует, то обновляем стоимости маршрутов для соседних вершин. И так, пока не будет найдет итоговый маршрут. Описание - так себе, поэтому если у вас получится сделать получше, пишите в комментариях. В следующей главе "8. Жадные алгоритмы" мы познакомимся с понятием жадности. Мы узнаем, как можно решать задачи, для которых оптимальные алгоритмы работают слишком долго. Примеры такой задачи - построение оптимального маршрута через несколько точек. Жадные алгоритмы построены на удивительно простой концепции, которая, однако, позволяет достигать достаточно хороших результатов. Читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос. Книжка несложная, успехов в прочтении :) #книжный_клуб #алгоритмы