search

fullstack-development / developers-roadmap

How to learn front-end or back-end development
1.18k stars 265 forks source link

mid1: переработать вопросы по типам и структурам данных #163

Closed chmnkh closed 3 years ago

chmnkh commented 4 years ago

1) Топик проработан плохо: есть куча вопросов, поставленных откровенно криво (конкретнее опишу позже). 2) Плюс, лично у меня есть ощущение, что вопросы не сильно осознанно составлялись, т.е. не понятно, к примеру, почему именно эти структуры, адт, и так далее, и что мы вообще хотим от этого топика. 3) Надо по идее какие-то нормальные ресурсы найти, потому что на тему структур и адт просто адская неразбериха: в одной и той же статье в одном предложении что-то называют адт, в другом - уже структурой, в итоге новичковый мозг просто плавиться начинает.

Znack commented 4 years ago

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

Znack commented 4 years ago

Результаты обсуждения:

Znack commented 4 years ago

@sk1e @in19farkt @Zarwlar @chmnkh @alextsk скиньте плиз ещё рекомендуемые источники

alextsk commented 4 years ago

Алгоритмы и структуры данных

Анализ

(часть первая - взгляд с высоты, не надо требовать пруфы, в основном определения и пару примеров, чтобы общее понимание сформировалось) тип, абстрактный тип и структура данных, алгоритм: определения, различия ассимптотический анализ: что такое, худший, средний, лучший случаи, время и память, O(n) и o(n), что здесь n амортизированный анализ, вероятностный анализ ( что, зачем) общие стратегии: брут форс, Divide & Conquer, динамическое прогр-е NP-complete\hard задачи, как определить, пример недетерминированные алгоритмы - что это, зачем могут понадобиться

алгоритмы gcd (все с этого начинают)) lcm karatsuba multiplication - (хорошо взрывает голову, не сложный, интересный пример алгоритмической оптимизации известной задачи)

Линейные списки

(тут можно побольше наводящих вопросов накидать)

алгоритмы

alextsk commented 4 years ago

выше набросал свое представление на 1-го мидла курсивом выделены мысли вслух, их конечно надо убрать потом)

источники - Karumanchi N. - Data Structures and Algorithms Made Easy Stephens R. - Essential Algorithms. A Practical Approach to Computer Algorithms Robert Sedgewick and Kevin Wayne - Algorithms - у них есть и на С и на яве и вроде даже на питоне, кому что нравится Cormen - Introduction to Algorithms Cormen - Algorithms Unlocked - это один Кормен но разные книги! unlocked значительно проще https://www.academia.edu/39717003/Horowitz_and_sahani_fundamentals_of_computer_algorithms_2nd_edition - хоровиц, недавно про него узнал, в целом все по делу, жалко качество не очень, свежее не нашел и Кнут конечно

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

про сложность Stephens самый простой, у Сormena подробнее, есть тета и омега но все еще сжато, у Karumanchi там куча математики, но если ее пропустить то основы понятно написаны главное не надо пугаться кучи формул, большинство там можно пропустить при обзорном чтении без ущерба

Znack commented 4 years ago

@alextsk выглядит неплохо, спасибо, что написал :) Предлагаю тогда за основу взять твой вариант, но я бы его немного сжал, мне кажется тут уже дофига тем, я бы убрал общие стратегии (которые брут форс, Divide & Conquer, динамическое прогр-е), NP-complete\hard задачи, недетерминированные алгоритмы, массивы.

И по ресурсам будет вообще супер круто, если ты прямо скажешь, в какой книге какие главы смотреть :)

Zarwlar commented 4 years ago

амортизированный анализ, вероятностный анализ ( что, зачем) общие стратегии: брут форс, Divide & Conquer, динамическое прогр-е NP-complete\hard задачи, как определить, пример недетерминированные алгоритмы - что это, зачем могут понадобиться

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

alextsk commented 4 years ago

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

я их хочу на первого потому что я планировал именно на эти темы ~3-5 часов ненапряжного чтения, т.е. очень поверхностно рассмотреть, чтоб знать что такое вообще бывает, обзор области. как анализ стоимости продукта в макконнелле, никто от него менеджером не стал) на уровне математики я с этим тоже не умею работать, но не вредно уметь опознать если тебе попадется travelling salesman. а стратегии это база для классификации алгоритмов, удобнее их потом сортировать в голове и возвращаться к ним на верхних уровнях уже не планируется.

