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

171 (2017-2018) группа

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

Студент TODO №1 №2 №3 №4 №5 №6 №7 №8 №9 Тест 1 №10 №11 Тест 2
46 Endian check 2 1 Bits Биты float (IEEE 754) Exploit O(n) vs O(n*log(n)) vs O(n^2) 1 2 3 4 1 2 3 PE 6 5 HashTable 2 3 1 Зачет
Богданов Егор 1
Дикусар Николай 1
Евгений Богданов 1
Завадский Илья 1
Келим Илья 1
Кутленков Дмитрий 1
Миронов Илья 12
Мясников Владислав 1
Орачев Егор 1
Осипова Александра 1
Радев Даниел 21
Рыбина Екатерина 1
Сергеев Егор 1
Фунт Дина 1
Ярош Дмитрий 1

Задачи

Тест 2. 13.12.17
Вопросы
  1. Зачет
Домашняя работа 11. 06.12.17
Graphviz homepage
Balanced
Optimal (в предположении, что запросов к 1 много больше, чем к остальнм узлам)
    1. Построить оптимальное (не обязательно сбалансированное) бинарное дерево поиска для набора данных в файле следующего формата
      число_1 - количество запросов_1
      число_2 - количество запросов_2
      ...
      число_n - количество запросов_n

    2. Полученное дерево вывести в исходный файл утилиты graphviz (dot). Сгенерировать изображение дерева.

    3. Добавлено позже. Проверить, генерируется ли сбалансированное дерево при равных весах

Домашняя работа 10. 15.11.17
  1. HashTable

    Реализовать хеш-таблицу. Ключи - char*, значения - int.
    - создать с указанием начального размера и используемой хеш-функции,
    - очистить,
    - вставить (ключ, значение),
    - получить (ключ),
    - проитерировать по парам (ключ, значение) произвольной функцией,
    - напечатать статистику (количество ключей, данные о длинах цепочек, ...)
    UPD: статистика оформляется отдельной таблицей, как задаче о сортировках

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

  3. Проверить наличие утечек памяти каким-либо инструментом: Valgrind, встроенные средства gcc, другие.
    Сознательно внести ошибку, убедиться, что утечка обнаруживается. Отчетность - скриншот.
    Добиться, чтобы в финальной версии утечек памяти не было. Отчетность - скриншот и комментарий, было ли полезно, или всё работало сразу, ничего не нашлось.

Тест 1. 01.11.17
Чтение строк неизвестной заранее длины
  1. С клавиатуры вводятся строка и символ, необходимо вывести на экран введенную строку, удалив из неё все вхождения символа

  2. Два неотрицательных числа заданы в двоичной форме в массивах. Элементы обоих массивов — булевые (0, 1). Написать программу, которая определяет, какое число больше.

  3. Вывести на консоль все однострочные комментарии С++ (вида "// комментарий \n") из входного файла (вместе с символами "//"). До комментария в строке может быть значимый текст, его выводить не надо, строки без комментариев не выводить. Конец строки представляется символом \n, могут быть полезны функции fgetc и feof.

  4. PE 6

    Шестая задача с сайта Project Euler https://projecteuler.net/problem=6

  5. В файле содержится 2n+1 строк. Из них n - пары одинаковых строк, последняя строка не совпадает ни с одной другой.
    вывести уникальную строку на экран.

Домашняя работа 9. 31.10.17
  1. Реализовать структуры данных и основные операции для работы с односвязными списками. Оформить в виде библиотеки, пригодной для переиспользования в последующих задачах.
    Операции - создание, вставка в начало, вставка в конец, вставка после, удаление элементов по условию (значение равно введенному), печать, очистка.

  2. Реализовать интерфейс вида
    1. Print
    2. Op 1
    3. Op 2
    ...
    n. Exit

  3. Обратить список без использования O(n) дополнительной памяти.
    В библиотеку добавляется новая функция. В интерфейс - команда её вызова.

  4. Проверить, является ли список циклическим без использования O(n) дополнительной памяти.
    В библиотеку добавляются новые функции (создать петлю от последнего элемента до n-го, проверить). В интерфейс - команды их вызова.

Домашняя работа 8. 13.10.17
  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 - не дождались ответа.

Домашняя работа 7. 13.10.17
  1. Exploit

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

Домашняя работа 6. 04.10.17
gcc x86 Assembly Quick Reference ("Cheat Sheet")
Как правильно читать объявления в Си
IEEE 754
Function pointer example
Dynamic multidimensional array example
Массивы и указатели. Некоторые нюансы.
Краткий справочник по указателям в C
Головоломка на знание одной древней особенности C. В комментариях можно найти правильный ответ и прочитать подробнее
Пример статической инициализации массива структур
  1. Биты float (IEEE 754)

    Вывести на экран float
    Пример печати числа -0.05078125:
    ___0 -5
    (-1) * 2 * 1.101
    Символ "_" использован для выравнивания. Система "съедает" ведущие пробелы.
    Для особых значений печатаются +Inf, -Inf, Nan
    Способов три: union с int и битовые операции; union со структурой с bit fields; взятие адреса и разыменование указателя, приведенного к другому типу и битовые операции
    Детали реализации:
    1. Определить структуру с двумя полями: описанием способа обработки и указателем на функцию.
    2. Написать функцию (или несколько, если некоторый код напрашивается на выделение в отдельную функцию), которая выводит на экран список способов обработки, получив массив структур, определенных в пункте 1.
    3. Пользователь выбирает способ, вводит два float. Из частного (благодаря делению на ноль мы сможем получить +Inf, -Inf и NaN) выбранным способом получаются значения знака, мантиссы, экспоненты.
    4. Полученные значения отправляются в функцию красивой печати.
    5. Не забудьте проверить, что sizeof(float) == 4.

Домашняя работа 5. 27.09.17
Задание
  1. Bits

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

Домашняя работа 4. 27.09.17
  1. Реализовать некоторые стандартные функции работы со строками
    int strlen(char*) - длина строки
    strcpy(char* dst, char* src) - копирование строки
    strcat(char* dst, char* src) - конкатенация строк
    int strcmp(char* s1, char* s2) - лексикографическое сравнение строк. Результат сравнения: 0 - равны, <0 - первая меньше, >0 - первая больше.

Домашняя работа 3. 22.09.17
  1. Endian check

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

  2. Скомпилировать и запустить программу на big-endian платформе. Попробуйте использовать QEMU (https://www.qemu.org/).

Домашняя работа 2. 14.09.17
  1. Пройти первые три уровня (10 задач)
    http://learngitbranching.js.org/

Домашняя работа 1. 06.09.17
StyleGuide
Разработчики, которые используют пробелы, зарабатывают больше
  1. Аккаунты

© 2014-2018 HwProj