Category: образование

Category was added automatically. Read all entries about "образование".

Технотрек: Занятие 01: Start() { Квадратное уравнение бросает вызов; }


(Копия блога на Технотреке)

Привет!

В понедельник 18 сентября торжественно состоялось первое занятие курса по промышленному программированию на С/С++.

Квота на зачисление была 55 человек. Отбор происходил по задачам на программирование и логическим тестам.

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

Summary
Collapse )

Технотрек: Занятия 09, 10: Рекурсивный спуск


(Копия блога на Технотреке)

Summary

На лекции мы рассмотрели восстановление дерева из записи, в которой взаимоотношение узлов задано неявно, с помощью приоритетов операций, в более общем случае - с помощью грамматики. Эта задача называется синтаксическим анализом. Одно из ее решений - метод рекурсивного спуска. Несмотря на то, что он достаточно прост, к сожалению, в сети нет внятных его описаний. Поэтому на лекции мы рассматривали много примеров, рисовали деревья синтаксического разбора и читали мантры. :) Хорошая метафора рекурсивного спуска - работа строительной бригады, устроенной наподобие этого:



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

Домашнее задание
Collapse )

Технотрек: Занятия 07, 08: Построить проект, вырастить дерево, родить левого или правого сына


(Копия блога на Технотреке)

Summary

Деревья - структуры данных, где мы совсем отказываемся от линейности, даже в логическом смысле. Для родительского узла дерева существует более одного "следующего" узла - например, левый и правый, называемых сыновними или дочерними узлами. Связь с родительским узлом у дочерних узлов может как быть, так и не быть; но с ней гораздо удобнее продвигаться от листьев дерева к его корню. Мы рассмотрели разные виды организации узлов деревьев и реализации связей между узлами.

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

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

Для деревьев у нас будут три задачи, полторы из них рассматривались на прошедшей лекции: это экспертная система ("Акинатор") и убийца лаб по общефизу символьное дифференцирование.

Домашнее задание

Collapse )

Технотрек: Промышленное программирование. Занятие 03: Неубиваемый стек


(Копия блога на Технотреке)

Summary

Мы рассмотрели простейшую структуру данных - стек (буфер LIFO) и его реализацию в Си с точки зрения объектно-ориентированного программирования. Для этого мы применили логическую группировку данных (структуру, struct) и семейство функций (методов), связанных с ней. Типичными методами являются инициализация (конструкция, Stack_ctor), деинициализация (деструкция, или очистка, Stack_dtor), тихая верификация (Stack_OK) и отладочный дамп (Stack_dump). Первые две последних функции поддерживаются С++ как конструкторы и деструкторы; для последних двух нет явно поддерживаемых эквивалентов, но без них легко допустить ошибку даже в простой структуре данных и очень тяжело ее поймать. Также рассмотрели стратегии двойной проверки для динамической верификации объектов стека.

Домашнее задание

Collapse )

Технотрек: Промышленное программирование. Занятие 02: Указатели тоже бросают вызовы

(Копия блога на Технотреке)

Summary

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

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

Домашнее задание

Collapse )