И по ресурсам будет вообще супер круто, если ты прямо скажешь, в какой книге какие главы смотреть

тут как раз зависит от степени погружения, практически все эти темы есть во всех книгах, я лично читаю одно и если становится непонятно читаю то же самое в другой, иногда помогает) все эти темы обычно в начале, я дальше просто сам не ушел

Znack commented 4 years ago

я их хочу на первого потому что я планировал именно на эти темы ~3-5 часов ненапряжного чтения и возвращаться к ним на верхних уровнях уже не планируется.

Ну просто все равно в сумме это 3-5 часов, если ты знаешь где читать и насколько глубоко уходить, то есть тонко чувствовать границу :) У нас же по любому будет, что кто-нибудь будет в итоге заморачиваться и начнет слишком углубляться. Тут поэтому в том числе нужны ресурсы, чтобы более-менее было понятно, каких материалов достаточно.

Я предлагаю более концептуальные и более обширные вещи всё-таки повыше вынести, там тоже могут обзорно изучить тему и рассказать :)

alextsk commented 4 years ago

ну да, я там немного в кучу все собрал, если те же стратегии и анализ можно считать за концептуальные, то np и nondeterm - это скорее "неплохо бы знать". может как то более явно обозначить ожидания, например сколько времени рассчитано на изучение всего раздела? там при желании по любой из тем можно хорошо закопаться

Znack commented 4 years ago

Ну нам в идеале, чтобы на первом мидле за 20 часов можно было все вопросы разобрать. То есть если из твоего текущего варианта убрать концептуальные вещи, которые мы выше с Лехой @Zarwlar описали, но оставить-таки массивы, то примерно вроде так и получается по объему

Zarwlar commented 4 years ago

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

Есть кому что по этому пункту предложить?

alextsk commented 4 years ago

Есть кому что по этому пункту предложить?

http://web.cs.iastate.edu/~hridesh/teaching/362/07/01/papers/p50-liskov.pdf

chmnkh commented 4 years ago

Есть кому что по этому пункту предложить?

http://web.cs.iastate.edu/~hridesh/teaching/362/07/01/papers/p50-liskov.pdf

каким образом это поможет, конкретно?) это по сути пейпер только про АДТ, причем АДТ там рассматривается (если я правильно помню) сугубо с точки зрения определения типов в языке, что немного разнится с тем, как рассматривается АДТ в других источниках

про структуры данных там вообще ни слова нет

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

chmnkh commented 4 years ago

опишу проблему более подробно

Есть 2 понятия: структуры данных и абстрактные типы данных. По идее, это разные понятия. Т.е. взяв какую-то вещь, например, деревья, должно быть возможным четко сказать, что это - адт, или что это - структура. Поскольку как адт так и структура - термины сами по себе достаточно абстрактные, то четко для себя решить, где те критерии, по которым что-то можно или к структуре или к адт отнести - это, как мне кажется, нифига не просто.

И вот ты такой вроде как с понятиями ознакомился (напомню, они, на мой взгляд, довольно абстрактные), и решил погрузиться в тему глубже, посмотреть конкретные примеры, и ты начинаешь гуглить, к примеру, деревья. И ты натыкаешься на статью, в которой сначала деревья называют адт, потом структурой, потом опять адт, и т.д. Потом натыкаешься на статью, где это всю дорогу называют адт. Потом натыкаешься на ЕЩЕ ОДНУ статью, где это всю дорогу называют структурой...

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

alextsk commented 4 years ago

каким образом это поможет, конкретно?) это по сути пейпер только про АДТ,

не совсем, это пейпер с определением АДТ, из нее понятно зачем оно вообще было создано и да, дерево может быть и структурой и адт) зависит от того с какой стороны ты на него смотришь, как имплементер или пользователь. когда есть куча противоречащих источников я смотрю в первоисточник, поэтому и скинул эту бумагу, мне лично она помогла

Zarwlar commented 4 years ago

мне лично она помогла

А чем именно помогла?

Znack commented 3 years ago

Сделано вот тут https://github.com/fullstack-development/developers-roadmap/pull/203