~ 565 - 567 дни 👨‍💻 | Графы

Последние дни знакомился с графами.

Графы - это структура связанных данных. Она состоит из вершин и ребёр.
Рёбра - это связи между вершинами.

Графы похожи на деревья. Точнее деревья являются частным случаем графов.

Смежные вершины - это вершины непосредственно связанные между собой.
Вершины могут быть связаны между собой цепочкой промежуточных вершин.

Связный граф - это граф, в котором все вершины связаны между собой и есть возможность из любой вершины добраться до любой вершины.

Направленный граф (ориентированный) - это граф с рёбрами, у которых есть направление.

Циклический граф - это направленный граф, ребра которых замыкаются в кольцо. В таком случае возможен бесконечный цикл.
Ациклический граф не имеет подобного кольца.

Взвешенный граф - это граф, ребра которого имеют свой вес. Например, указано расстояние между городами.

Вершины обычно хранятся в виде объектов класса в массиве.
Рёбра (т.е. связи между вершинами) реализуются 2-мя способами:
1) Матрица смежности;
2) Список смежности;

Реализовал структуру данных и методы вставки вершины/связи, удаления вершины/связи, проверка смежности вершин.

Покрыл код тестами.

P.s. как здорово, что прошлым летом я прорешал большое кол-во маленьких задач по работе с матрицами на python. 🤓

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/graph

~ 568, 569 дни 👨‍💻 | Поиск пути в графе, чётные деревья

За эти два дня написал 2 метода:

1) Поиск пути в графе (обход в глубину).

Ищем путь из вершины А к вершине Б.
Метод возвращает список вершин от А до Б.

Ссылка на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/b888bc9ef1116eb3383e44769b4473bf3fcda893/data_structures/graph/simple_graph.py#L50

2) Разделение дерева на чётные поддеревья.

Дано дерево. Нужно разорвать в дереве связи между узлами таким образом, чтобы получилось максимально возможное кол-во чётных деревьев.
Метод возвращает список узлов, между которыми нужно удалить связь

Ссылка на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/b888bc9ef1116eb3383e44769b4473bf3fcda893/data_structures/trees/SimpleTree.py#L89

Код покрыл тестами.

~ 570, 571 дни 👨‍💻 | Поиск пути в графе (обход в ширину)

Занимался над реализацией метода поиска пути в графе через обход в ширину.

Данная реализация позволяет получить кратчайший путь. Это его отличает от обхода в глубину.

Кратчайший путь мы получаем так как обходим все смежные вершины последовательно. И только потом опускаемся на уровень вниз.

Сам метод поиска реализовать было относительно не сложно.
Довольно много времени провёл над решением возврата пути из вершины А к вершине В.

Долгое время не получалось вернуть верный путь - то лишняя вершина попадала в результат, то наоборот одной вершины не хватало.

Код покрыл тестами.

С кодом можно ознакомиться по ссылке на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/graph/simple_graph.py#L84

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░  90%

Потрачено в этом году👆👆👆

Ещё 10% чтобы закрыть оставшиеся задачи поставленные на этот год.

~ 572 день 👨‍💻 | Уязвимые вершины в графе

Реализовал метод нахождения уязвимых вершин в графе.

Уязвимые вершины - это вершины, которые не в ходят ни в какой треугольник.

Треугольник вершин - это когда у смежных вершин есть связь.

Например, у вершины А есть смежные вершины В и С. Если у вершин В и С есть связь, то вершины устойчивы, они связаны в треугольник.

Если вершина не имеет ни одной связи между смежных вершин, то данная вершина уязвимая.

Код покрыл тестами.

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/graph/simple_graph.py#L110

~ 573, 574 дни👨‍💻 | Итоги месяца

В ноябре изучал деревья, пирамиды, графы.
Создавал структуры и их методы.

Наибольшие трудности испытал с удалением узлов из бинарного дерева поиска.
Довольно хорошо прокачал навык написания рекурсивных функций. Хорошо усвоил особенности "пирамиды" ("кучи"). Понравилось искать пути в графе. Теперь точно знаю разницу между обходом в глубину и обходом в ширину. Понравилось строить двоичные деревья поиска различными способами.

Не устаю восхищаться подходом изучения алгоритмов и структур данных с обязательным написанием тестов. Благодаря тестам находил такие ошибки в алгоритмах, которые без тестов невозможно было бы обнаружить. Также из-за наличия тестов получалось легко вносить изменения в ранее написанные методы.

Улучшился навык чтения и написания кода в целом. Код удается писать более чисто, без лишних вложенных конструкций или излишних условных операторов. Стал чаще разбивать большие функции или методы.

А как у вас прошел месяц?

Что у меня по достижению сверхцели?

'''Сверхцель: стать ТОП-специалистом в ИТ через 5 лет. А именно уметь проектировать и реализовывать сложные проекты на миллионы строк кода.'''

