Практикум на ЭВМ

171 (2019-2020) группа

Максим Журавлев

Студент TODO №1 №2 №3 №4 №5 №6 Тест 1 №7 №8
158 Аккаунты 2 Git tutorial Bits 1 1 1 2 3 4 Base64 1 Exploit 2 O(n) vs O(n*log(n)) vs O(n^2) Сортировка строк
Антипенко Андрей 13
Аристов Дмитрий 14
Божнюк Александр 7
Вэй Юйсян 16
Зверев Константин 10
Ли Цзэминь 16
Назарова Мария 12
Олейников Андрей 10
Саулькина Екатерина 11
Слухинский Дмитрий 14
Субботин Дмитрий 10
Фаст Никита 11
Шамуров Абдумалик 14

Задачи

Домашняя работа 8. 11.11.19
[Дополнительно]Доклад Алексея Шипилёва о типовых ошибках и лучших практиках измерения производительности. Есть Java специфичные места.
Lower bound for comparison based sorting algorithms
[К задаче]mman-win32
[К задаче] Файлы, отображаемые в память (обратите внимание на дискуссию по поводу применимости подхода в комментариях)
Слайды с таблицей максимальный размер проблемы в зависимости от асимптотики и времени ожидания и оценка сложности для рекурсии
Еще одни слайды с таблицей максимальный размер проблемы в зависимости от асимптотики и времени ожидания
[К задаче] Измерние промежутков времени в C
[К задаче] Генерация случайных чисел в C
[Дополнительно] Что такое Strict Aliasing и почему нас должно это волновать?
[Дополнительно] Инициализация в С++ действительно безумна. Лучше начинать с Си
  1. O(n) vs O(n*log(n)) vs O(n^2)

    Реализовать три сортировки (обращаю внимание, на паре было сказано про две): подсчетом, основанную на сравнениях с асимптотической сложностью O(n*log(n)) и основанную на сравнениях с асимптотической сложностью O(n2). Измерить время работы и заполнить таблицу на наборах входных данных разного размера: 5, 10, 100, 1k, 10k, 100k, 1M, 10M, 100M. Допускается значение n/a - не дождались ответа.
    Массивы можно заполнить случайными числами (см. ссылку). Для воспроизводимости результата генератор инициализировать не текущим временем, а каким-либо числом.

  2. Сортировка строк

    Написать программу для сортировки строк в текстовом файле с использованием механизма файлов, отображаемых на память (memory mapped files). Строки в файле оканчиваются по правилам операционной системы (\n или \r\n). В качестве компаратора можно использовать любой адекватный поставленной задаче. Для примера достаточно больших текстовых файлов можно брать файлы с геномами из https://www.ncbi.nlm.nih.gov/genome.

Домашняя работа 7. 03.11.19
Пример статической инициализации массива структур
[Дополнительно]Массивы и указатели. Некоторые нюансы.
Краткий справочник по указателям в C
Function pointer example
Как правильно читать объявления в Си
[К задаче]gcc x86 Assembly Quick Reference ("Cheat Sheet") (AT&T syntax)
[К задаче]Еще одна шпаргалка по ассемблеру x86 (Intel syntax)
[Дополнительно]Compiler explorer
О гарантиях и ограничениях при чтении не последнего записанного в union поля
Пояснения к термину trap representation, упомянутому в предыдущей ссылке
[Дополнительно] Обзор различий между современным C и С++
Разбираемся в С, изучая ассемблер
Изучаем С используя GDB
Каламбуры типизации функций в C
  1. Exploit

    Реализовать атаку buffer overflow, написав заведомо небезопасную функцию чтения.
    В коде следующие функции:
    - main,
    - input,
    - other.
    main вызывает input, специально подобранный ввод приводит к вызову other (перезаписан адрес возврата). Other печатает что-нибудь, дабы продемонстрировать, что была вызвана. Корректное продолжение работы не требуется.
    main или input печатают любую необходимую информацию: адреса функций, содержимое стека.
    Совет: считывайте очередной int в массив, используя while(!stop) { <...>; data[i++] = x;}. Это проще, чем scanf("%s", ...).
    Отчетность - код + скриншот.

  2. Определить, на какой платформе, запущена программа: little- или big-endian.

Тест 1. 16.10.19
Base64
Пример применения Base64
Листинг
  1. Задачи, как описаны в классе

