Где заботать использование инвариантов в циклах, сортировках и т.п.
Если стоит задача написать эффективный в вычислительном плане цикл, можно почитать dragon book и все, что связано с цикловыми оптимизациями. А лучше научиться стрить по циклу control flow и data flow графы на бумажке. Сразу станет понятно каким образом написать его оптимально. А если нужно, чтобы цикл выглядел красиво, незнаю где прочитать. Можно поробовать построить матрицу инцидентности в узлах которой стоит зависимость между стэйтментами. Ну и по ней минимизировать высоту дерева предикатов.
Кормен же.
Например тут: http://e-academy7.narod.ru/COURSES/PROGRAM/LITERATURA/01shen...
Хорошо, жалко нет теории, жалко кривой паскаль, но в общем-то подходит, почитываю потихоньку.
Если стоит задача написать эффективный в вычислительном плане цикл, можно почитать dragon book и все, что связано с цикловыми оптимизациями. А лучше научиться стрить по циклу control flow и data flow графы на бумажке. Сразу станет понятно каким образом написать его оптимально. А если нужно, чтобы цикл выглядел красиво, незнаю где прочитать. Можно поробовать построить матрицу инцидентности в узлах которой стоит зависимость между стэйтментами. Ну и по ней минимизировать высоту дерева предикатов.Слишком высоко, мне не хватает базовых "школьных" скиллов сделать хотя бы правильный, а потом уже эффективный цикл, а не знания об устройстве компиляторов.
Кормен же.Можно подробнее?
Полное имя, название книги?
Хорошо, жалко нет теории, жалко кривой паскаль, но в общем-то подходит, почитываю потихоньку.У этой книги много преимуществ =) Она тонкая, темы изложены коротко, понятно и интересно.
Pascal выбран, наверное, потому что его преподают в школах. Однако можно упражняться переписыванием на C/C++. Хотя и не понятно, зачем.
Что приятно - перед циклами в комментарии выписан инвариант — можно ощутить, что это такое, и зачем оно нужно, на примере живого кода.
Тут рекомендовали книгу Кормена Лейзерсона, Ривеста, Штейна). Она классная, но ещё и толстая. Не помню точно, но мне кажется, что явно в псевдокоде программ там инварианты не выписываются, да и в оглавлении их тоже нет. Однако инварианты упоминаются в доказательствах оценок трудоемкости. По этой книжке лучше учить разные алгоритмы и структуры данных.
Теорию самих инвариантов можно, скорее всего, найти в книгах про верификацию компьютерных программ и, наверное, в разных упоротых книгах про теоретические основы информатики. Но не думаю, что это стоит читать с самого начала.
На всякий случай вот ворох разных ссылок:
http://www.cs.tufts.edu/~nr/cs257/archive/robert-paige/invar...
http://en.wikipedia.org/wiki/Invariant_%28computer_science
http://en.wikipedia.org/wiki/Loop_invariant
http://stackoverflow.com/questions/112064/what-is-an-invaria...
http://programmers.stackexchange.com/questions/165816/why-ar...
Тут рекомендовали книгу Кормена Лейзерсона, Ривеста, Штейна). Она классная, но ещё и толстая. Не помню точно, но мне кажется, что явно в псевдокоде программ там инварианты не выписываются, да и в оглавлении их тоже нет. Однако инварианты упоминаются в доказательствах оценок трудоемкости. По этой книжке лучше учить разные алгоритмы и структуры данных.Инварианты там упоминаются в примерах и упражнениях, например, http://clrs.skanev.com/02/02/02.html.
Ну и естественно не предлагается читать всего кормена, для понимания инвариантов достаточно в первые пару глав вникнуть.
Оставить комментарий
araql
Никогда не сталкивался с учебником, в котором бы правильно учили составлять циклы вроде while красивые, без лишних инструкций до и после цикла и т.п.Никогда, собственно, не учился это делать.
На собеседовании в Яндексе предлагали мыслить "какой здесь инвариант?" - никогда так не делал.
Я догадываюсь, что по этому можно мегабайтную книжку написать, посоветуйте, пожалуйста, что-нибудь разумного объёма, хотя бы ознакомиться, примеры и т.п. Английский (лучше даже русский языки.