Прошел уже год. Что мы имеем? =)

Календарный год начинался насыщенно. Читал много книг, занимался на курсах, развивал LinkedIn, общался с другими разработчиками, активно общался с рекрутерами, проходил собеседования.

После февраля, темп значительно снизился, но к апрелю восстановил учебу. Активно занимался английским.

В начале июня сменил работу с хорошим приростом в ЗП. На текущей работе получаю много задач, соответственно получаю много коммерческого опыта.

В начале августа завершил 10-ти месячный курс Яндекс.Практикума по разработке сервисов на Django. Курс реально большой, знакомит с многими актуальными навыками работы. Довольно хорошо выработался навык написания чистого кода по стандарту PEP8. На курсе было много хорошего. Иногда открываю материалы и перечитываю. При этом рекомендую на него записываться имея некоторый багаж знаний и навыков за плечами. Из минусов могу назвать, что сейчас навыки backend разработки не применяю, на django сервисы не пишу.

В августе начал активно изучать АСД. Это крайне важный блок, который необходимо изучить на хорошем уровне. На сегодня изучил 15 структур данных, написал к ним методы, покрыл код тестами.

В целом я доволен своим вектором развития. =)

Что дальше?
Начал изучать ООП. И не просто ООП, а ООАП (объектно-ориентированный анализ и проектирование).

P.s. прошел 1 год из 5-ти.

581 день 👨‍💻 | Абстрактные типы данных (АТД)

Не писал здесь почти 2 недели. Активно изучаю ООАП.
Постепенно буду отписываться по данной теме.

Что такое абстрактный тип данных (АТД)?

Это самое базовое понятие в ООП, на основе которого следует проектировать любые объектно-ориентированные программы.

Это более высокий уровень абстракции, чем класс.
Если пройти сверху вниз по уровням абстракции, то получается следующее:
1) АТД
2) Класс
3) Объект класса

АТД - это класс, но без реализации.

АТД определяет допустимое множество объектов, а также допустимый набор методов над этими объектами. Просто задается тип данных и указываются допустимые методы без их конкретной реализации.

АТД - это абстрактный класс.

Класс - это реализация АТД.
В классе доступны поля и методы, которые прописаны в АТД. А все вспомогательные методы и поля, которые не прописаны в АТД, приватны и недоступны для внешнего мира.

———
Например, можно посмотреть АТД динамического массива по ссылке на гитхаб.
АТД DynArray и его реализация в виде уже готового класса.

Как всегда код покрыл тестами.

https://github.com/avagners/OOAP/blob/main/dyn_array/DynArray.py

С наступающим Новым годом! 🎄🎄🎄

Напишу пару слов.

Год выдался хорошим. Возможно, самым успешным в плане выполнения поставленных целей.

Завершил ряд курсов, среди которых большой курс на ЯП. Прочитал ряд книг по Computer Science. Изучил базовые структуры данных на довольно хорошем уровне.

Закрепился в профессии. В июне поменял место работы с ростом в доходе. Сейчас у меня много задач. А это значит много опыта.

Обновил себе ноутбук. Эта покупка является своеобразным символом моих достижений в освоении новой профессии.

В следующем году нужно приложить ещё больше усилий, чтобы реализовать поставленные цели. "Дисциплина, усердие, внимание!" - вот мой девиз следующего года)))

Вперёд, в 2023 год! 🎉🎊🎉🎊🎉🎊

Продолжаю изучение ООАП.

После изучения абстрактных типов данных (АТД) и практической отработки на 10 структурах данных приступил к изучению наследования, композиции и полиморфизма в ООП.

Все мои АТД можно посмотреть по ссылке на гитхаб: https://github.com/avagners/OOAP/tree/main/part_1

Есть два фундаментальных вида отношений между классами в ООП: наследование и композиция.

Наследование -- это отношение "является" (is-a), когда один класс является потомком другого класса.

Композиция -- это отношение "содержит" (has-a), когда один объект содержит объект другого класса (как поле соответствующего типа).

Три разные возможности наследования:
-- расширение класса-родителя (наследник задаёт более общий случай родителя);
-- специализация класса-родителя (наследник задаёт более специализированный случай родителя);
-- комбинация нескольких родительских классов.

#ООП

Зарегистрировался на HackerRank.👨‍💻

Как минимум ближайшие 30 дней буду решать задачки на данном ресурсе.
Хочу проверить навыки SQL и Python.

Сегодня решил 13 задачек:
- 5 на Python;
- 8 на SQL;

Получил первые звёздочки)😁

гоу со мной)

​Получил еще по одной звёздочке =)

​Итоги 7 дней на HackerRank.

Всего решено 76 задачек, из которых:
- 45 на SQL;
- 31 на Python;

По SQL уже получил золотой значок)