Category: it

Category was added automatically. Read all entries about "it".

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


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

Привет!

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

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

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

Summary
Collapse )

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


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

Summary

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



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

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

Технотрек: Промышленное программирование. Занятие 07: Внезапно лаба (хеши и списки)


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

Summary

Односвязные и двусвязные списки и хеш-таблицы - классика структур данных, но для них важны правильная реализация и правильное использование. Список возникает как решение противоречия между физически линейным непрерывным размещением объектов в памяти (массив) и необходимостью быстрой вставки/удаления в среднюю часть последовательности. При этих операциях элементы массива неотвратимо надо сдвигать; на это уходит время. Мы отказываемся от того, что логически последовательные элементы будут физически последовательно (смежно) лежать в памяти, теряем формулу быстрого вычисления номера следующего элемента (n+1) и заменяем ее номером или указателем, хранящимся в самом элементе. Теперь мы можем размещать элемент в памяти где угодно, не заботясь о смежности с другими элементами и не делая сдвиги. Это и есть идея списка.

Заметим, что если нужны быстрые вставки/удаления только в начало или конец последовательности, то подойдет обычный массив. Если нужны быстрые вставки/удаления только с началом и с концом последовательности (но не с ее средней частью), достаточно кольцевого буфера. Если все же нужно реализовывать список, то лучше сразу двусвязный: памяти это займет немного больше, но все операции у него быстрые, не зависят от длины последовательности.

Одна из ужасных ошибок использования списков - непонимание того, что индексация у них кошмарно медленная. Это линейный поиск элемента в плохо кешируемом цикле, что практически так же медленно, чем поиск элемента по значению. Как у strlen(), только значительно хуже. Вот пример такого плохого кода:
for (int i = 0; i < List_Size (&list); i++)
    {
    const ListElement* elem = List_ElementAt (i);  // Та самая индексация
    ListElement_Dump (elem);
    }
Этот цикл - квадратичный по времени. Квадратичный, Карл! Не делайте так.

Правильно:
for (const ListElement* elem = List_Begin (&list); elem != NULL; i < List_Next (elem))
    ListElement_Dump (elem);
Сравнение линейных структур данных:

Collapse )

Технотрек: Промышленное программирование. Занятие 06: The Процессор, continued


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

Summary

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

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

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

Collapse )

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


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

Summary

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

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

Collapse )

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

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

Summary

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

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

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

Collapse )

Технотрек: Промышленное программирование. Старт курса


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

Привет!

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

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

Жду всех!
Наша аудитория - 430 ГК.

С уважением,

Илья Дединский
Преподаватель Технотрек@Mail.ru

Funny Train

/*
part1zan пишет в ru_cpp:

Задачка по объектно ориентированному программированию

Ребята, спасите мою жопу от злого препода.. С программированием у меня запары,а задачку нужно сдать в среду уже.. Помогите кто чем сможет.
Вот собственно как она звучит:
Collapse )

Задачи для младших туристов-водников


  1. Отправляясь в поход, начинающий каякер Канопупкин дал себе слово каждый день в походе решать по 3 задачи, которые ему задала строгая учительница Марьиванна. Сколько двоек получит Канопупкин по возвращении, если его совести хватило только на половину задач, а поход длится 10 дней?

  2. Collapse )