Домашняя работа 6. 15.10.19
Безболезненное разрешение Merge конфликтов в Git
Разрешение конфликтов
[Дополнительно] Устройство Даффа - для чего может потребоваться switch с case без break
  1. Доделать задачи теста:
    Посчитать n-ое число Фибоначи. Любой способ. Корректность в пределах выбранного типа данных. Без проверки на переполнение.

  2. Реализовать функцию для получения числа из строки. Минимум - корректный ответ для корректных входных данных. Максимум - решение, пригодное для практического использования: проверка входных данных, индикация ошибки.

  3. Пользователь вводит N - целое положительное число и затем N чисел из диапазона 0-255.
    Необходимо вывести уникальные значения в порядке ввода.
    Пример: 4 9 5 6 6 5 4 -> 4 9 5 6
    Замечание: очевидное решение - использовать динамически выделенный массив размера N и квадратичный алгоритм для поиска уникальных чисел, но существует решение, требующее константного количества памяти и количества операций, пропорционального длине ввода.

  4. Найти ошибки в листинге (см. ссылки тест 1)

  5. Base64

    Минимум - реализовать преобразование исходного текста в Base64 без поддержки паддинга (длина кратна 3).
    Максимум - преобразование туда-обратно с поддержкой паддинга.

Домашняя работа 5. 04.10.19
[К задаче]Карта памяти программы на языке С
Do you know what *p++ does in C?
Формальное описание терминов "аргумент" и "параметр" в контексте языка C (eng).
Передача по ссылке и по значению(eng)
  1. Данная задача с одной стороны требует знания того, что мы еще не прошли на парах: указатели, динамическое выделение памяти, с другой стороны - элементарна. Поэтому не пугайтесь.
    Распечатать по несколько адресов разных видов сущностей:
    - локальных переменных,
    - глобальных переменных,
    - пользовательских функций,
    - системных функций,
    - динамически выделенных переменных.
    Оценить, какие виды сущностей находятся рядом, а какие в разных областях памяти.
    Совпадает ли наблюдаемое поведение с теорией
    Отчетность - программа и документ с таблицей и выводами.
    Советы:
    - Для печати адреса используйте оператор & для получения адреса (если речь не идёт об указателе, см. ниже) и спецификатор вывода %p в форматной строке printf.
    - Динамическое выделение памяти:
    int* data = malloc(n * sizeof(int));
    if (data == NULL) {<обработка ошибки выделения памяти>}
    <...>
    free(data);
    Как аргумент для printf используем data, а не &data;

Домашняя работа 4. 24.09.19
[Дополнительно]Аналог закона Мура для оптимизирующих компиляторов
[Дополнительно] Бесплатного супа больше не будет - перевод статьи (2005) о конце эры выполнения закона Мура
[Дополнительно]Закон Мура
[Дополнительно]13 years after the Herb Sutter prediction. does the free lunch really over?
[Дополнительно] Закон Мура (eng)
  1. Реализовать некоторые стандартные функции работы со строками
    size_t strlen(char*) - длина строки (здесь исправил ошибку. Был Int, а не size_t)
    strcpy(char* dst, char* src) - копирование строки
    strcat(char* dst, char* src) - конкатенация строк
    int strcmp(char* s1, char* s2) - лексикографическое сравнение строк. Результат сравнения: 0 - равны, <0 - первая меньше, >0 - первая больше

Домашняя работа 3. 18.09.19
Задание
[Дополнительно]Удачная модель ветвления для Git
Коллеция трюков с битами
[Дополнительно] Как используется странная инструкция popcount в современных процессорах
  1. Bits

    В соответствие с приложенным файлом
    В задаче про каждый третий бит считаем с младшего. Должно получиться число 613566756.

Домашняя работа 2. 11.09.19
[Дополнительно]История создания Norton Commander. Часть 1 / 3
Набор ссылок на записи школы Яндекса. Нас интересует описание систем контроля версий
Точки следования
Sequence points
Style guide
Установка gcc в Linux-подсистеме Windows 10(eng)
Установка gcc в Windows(eng)
MinGW(eng)
Cygwin(eng)
Умные алгоритмы обработки строк в ClickHouse
  1. Git tutorial

    Пройти первые 3 уровня (10 задач). Полное прохождение поощряется.
    http://learngitbranching.js.org/
    Отчетность - скриншот

Домашняя работа 1. 11.09.19
Teletype as a linux terminal
  1. Аккаунты

    Зарегистрировать аккаунт на https://github.com

  2. Реализовать задачи теста, требующие написания кода, на знакомом языке программирования

© 2014-2019 HwProj