|
|
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Добрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и, главное, проработали и знают все или большую часть алгоритмов,с успехом используют их в повседневной практической детельности? Понятно, что на них основана вся computer science, и хочется приобщится к анналам... Какой подход применить, чтобы изучить их за минималльное время? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 12:27:47 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Как изучать? Читать и осмысливать. Чтобы за минимальное время? Перестать тратить мгновения быстротекущей на ерунду. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 13:36:00 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcher Кнута читают на протяжении всей жизни. Так что "изучить их за минималльное время" звучит смешно. Это что - то навроде библии для программиста - т.е. каждый раз смотришь на то - же самое по новому. Просто начни читать для начала. Я могу сказать с чистой совестью, что читал кое что из "Искусства программирования" - когда прижимало. Причем понял не все - слабая математическая подготовка. Про минимальное время прочтения Кнута забудь. Это не "что - то там для чайников за 21 день". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 20:21:16 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Если просто охота побыстрее познакомиться с основными алгоритмами - есть море книг. Есть на псевдоязыках, есть на конкретных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 20:23:19 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcherДобрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и с чистой совестью заявляю, что я его открыл дочитал до фразы не вижу ничего особенного, чтобы программировать в течении недели на полдюжине различных ассемблеров, закрыл и поставил на полку. пысы полезности, собственно, книг Кнута этим утверждение опровергать не пытаюсь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 22:57:01 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
tchingiz algo_searcherДобрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и с чистой совестью заявляю, что я его открыл дочитал до фразы не вижу ничего особенного, чтобы программировать в течении недели на полдюжине различных ассемблеров, закрыл и поставил на полку. пысы полезности, собственно, книг Кнута этим утверждение опровергать не пытаюсь. От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы". И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :) Но мне один раз реально помогло его разбирательство с комбинаторикой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 23:04:10 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
И еще, встречались злобные маньяки, советовавшие начать изучение программирование с прочтения Кнута. Это пипец. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 23:15:40 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_Lamerвстречались злобные маньякиВозможно, я ещё более злобный маньяк. Я обычно рекомендую начинать с Вирта ("Систематическое программирование. Введение", а затем "Алгоритмы и структуры данных"). И только уже потом, конечно, Кнут. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.10.2008, 23:49:59 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
ДмиДми SQL_Lamerвстречались злобные маньякиВозможно, я ещё более злобный маньяк. Я обычно рекомендую начинать с Вирта ("Систематическое программирование. Введение", а затем "Алгоритмы и структуры данных"). И только уже потом, конечно, Кнут. Нет, так нормально, вы не злобный маньяк. Но читать Кнута, и прочитать Кнута - это совсем разные вещи, вот что топиккастеру надо понять. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 00:08:35 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Да, пожалуй я не очень правильно выразился. По сути, я и имел в виду то, как ЧИТАТЬ его. На самом деле, я не новичок в области программирования, алгоритмов и баз... И присоеденюсь мыслям, звучавшим почти во всех ответах - много математики, слишком много порой, и сложно все увязать... Под быстрым изучением я предпологал, какое количество лет надо, например, чтобы изучить последовательно? Ведь наверняка, в таких институтах, как МИТ, данный труд является частью учебного процесса... Меня интересовало вот что: допустим мне хочется повысит уровень знаний в области CS и основных алгоритмов. И вот тут два пути прослеживаются: 1. Просто берем и пользуемся, как справочником, когда возникает приктическая необходимость. 2. Пытаемся изучать все подробно!? Кто как изучал? допустим в кнуте много алгоритмов, на которых, я больше чем уверен, построен тот же оракл...Писать базу свою?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 01:41:30 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcher , глупо ставить временные рамки -- это от способностей. Большинство книг (в том числе, Кнут) требуется тогда, когда надо какой-то конкретный вопрос изучить, причём тут важна полнота рассмотрения, фундаментальность. Тут с Кнутом мало что сравнится. А в общем, когда изучаешь какую-нибудь новую теорию, надо начинать с хорошего обзора, но в программировании не принято обычно обзоры писать. Поскольку Кнут в некотором смысле и математик, то у него эти обзоры как раз имеются -- смотри эти вещи в конце глав/параграфов SQL_LamerИ еще, встречались злобные маньяки, советовавшие начать изучение программирование с прочтения Кнута Это, наверное, камень в мой огород?:)) Хотя, если бы я был злобным, советовал бы туфту явную ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 09:15:24 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
То TeXpert Ну это я шутя :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 09:51:52 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcher wrote: > Добрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Моё мнение - лучше труды Кнута вообще без нужны не изучать. Читать всё там - безполезно, потому что не всем всё нужно. Читать что-то куском там практически невозможно, потому как там всё настолько контекстно зависимо, что ничего практически непонятно. Вообще, Кнут удивительно многословен, у него всегда куча лирических отступлений, не относящихся к делу, стиль изложения - излишне математичен и формален. Ну в общем, по-моему можно было бы сделать в 10 раз проще и понятнее. И конечно же, уже стала "притчей во языцах" его вымышленная ЭВМ, на АССЕМБЛЕРЕ (!) которой написаны все примеры. Ну и приведу пример моего собственного опыта. Мне надо было просто прочитать про алгоритмы обхода дерева. Открываю, ОГРОМНАЯ глава ("ура!" думаю). Читаю введение. "Ляляля ... поскольку в компьютерах применяются ТОЛЬКО бинарные деревья, то далее мы будем рассматривать ТОЛЬКО ИХ" (!) С какого бодуна он это вообще решил ? Ну и всё, вся остальная глава действительно только о бинарных деревьях, где все алгоритмы в основном строятся через рекурсию. Т.е. абсолютно безполезно для меня, поскольку мне надо без рекурсии и НЕ бинарные. > Есть люди, которые могут сказать с чистой совестью, что прочитали и, > главное, я не осилил. И не жажду. > проработали и знают все или большую часть алгоритмов,с успехом > используют их в повседневной практической детельности? Кнут не описывал вообще -то там каких-то сверхуникальных алгоритмов. Вот в книге "Всё про ТеХ" - да, есть его авторские. И ещё кажется у него был авторский алгоритм поиска подстроки в строке. Я это к тому, что не обязательно читать Кнута, можно напр. Лейзерсона сотоварищи. > Понятно, что на них основана вся computer science, и хочется приобщится > к анналам... Нет, вовсе нет. есть много других хороших и полезных книг. Кроме того, всё это во многом уже устарело. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 11:02:04 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
ДмиДми wrote: а затем "Алгоритмы и структуры данных" Вот это - вполне достойная тоже книга Ахо, Ульман и др. Более я считаю даже классическая, чем ИП. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 11:04:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_Lamer От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы". И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :) Там математика действительно на уровне школы, вопрос только в том КАКОЙ школы. Вот мне универ после школы с математическим уклоном вообще ничего не дал ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 12:03:44 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcherПонятно, что на них основана вся computer science, и хочется приобщится к анналам... Это не так, три с половиной тома Кнута это далеко не вся computer science. Например, Кнут практически не касается вопросов построения компиляторов и всего связанного с грамматиками языков. А это на самом деле добрая половина, если не больше, от compuer science. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 12:56:19 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Так, дожили, шаблоны изучать вредно, Кнута читать бесполезно. Может застрелиться? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 12:57:49 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
На счет шаблонов не согласен - в наше время когда сложность проектов стала главной проблемой, и они как раз помогают снизить ее. Тут уж надо выбирать что важнее: умение сдавать проекты вовремя, или глубина теоретических знаний. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 13:19:38 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Mike7 algo_searcherПонятно, что на них основана вся computer science, и хочется приобщится к анналам... Это не так, три с половиной тома Кнута это далеко не вся computer science. Например, Кнут практически не касается вопросов построения компиляторов и всего связанного с грамматиками языков. А это на самом деле добрая половина, если не больше, от compuer science. 5 том (если не путаю) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 13:59:30 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan) 5 том (если не путаю) Фактически состоящий из нескольких книг. Когда выйдет почитаем, а пока он только в планах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 14:50:57 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
WorobjoffНа счет шаблонов не согласен - в наше время когда сложность проектов стала главной проблемой, и они как раз помогают снизить ее. Тут уж надо выбирать что важнее: умение сдавать проекты вовремя, или глубина теоретических знаний. Да был тут весной по-моему срач был. Там меня убеждали что зная шаблоны ты их везде натыкаешь, где надо и не надо, что писец потом в коде разбираться. Но я лично накупил книг, почитываю временами, не хочу я ближе к пенсии наконец понять что лучше было всё таки изучить шаблоны :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 14:59:32 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Mike7 Gluk (Kazan) 5 том (если не путаю) Фактически состоящий из нескольких книг. Когда выйдет почитаем, а пока он только в планах. Вряд ли дождемся в этой жизни Но 4 можно сказать уже есть ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 16:09:52 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
ДмиДми SQL_Lamerвстречались злобные маньякиВозможно, я ещё более злобный маньяк. Я обычно рекомендую начинать с Вирта ("Систематическое программирование. Введение", а затем "Алгоритмы и структуры данных"). И только уже потом, конечно, Кнут. Кнута следует читать по мере необходимости, после того как будет освоен Вирт. В "Алгоритмах и структурах" он даёт хороший базис. Чтение-же "всего подряд" в сжатые сроки - это есть признак либо большого гения (в чём я сильно сомневаюсь), либо признак неорганизованности и неумения поставить конкретную цель. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.10.2008, 16:29:00 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan)Но 4 можно сказать уже есть А не знаешь, когда будет в виде одной книги? А то видел отдельными кусками. Имею в виду на русском ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2008, 09:03:42 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Специалистом себя не считаю, но все же позволю себе подлить масла в огонь и упомянуть такие книжки как, например, "Паттерны проектирования" Э.Гамма, Р.Хелм, Р.Джонсон, Дж.Влиссидес и "Совершенный код" С.Макконнелла. На мой взгляд, они могут существенно повысить навык программирования. Также представляют интерес книги про пользовательский интерфейс, но еще пока ни одной не открывал, может кто знает фундаментальную книгу по данной тематике? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2008, 21:34:53 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
W_and_GТакже представляют интерес книги про пользовательский интерфейс В топку такие книги (им тут не место)! А не то начнут предлагать изучать книги по БДЕ и всякую лабуду "за 21 день" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.10.2008, 23:47:25 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
TeXpert W_and_GТакже представляют интерес книги про пользовательский интерфейс В топку такие книги (им тут не место)! А не то начнут предлагать изучать книги по БДЕ и всякую лабуду "за 21 день" Да есть у меня в шкафу книга чисто по интерфейсу, название не помню, но вроде про 21 день там речи нет, и про БДЕ тоже :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 06:57:04 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Однозначно такие книги к программированию никакого отношения не имеют. А то я встречал и книги типа "Как работать в Internet Explorer" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 07:51:00 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
...а если уж руки так и чешутся -- возьмись за The TeXbook . Внутренний его язык поизощрённее будет, чем C++. Как осилишь -- возьмись за The METAFONTbook . Напомню, что тема называется " Изучение трудов Кнута (Как изучать) " ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 07:55:48 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
TeXpert Gluk (Kazan)Но 4 можно сказать уже есть А не знаешь, когда будет в виде одной книги? А то видел отдельными кусками. Имею в виду на русском Подозреваю, что никак не раньше чем когда выйдет одной книгой на английском Скорее всего он по любому будет разделен на несколько томов Пока что это draft ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 09:33:56 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
TeXpert W_and_GТакже представляют интерес книги про пользовательский интерфейс В топку такие книги (им тут не место)! А не то начнут предлагать изучать книги по БДЕ и всякую лабуду "за 21 день" Быть может меня не верно поняли, но я имел ввиду книги, в которых написано, как лучше спроектировать пользовательский интерфейс своей программы, т.е., грубо говоря, по каким местам надо разбросать кнопки и прочие конторолы на форме, так чтобы у пользователя не возникало проблем с использоваением вашей программы. Для пущей убедительности скажу, что в Microsoft этому вопросу уделяют достаточно много внимания, можно спорить на сколько это хорошо у них получается.. но факт остается фактом. Из книг могу упомянуть такие: "Разработка пользовательского интерфейса" Тео Мандел и "Дизай пользовательского интерфейса" Влад В. Головач ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 11:35:09 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
W_and_GБыть может меня не верно поняли, но я имел ввиду книги, в которых написано, как лучше спроектировать пользовательский интерфейс своей программы, т.е., грубо говоря, по каким местам надо разбросать кнопки и прочие конторолы на форме, так чтобы у пользователя не возникало проблем с использоваением вашей программы. Я правильно понял :) И думаю полистать такую книгу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 12:08:02 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
W_and_G TeXpert W_and_GТакже представляют интерес книги про пользовательский интерфейс В топку такие книги (им тут не место)! А не то начнут предлагать изучать книги по БДЕ и всякую лабуду "за 21 день" Быть может меня не верно поняли, но я имел ввиду книги, в которых написано, как лучше спроектировать пользовательский интерфейс своей программы, т.е., грубо говоря, по каким местам надо разбросать кнопки и прочие конторолы на форме, так чтобы у пользователя не возникало проблем с использоваением вашей программы. Вас правильно поняли. Никакой связи с тем, что в топике говориться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 14:14:34 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_LamerВас правильно поняли. Никакой связи с тем, что в топике говориться. Ну если так, то прошу прощения за флуд :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.10.2008, 17:32:07 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
W_and_G Также представляют интерес книги про пользовательский интерфейс, но еще пока ни одной не открывал, может кто знает фундаментальную книгу по данной тематике? тут нужно читать психологи и тому подобное, про когнитивно сознательное и бессознательное ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.10.2008, 06:43:38 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcherДобрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и, главное, проработали и знают все или большую часть алгоритмов,с успехом используют их в повседневной практической детельности? Понятно, что на них основана вся computer science, и хочется приобщится к анналам... Какой подход применить, чтобы изучить их за минималльное время? С чистой совестью те алгоритмы изучать можно только осмыслив каждый алгоритм и придумать себе "домашнее задание" и успешно его выполнив! Удачи:) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.10.2008, 17:50:44 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
С0ВЕСТЬ algo_searcherДобрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и, главное, проработали и знают все или большую часть алгоритмов,с успехом используют их в повседневной практической детельности? Понятно, что на них основана вся computer science, и хочется приобщится к анналам... Какой подход применить, чтобы изучить их за минималльное время? С чистой совестью те алгоритмы изучать можно только осмыслив каждый алгоритм и придумать себе "домашнее задание" и успешно его выполнив! Удачи:) Там же вроде итак тонна домашних заданий? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.10.2008, 07:25:54 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
XDiaBLoС0ВЕСТЬ algo_searcherДобрый день! У меня вопрос по томам Кнута - как изучать все эти алгоритмы? Есть люди, которые могут сказать с чистой совестью, что прочитали и, главное, проработали и знают все или большую часть алгоритмов,с успехом используют их в повседневной практической детельности? Понятно, что на них основана вся computer science, и хочется приобщится к анналам... Какой подход применить, чтобы изучить их за минималльное время? С чистой совестью те алгоритмы изучать можно только осмыслив каждый алгоритм и придумать себе "домашнее задание" и успешно его выполнив! Удачи:) Там же вроде итак тонна домашних заданий?Но зато потом... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.10.2008, 17:35:09 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Эхх, скучно, Кнута почитать, или Роберта Мартина уж дочитать сначала? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 10:04:09 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
На меня самое большое впечатление в области программирования произвела не очень толстая книга Ч.Уэзерелла "Этюды для программистов", которую, к сожалению, потерял. Даже удалось одну задачу из нее решить. Так что рекомендую не нее обратить внимание. Нового из нее мало что почерпнуть можно, а вот понимание того, что сам мало чего понимаешь - это 100%. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 12:45:11 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 14:31:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Благодарю за ссылку, но там написано "Скачать книгу с нашего сайта нельзя". Пока не разобрался в чем дело, но буду пробовать варианты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 15:14:37 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomБлагодарю за ссылку, но там написано "Скачать книгу с нашего сайта нельзя". Пока не разобрался в чем дело, но буду пробовать варианты. Там ссылка на осла. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 15:21:26 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Все. Нашел в другом месте. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.12.2008, 15:46:34 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Три тома Кнута я прочитал (и даже понял почти все, что там излагалось), и хочу сказать следующее. Для прочтения, как говорится, со вкусом его трудов необходимо: 1. Иметь математическое образование , поскольку Кнут сам был чистым математиком; 2. Иметь практикум по программированию на ассемблере, чтобы с пониманием просто НАЧАТЬ читать его первый том и про его машину MIX. Более того, желательно хотя бы на двух видах ассемблера, поскольку он предлагает гипотетическую модель и необходимо улавливать общие моменты, присущие языкам низкого уровня, а также те места, которые присущи только для его машины MIX; 3. Уже иметь опыт составления алгоритмов на алгоритмических языках высокого уровня, чтобы быть подготовленным к решению тех задач, которые предлагает автор. 4. Иметь хотя бы представление о проблемах классических операционных систем, поскольку многие алгоритмы предназначены именно для них. Поэтому я счтаю, что эта книга не может быть рекомендована как для первоначального изучения, так и для изучения программированию вообще. Например, о его втором томе "Поиск и сортировка" хочу сказать вот что. Не знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу, т.е. математически нельзя доказать, что он работает быстрее других. Работает, и все. А по поводу других алгоритмов, как утверждает MasterZiv, я также согласен. Часто предложенные алгоритмы требуется переделывать и обобщать (в худшую сторону), а для этого надо самому быть "почти готовым" изобрести нечто подобное. Я так считаю: прочтение книг Кнута на сегодняшний день мало что кому может дать, а скорее принесет больше вреда. Они больше являются своего рода тестом: если прочитал их и понял, то в какой-то мере можешь считать себя алгоритмистом, что сейчас очень редко встречается не только среди программистов вообще, но и среди программистов, занятых составлением кода программ. А вообще сейчас в программировании столь много других интересных направлений, что совсем не обязательно начинать с изучения алгоритмов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 10:29:29 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomНе знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу, т.е. математически нельзя доказать, что он работает быстрее других. Работает, и все. а можно про это подробнее? очень интересно! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 11:12:23 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Сегодня есть много предметных областей, где знания фундаметальных труднов Кнута недостаточно. Приведу один пример. Все попытки создать универсальную формулу оценки стоимости (cost) SQL запроса терпят поражение. Первый фактор. Подобрать оценку времени работы по конфигурации соединений таблиц практические невозможно. На время работы запроса влияет около 100 и более факторов (в т.ч. другие параллельно работающие запросы), и в таких условиях аналитическая формула даёт либо очень грубое приближение, либо требует корректировки весов (настройки оптимизатора) и постоянного пересбора статистики. Функция стоимости еще и не всегда бывает монотонной. Сам наблюдал ситуацию, когда уменьшение cost вызывало увеличение elapsed time. Второй фактор. Комбинаторная сложность поиска планов. Если для 2-3 таблиц реально перебрать все варианты соедниений в разумное время, то для 5-7 таблиц, задачу можно шедулить на несколько часов. Классическая школа программирования такие задачи предлагает решать комбинаторно, что само по себе является "дорогой в никуда". В далёкую бесконечность. Есть надежда, что помощь придёт со стороны Генетических Алгоритмов (ГА). И время поиска можно будет поставить в разумные пределны. К сожалению, много программистов и специалистов смежных областей (сисадмины, сетевики, электронщики) имеют об аппарате ГА очень смутное представление. Тоесть "слыхали" что-то. Как про "инопланетян". Но решать задачу будут упорно используя классические (переборные) алгоритмы. Хотя мы уже давно выросли из "детских штанишек". И на дворе стоит 21 столетие. И объёмы данных, которые надо комбинировать уже давно не укладываются в наши вычислительные мощности. И закон Мура уже не такой "Муристый" оказался. Может сумбурно выразился. Но, вот, как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 11:14:27 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomТри тома Кнута я прочитал (и даже понял почти все, что там излагалось), и хочу сказать следующее. Для прочтения, как говорится, со вкусом его трудов необходимо: 1. Иметь математическое образование , поскольку Кнут сам был чистым математиком; 2. Иметь практикум по программированию на ассемблере, чтобы с пониманием просто НАЧАТЬ читать его первый том и про его машину MIX. Более того, желательно хотя бы на двух видах ассемблера, поскольку он предлагает гипотетическую модель и необходимо улавливать общие моменты, присущие языкам низкого уровня, а также те места, которые присущи только для его машины MIX; 3. Уже иметь опыт составления алгоритмов на алгоритмических языках высокого уровня, чтобы быть подготовленным к решению тех задач, которые предлагает автор. 4. Иметь хотя бы представление о проблемах классических операционных систем, поскольку многие алгоритмы предназначены именно для них. Поэтому я счтаю, что эта книга не может быть рекомендована как для первоначального изучения, так и для изучения программированию вообще. 1) Факультет Информатики и Прикладной Математики сойдёт? 2) Писал на ассемблере. Использовал компиляторы MASM и TASM. 3) :) Это уж тем более мне не проблема. 4) А какие у них там проблемы? Всякие там семафоры с мьютексами? regom Я так считаю: прочтение книг Кнута на сегодняшний день мало что кому может дать, а скорее принесет больше вреда. Блин, про шаблоны проектирования я слышал тоже самое. Так что уж теперь, вообще ничего кроме спецификаций ЯП не читать??? Да идите ка вы на йух со своим пессимизмом, прошу прощения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 12:22:07 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regom Например, о его втором томе "Поиск и сортировка" хочу сказать вот что. Не знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу 1. Это третий том 2. Возьми массив отсортированный в обратном порядке, а затем скорми его QuickSort-у (в том виде что любят давать функциональщики, с выборкой головы списка), а затем HeapSort-у. Убедись что серебрянной пули не существует 3. Потом вспомни, что массивы далеко не всегда умещаются в оперативную память целиком и пойми для чего существуют алгоритмы сортировки на лентах После этого можешь вернуться к критике Кнута. Будет интересно послушать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:02:18 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomчто сейчас очень редко встречается не только среди программистов вообще, но и среди программистов, занятых составлением кода программ А программисты "вообще" что составляют ??? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:06:05 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
авторпоскольку Кнут сам был чистым математикомПочему был ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:08:14 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonМожет сумбурно выразился. Но, вот, как-то так. Имеются ли success story по применению ГА в оптимизаторах РСУБД ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:12:40 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Restavraciyaавторпоскольку Кнут сам был чистым математикомПочему был ? А почему чистым вопросов не вызывает ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:13:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan)Restavraciyaавторпоскольку Кнут сам был чистым математикомПочему был ? А почему чистым вопросов не вызывает ? А потому что это бред. Как понимать чистым? Он программистом то есть вообще не был? А кто ему программы помогал составлять? Это как Эйнштейн на пару с известным математиком теорию разрабатывал? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:19:41 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
По поводу программистов "вообще" могу пояснить. На сегодняшний день есть много систем, которые даже на первое место выносят то, что приложение можно создать без написания какого либо кода или с минимальными затратами. И вот работает себе такой программист, то рыбку нарисует на главной форме, то еще картинку добавит, то просмотр справочника како-нибудь соорудит, ну на крайний случай заглянет в пособие по SQL и SELECT какой-нибудь за неделю работы вымучает (в основном пробным путем) . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:19:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan) 2. Возьми массив отсортированный в обратном порядке, а затем скорми его QuickSort-у (в том виде что любят давать функциональщики, с выборкой головы списка), а затем HeapSort-у. Убедись что серебрянной пули не существует 3. Потом вспомни, что массивы далеко не всегда умещаются в оперативную память целиком и пойми для чего существуют алгоритмы сортировки на лентах Добавлю. Кнута надо изучать постоянно абстрагируясь от железа. Маэстро не очень жалует такие технологии, как мультипоточность, параллелизм. Боллее того, навязывает идею существования некой гипотетической ЭВМ, которую он создал специально для обучения, и которую во что-б это ни стало, надо изучить. Я вспоминаю свою курсовую по списковым структурам на 2 курсе универа. В попытках оптимизировать и улучшить её работу я дошёл до того, что просто не мог её сдать. Идеальное решение заводило меня в неосуществимые сроки. Многие постулаты теории алгоритмов завязаны на том, что указатель не имеет физических размеров, (а это не так), память выделяется произвольными размерами (а на самом деле memory manager выделит физически другое число), диск инерционный, медленный на random access и быстрый на sequental, доступ к оперативке быстрее по чётным адресам, чтение слов и двойных слов лучше производится по кратным адресам, хеш-таблицы не любят "реорганизаций", бинарные деревья (как структура хранения) существуют только в воспалённом мозге теоретиков и т.д. и т.д и т.п. Всё это, как снежный ком накатывается на "теорию" Кнута и выдаёт парадоксальные решения, и не очень похожие на книжные, академичные алгоритмы. Несколько дней назад в форуме один "крендель" пытался использовать метод Шелла для сортировки структур на дисковом файле. Ну... чтож. Успехов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:35:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan)Имеются ли success story по применению ГА в оптимизаторах РСУБД ? Точно не уверен. Вроде-бы PostgreSQL применяет GA. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 13:37:05 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonGluk (Kazan)Имеются ли success story по применению ГА в оптимизаторах РСУБД ? Точно не уверен. Вроде-бы PostgreSQL применяет GA. Ссылочка была бы интересна. IMHO в оптимизаторах на практике не столь желательна безошибочность, сколько стабильность и предсказуемость. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 14:37:03 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonНесколько дней назад в форуме один "крендель" пытался использовать метод Шелла для сортировки структур на дисковом файле. Ну... чтож. Успехов. Дык для того и нужно читать книжки (Кнута в частности), чтобы применять инструменты по назначению :) А своей головы за плечами никто не отменял, кстати ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 14:39:27 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Gluk (Kazan)Ссылочка была бы интересна. IMHO в оптимизаторах на практике не столь желательна безошибочность, сколько стабильность и предсказуемость. Вот маленький камент. http://www.postgresql.org/docs/8.1/interactive/geqo-pg-intro.html Добавлю. ГА оптимизатор решит только первую часть проблемы. Т.е. быстрое построение плана для большого количества джойнящихся таблиц. Все прочие задачи - остаются за кадром. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 14:47:47 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonhttp://www.postgresql.org/docs/8.1/interactive/geqo-pg-intro.html спасибо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 14:54:31 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_LamerИ еще, встречались злобные маньяки, советовавшие начать изучение программирование с прочтения Кнута. Это пипец. Зато когда на полке стоит Кнут - это выглядит круто :) А можно еще закладок с десяток в него насовать ;) Хотя для имеющих дело с математическими алгоритмами - книжка очень нужная. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 21:03:36 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Vladimir KozlovSQL_LamerИ еще, встречались злобные маньяки, советовавшие начать изучение программирование с прочтения Кнута. Это пипец. Зато когда на полке стоит Кнут - это выглядит круто :) Это ви мне? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 21:26:30 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonGluk (Kazan)Ссылочка была бы интересна. IMHO в оптимизаторах на практике не столь желательна безошибочность, сколько стабильность и предсказуемость. Вот маленький камент. http://www.postgresql.org/docs/8.1/interactive/geqo-pg-intro.html Добавлю. ГА оптимизатор решит только первую часть проблемы. Т.е. быстрое построение плана для большого количества джойнящихся таблиц. Все прочие задачи - остаются за кадром. Звиняйте, что встреваю, но есть и посвежее документация ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 22:32:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Талмуды трудов Ленина... Сочинения Толстого и Достоевского... Справочники по вышке Выгодского и сочинения Гмурмана по мат-статистике и Венцтель - дискретка. Джентльменский набор студента. Мне кажется, времена, когда люди "коллекционировали" литературу прошли. Мне пока хватает электронного варианта Кнута. Некуда ставить энти три кирпича! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 23:21:05 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
###Звиняйте, что встреваю, но есть и посвежее документация Спасибо, я не против. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.12.2008, 23:22:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Vladimir Kozlov пишет: > Зато когда на полке стоит Кнут - это выглядит круто :) А можно еще > закладок с десяток в него насовать ;) Подтверждаю. Стоит на самом красивом месте. Выглядит. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 01:30:13 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
MasterZiv, Я тут перевожу главу из PCL, можно вам потом на суд? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 01:34:27 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
У меня четверть стола занимает компьютер, четверть Кнут и Страуструп и половину книжки по математике, которую я решил постичь чуть менее, чем полностью после прочтения первого тома Кнута) Можно сказать эта книга радикально поменяла мое мировоззрение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 04:25:35 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomНе знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу, т.е. математически нельзя доказать, что он работает быстрее других. Работает, и все. скажите плиз название этого алгоритма, охота про него погуглить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 06:43:44 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
LK4D4У меня четверть стола занимает компьютер, четверть Кнут и Страуструп и половину книжки по математике, которую я решил постичь чуть менее, чем полностью после прочтения первого тома Кнута) Можно сказать эта книга радикально поменяла мое мировоззрение. У меня 2/3 стола занимает 26" монитор, а 1/3 МФУ, Кнут стоит на полке пока. Но скажите, зачем вам захотелось так глубоко познать математику? Неужели всё так плохо? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 06:56:35 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
To AVOT Да так и называется - быстрая сортировка (quicksort) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 09:27:49 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
авот, имел про этот алгоритм информацию давно и вот сейчас из Википедии: Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Самый быстрый из известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов). Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы: Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции: два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно; вычисляется опорный элемент m; индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный; индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного; если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент; если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения. QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод. На практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. И еще вопрос: как на форуме перед ответом на какой нибудь вопрос поместить в прямоугольнике ранее заданный вопрос? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 09:30:02 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomИ еще вопрос: как на форуме перед ответом на какой нибудь вопрос поместить в прямоугольнике ранее заданный вопрос? кликнуть "Цитировать", отредактировать если нужно, и перед отправкой смотреть "Предварительный просмотр" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 09:50:56 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
авотregomИ еще вопрос: как на форуме перед ответом на какой нибудь вопрос поместить в прямоугольнике ранее заданный вопрос? кликнуть "Цитировать", отредактировать если нужно, и перед отправкой смотреть "Предварительный просмотр" Спасибо, получилось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 09:54:45 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regom Например, о его втором томе "Поиск и сортировка" хочу сказать вот что. Не знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу, т.е. математически нельзя доказать, что он работает быстрее других. Работает, и все.Несомненно необходимо хорошее математическое образование чтобы понять книгу. А еще лучше если вы участвовали в математических олимпиадах. Во вторых знать ассемблер не столько обязательно, но ПОНИМАТЬ КАК выполняются дествия - нужно. А все что вы понаписали про быструю сортировку - какой-то бред. Во первых не быстрее. Во вторых для ЛЮБОГО метода есть свои доказательства. А доказать что этот метод быстрее всех и всегда - нельзя. Потому что это не так. В третьих к вашему сведенью практически все открытия, сделаны "случайно". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:23:25 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
[quot Программист 1сА все что вы понаписали про быструю сортировку - какой-то бред.[/quot] Написал не я - написано в Википедии. Или там тоже бред? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:26:25 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomПрограммист 1сА все что вы понаписали про быструю сортировку - какой-то бред. Написал не я - написано в Википедии. Или там тоже бред? Типа "моветон" наверное ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:40:05 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonМне пока хватает электронного варианта Кнута. Некуда ставить энти три кирпича! Во-во, Asus EEE занимает намного меньше места - а книжек в нем больше :) У меня из бумажных кирпичей самый толстый - это второй том Хорстмана (ну и пользы от него в повседневной практике побольше чем от Кнута) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:49:18 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_Lamer Это ви мне? А вот так тоже неплохо... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:50:34 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Замечу, что полезны оба "Кнута" . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 10:54:21 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
SQL_Lamer От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы". И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :) Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 11:14:56 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
VovkaMorkovkaSQL_Lamer От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы". И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :) Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника Особенно если ее закончил лет эдак пять назад. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 11:24:53 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regom пишет: > быстрый из известных универсальных алгоритмов сортировки массивов (в > среднем O(n log n) обменов при упорядочении n элементов). O - ВЕРХНЯЯ оценка, а не средняя. > И еще вопрос: как на форуме перед ответом на какой нибудь вопрос > поместить в прямоугольнике ранее заданный вопрос? Код: plaintext Вверху формы нового сообщения есть кнопки. Понажимайте, посмотрите что получается, потом научитесь сами их вставлять. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 11:40:13 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomОсобенно если ее закончил лет эдак пять назад. Полноте-с, батенька. Открыли справочник. Полистати-с. Освежили тык скыть голову. А учится ради сдачи экзамена это.. знаетели как-то. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 12:01:54 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Вспоминается случай. Был у нас мужик один, все рассказывал, что в университете заставил весь трехтомник прочитать, мол даже на том выдуманном "ассемблере" программы писать приходилось. И что в итоге - поработал человек программистом, архитектором, да и прошел продавать в той же сфере. Теперь наверное заказчикам мозги парит. Доход тогда отличался на порядок, то есть в 10 раз (архитектор vs торгаш), не думаю, что сейчас сильно поменялось. Резюме - само по себе изучение это хорошо, конечно, а как жизнь вывернет ... и себя знать еще важнее... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.12.2008, 13:25:53 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Вот-вот . O(n log n) - это у сортировки слиянием у квик O(n^2). На практике квик быстрее, в принципе они одинаково шустрые. Но мердж намного "надежнее", этот зверь сортирует как надо и в сроки. Квику с легкостью можно подсунуть бяку, но и там спасает random выбор медианы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 12:46:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 15:06:27 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
LK4D4Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных. ну здрасьте; приплыли; ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 16:25:15 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Книги Кнута следует изучать с листком в одной руке и карандашом в другой.Там можно всё понять.И польза от книг Кнута действительно есть,я лично читал её с удовольствием.Правда она у меня в эл.варианте,и поэтому сидя перед монитором и при этом осмысливать всё это сложновато.Намереваюсь купить третий том в ближайшие месяцы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 19:50:05 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
LK4D4Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных. За что его отмечать? Что, он чем-то существенным отличился? Его даже не рассматривают в разделах, посвящённых сортировкам. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 20:38:41 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
VovkaMorkovkaSQL_Lamer От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы". И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :) Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника Я, к примеру, в классе с историческим уклоном учился :)) Лет сто назад. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.12.2008, 22:16:51 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
regomПрограммист 1сА все что вы понаписали про быструю сортировку - какой-то бред. Написал не я - написано в Википедии. Или там тоже бред?Вы читаете невнимательно. Еще раз прочтите статью - даже там написано что он не является "быстрейшим": Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных Во вторых - при объемах списка сортировки более чем объем памяти - (что в принципе нормальное явление для больших баз) очень сильно влияеет и другой недостаток этого метода: При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна.Что позволяет методам не так интенсивно работающим с памятью обойти его. В третьих - покажите ОТКУДА в вкипедии вы звяли слова что этот метод был открыт случайно, а не являлся плодом долгих поисков. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.12.2008, 10:32:34 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
retty_jj_007Вот-вот . O(n log n) - это у сортировки слиянием у квик O(n^2). На практике квик быстрее, в принципе они одинаково шустрые. Но мердж намного "надежнее", этот зверь сортирует как надо и в сроки. Квику с легкостью можно подсунуть бяку, но и там спасает random выбор медианы introsort вполне может распознать бяку и отказаться от квика. глянул в /usr/include/c++ - g++ юзает именно интро. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.12.2008, 16:03:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
algo_searcherкакое количество лет надо, например, чтобы изучить последовательно? до гроба, это наша участь! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.12.2008, 23:52:50 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Программист 1сПравда, вероятность возникновения худшего случая ничтожна. Живо вспоминается анекдот про роту солдат и вероятность встретить на улицк 10 мужчин подряд ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 09:41:22 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Как я понимаю, здесь все - большие знатоки по части алгоритмов. Позвольте вам задачку подкинуть: Имеется множество одномерных отрезков вида: (x_left,x_right). Требуется так организовать это множество (список), чтобы для заданного x временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right в большинстве случаев была меньше O(n), где n- количество отрезков. PS: фраза "в большинстве случаев" означает: количество нужных отрезков обычно намного меньше n ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 12:24:07 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчность Имеется множество одномерных отрезков вида: (x_left,x_right). Требуется так организовать это множество (список), чтобы для заданного x временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right в большинстве случаев была меньше O(n), Что значит "организовать"? Отсортировать? Или что-то другое? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 13:37:00 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
mayton Что значит "организовать"? Отсортировать? Или что-то другое? - Организовать структуры данных(иерархию классов). Разумеется для быстрого поиска понадобится предобработка(скорее всего сортировка данных по какому-либо признаку(тоже непонятно по какому)). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 14:47:02 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
По вопросу о поиске подходящего отрезка будем считать, что системе небходимо максимально быстро найти первый подходящий отрезок и неважно за счет чего: то ли упорядочивания, то ли какого либо поиска - тут отражена реальная ситуация, когда необходимо решить поставленную задачу, но не сразу ясно, за счет какого алгоритма. Я бы интуитивно поступил так. Все отрезки рассматривал как лес деревьев, в каждом из которых отрезки не пересекаются и упорядочены не по координатам левого и правого конца, а по координатам середины. Тогда в процессе поиска по дереву мы быстро найдем левого и правого соседа точки Х, затем проверим принадлежит ли правый, или левый, или вообще X между двумя отрезками. В последнем случае переходим к другому дереву и т.д. При добавлении нового отрезка пробуем его разместить в ранее существующих деревьях между отрезками без пересечений, а если не получается - заводим новое дерево. В общем такие туманные предположения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 14:47:44 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Также хочу добавить, что первое дерево при добавлении отрезков необходимо делать наиболее эффективным. Т.е., если получилось так, что первое дерево содержит отрезки (a1,b1) и (a2,b2), и вот добавляется отрезок (a1,b2) (или чуть шире, но не пересекаясь с существующими отрезками в этом дереве). Тогда для устранения "провала" между b1 и а2 новый отрезок вносим в первое дерево, а отрезки (a1,b1) и (а2,b2) убираем куда-нибудь подальше (пытаемся встраивать в последующие деревья или, быть может, заводим новые). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 15:29:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
По моему, эта задача уже решена (в общем случае) Гуттманом путем построения специального вида дерева (R-Tree) для индексации и быстрого поиска пространственных данных. Однако для наихудшего случая, логарифмическое время не гарантируется, поэтому здесь нужна дополнительная информация. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:03:15 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Спаибо большое за идею!!! : regom Все отрезки рассматривал как лес деревьев, в каждом из которых отрезки не пересекаются и .... Можно организовать список массивов (лес массивов) каждый массив хранит упорядоченные координаты концов отрезков, отрезки из 1 массива-непересекаются. Таким образом, каждый из массивов может содержать не более 1 искомого отрезка. И по каждому из таких массивов можно осуществить бинарный поиск. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:04:20 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчностьСпаибо большое за идею!!! тьфу Спасибо :) Сомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:09:41 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчностьСомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) А зря. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:39:31 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonалчностьСомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) А зря. Интересно, а в чём смысл?(в 2-х словах) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:58:24 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчность, > Имеется множество одномерных отрезков вида: (x_left,x_right). > Требуется так организовать это множество (список), чтобы для заданного x > временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right > в большинстве случаев была меньше O(n), > где n- количество отрезков. у тебя имелись в виду одни требования, но в постановке задачи они не отражены. Очевидно ты имел в виду что требуется уметь еще и быстро добавлять/удалять новые отрезки. Но ты это не написал. Если быстро добавлять/удалять новые отрезки не нужно, то решение двольно очевидно -- просто бинарное дерево из всех концов отрезков, а в каждом узле сохраняешь информацию о тех отрезках которые "контролируют" данный участок. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2009, 20:52:38 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1344725]: |
0ms |
get settings: |
7ms |
get forum list: |
14ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
173ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
129ms |
get tp. blocked users: |
2ms |
| others: | 217ms |
| total: | 558ms |

| 0 / 0 |
