Форум DL

My Profile

Я решил получать обратную связь после каждой лекции (по желанию студентов).
Возможно такое более интенсивное общение будет способствовать повышению качества занятий БОЛЕЕ ОПЕРАТИВНО, а не на "будущий семестр".

Я буду выкладывать план лекции. А студенты могут в своих ответных сообщениях писать, что понравилось/не понравилось/изменить ПОСЛЕ КАЖДОЙ ЛЕКЦИИ.

My Profile

В процессе изучения двух предыдущих предметов
"Организация и функционирование ЭВМ",
"Архитектура вычислительных систем"

Студенты получили навыки:
- анализа и проектирования цифровых устройств
- программирования на языках ассемблера и C-MPA
- ? установки новых заданий для DL

В рамках ПАПВС-2009 предполагается
знакомство с новой теорией по проектированию, а также
совершенствование полученных практических навыков.

СУРС (6 часов)

- студенты (можно в команде) готовят модель полезного цифрового
устройства (гаджета), попутно при желании выставляя на DL
фрагменты в качестве заданий на проектирование/программирование

- студенты (можно в команде) готовят доклад (с картинками и иллюстрациями), по теме, согласованной с преподавателем, загружают его в теорию и читают доклад на лекции

В конце семестра невыполненный СУРС выставляется как пропуск 3 пар.

Как зарабатывать оценку в течение семестра.

Лекционные занятия

В начале лекции - записываем план. Те, у кого есть на лекции
ноутбук, могут не записывать - план лекции выложен на форуме.
По ходу лекции можно опережать лектора, активность поощряется
бонусными баллами. В конце лекции пишется контроль теории
(например, последние выполненные студентом три пункта плана).
За контроль теории можно получить оценку от 0 до 3.

Каждую неделю контрольная работа - задачи на разработку схем устройств или программ.

Кроме того, имеется папка с индивидуальными заданиями.
Каждая задача засчитывается только первому решившему.
В каждой теме студенту засчитывается только ОДНА задача.

Имеется возможность ставить новые задачи на проектирование
и программирование. Темы задач необходимо согласовывать с
преподавателем - нам не нужны простые и неинтересные задания.

Еженедельный бонусный конкурс на САМОЕ КРАСИВОЕ РЕШЕНИЕ
подробности на форуме

- Учимся думать-2009 (1-5) в курсе "Информатика 2008-2009"
бонусы (за решение и новые идеи) + самоучеба + информация для нас

План лекции 1. Каскадирование логических элементов

1. Определение логических операций и логических элементов
(AND OR XOR NOT)
2. Каскадирование логических элементов
(2AND -> 8AND, 2OR -> 8OR, 2XOR - 8XOR, NOT -> 8NOT)
3. Определение комбинированных логических операций
AND-NOT OR-NOT XOR-NOT
4. Каскадирование комбинированных логических операций
8AND-NOT, 8OR-NOT, 8XOR-NOT
5. 2-битовая беззнаковая схема сравнения
6. 2-битовая знаковая схема сравнения
7. 4-битовая беззнаковая схема сравнения (каскадированием)
8. 4-битовая знаковая схема сравнения
9. 32-битовая беззнаковая схема сравнения
10. 32-битовая знаковая схема сравнения

Приветствуется загрузка в новые задачи заданий,
спроектированных на лекции.

My Profile

На лекции 1 мы сделали только до 2-битовой беззнаковой схемы сравнения включительно.

Попытались сделать двух-битовую знаковую (+1 бонусный балл за контроль теории):
Евстратов, Лыщенко, Баразновский, Белякова, Полевиков

Попытались пойти еще дальше (+2):
Викторович, Войтович Павел, Чаховский, Журавлев

Есть претензии к контролю теории
(в следующий раз будет снижена оценка при таком выполнении):
Янкович, Полховский

My Profile

Лекция 2. Продолжение лекции 1

6. 2-битовая знаковая схема сравнения
Каскадированием:
7. 4-битовая беззнаковая схема сравнения
8. 4-битовая знаковая схема сравнения
9. 32-битовая беззнаковая схема сравнения
10. 32-битовая знаковая схема сравнения

My Profile

Михаил Семёнович, не знаю уместно ли моё замечание, но Пинчук Дима с нами уже не учится. Логично было бы его убрать из таблицы результатов ПО-31.

My Profile

Спасибо, убрал.

My Profile

Лекция 2. Продолжение лекции 1

Я подумал, без подсказки не обойтись.
Беззнаковые компараторы:
Итак сначала мы возвращаемся к схеме 1-битного.
Двухбитный компаратор как каскадирование двух 1-битных.
4-битный как каскадирование двух 2-битных.
8-битный как каскадирование двух 4-битных
16-битный как каскадирование двух 8-битных.
32-битный как каскадирование двух 16-битных.

Надеюсь со знаковыми компараторами передовики разберутся по аналогии сами и нам объяснят.

My Profile

4-хбитовая знаковая система сравнения (каскадированием). Как это работает?
Для начала представим числа, которые у нас имеются.
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
-------------
1000 -8
1001 -7
1010 -6
1011 -5
1100 -4
1101 -3
1110 -2
1111 -1

Как видно из этой "таблицы" все числа, и отрицательные, и положительные, располагаются по порядку возрастания. Вследствие чего упрощается процесс их сравнивания. Поясню поподробнее. Мы берём какое-нибудь число, например, 3 (0011) и сравниваем его с -7 (1001). В беззнаковой системе сравнения второе число окажется больше первого. Для того, чтобы этого избежать, мы инвертируем первый (старший) бит в каждом числе, в итоге получая вместо отрицательного числа число положительное, а вместо положительного, число, большее на 8. То есть, не имеет значения, отрицательное число или нет, результат такого сравнения всегда будет однозначно верен. Если мы сравним два отрицательных числа (1000 и 1001), то при инвертировании старших бит этих чисел, получим два новых числа (0 и 1), которые, тем не менее, сохраняют свои свойства сравнения друг с другом.
Немного запутанно, зато подробно

Итак, подведём итоги. Для реализации этой схемы, нам необходимо иметь 4-хбитовый беззнаковый компаратор (CMP4), на входы которого подаются наши числа, у которых старшие биты инвертированы, то есть числа:
na3,a[2-0]
nb3,b[2-0]
где na3 и nb3 - инвертированные биты.

My Profile

Самое красивое объяснение сделала Аносова Алина (+10 бонусных баллов), далее идет ее текст дословно:

Запишу числа от 7 до -8 в порядке убывания:
 7     0111               1111    15
 6     0110               1110    14
 5     0101               1101    13
 4     0100               1100    12
 3     0011               1011    11
 2     0010               1010    10
 1     0001               1001     9
 0     0000     ====>     1000     8
-1     1111               0111     7
-2     1110               0110     6
-3     1101               0101     5
-4     1100               0100     4
-5     1011               0011     3
-6     1010               0010     2
-7     1001               0001     1
-8     1000               0000     0
Инвертирую третий бит и результат записываю рядом.
Теперь видно, что получились числа в беззнаковой двоичной 
системе счисления от 15 до 0 и для них эта схема будет работать 
правильно (см.выше)

Войтовичу Павлу, который проявил инициативу и попытался объяснить результат в форуме, +5 бонусных баллов.

Есть, к сожалению, и отрицательные примеры:

Шимчик О.А.

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

Строго говоря это мои же слова - но я их высказывал в качестве СОМНЕНИЯ в корректности работы схемы, а не в качестве ДОКАЗАТЕЛЬСТВА ее некорректности!!! Вы учитесь на МАТЕМАТИЧЕСКОМ факультете и должны понимать, что является ДОКАЗАТЕЛЬСТВОМ, а что нет !!!

Шведов Андрей

Схема работает неправильно, 
т.к. при сравнении чисел с разными знаками в первых битах чисел
просто инвертируются биты.

Большаков Валентин

Рассмотрим 5 случаев сравнения:
"+" и "+", "-" и "-", "+" и "-", "0" и "+", "0" и "-". 
Подставить по одному примеру в каждый случай, и,
если получиться, то схема верна

У меня следующие существенные замечания:
1. Один или несколько подставленных примеров В ПРИНЦИПЕ не могут служит доказательством. Это все равно что, программа работающая на нескольких тестах. Из этого НЕ СЛЕДУЕТ, что она работает на ВСЕХ возможных тестах. Примеры могут служит только для доказательства НЕРАБОТОСПОСОБНОСТИ схемы, если мы найдем ХОТЬ ОДИН такой пример.
2. Кому предлагается делать эти подстановки? Мне? А Валентин что делал у нас на лекции?

С одной стороны, я хотел бы похвалить эту тройцу, что они имеют смелость иметь собственную точку зрения. А с другой стороны, у меня к ним ДВЕ претензии:
1. Надо осознать, что такое доказательство.
2. По-моему, их ответы во многом определены их ЛЕНЬЮ - как в течение всей лекции (они оказались "не в теме обсуждения"), так и в период "контроля теории", когда в порядке РАЗМЫШЛЕНИЯ над вопросом достаточно было просто (как это сделала Алина и многие другие) выписать все числа в порядке убывания и посмотреть, что станет с числами после инвертирования их старшего бита.

My Profile

Вопрос был в том, как сделать из беззнакового компаратора знаковый. Ведь можно просто прибавить к каждому из чисел 2^(n-1) (n - количество бит). Никто ведь не будет спорить, что от этого результат сравнения не изменится? Не изменится, но оба числа станут положительными и можно будет применить беззнаковый компаратор.

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

для 4-битов:

-положительные
  0xxx
+1000
  1xxx - увеличилось на 8 (2^3)

-отрицательные
  1xxx
+1000
1|0xxx - увеличилось на 8
^
|
"уходит", т.к. у нас 4 бита
мы получили 2 числа в беззнаковой форме, к которым можно применить беззнаковый компратор.

Короче фишка в том, что инвертируя старший бит, мы прибавляем к обоим числам одно и то же число, делая их положительными. Результат сравнения от этого не меняется.

My Profile

+10 бонусных баллов Климовичу Диме.
Жалко, что такое простое и понятное объяснение мы не услышали ВЧЕРА.
Но лучше позже, чем никогда

My Profile

План лекции 3. Каскадирование дешифраторов
1. УГО и определение дешифратора
2. Логические функции 1/2/3-битного дешифратора.
3. Функциональная схема 2-битного дешифратора
4. 4-битный дешифратор из 2-битных (каскадирование).
5. 16-битный дешифратор из 4-битных (каскадирование).
6. Задачи с использованием дешифратора.
7. Ассоциативная память (регистры + компараторы).

My Profile

Лекция 4. Каскадирование шифраторов

Бонусы за активную работу на предыдущей лекции

 Баразновский - 10
Журавлев     - 10
Поляков      -  5
Пинчук       -  3
Шведов       -  3

План

1. УГО и определение шифратора
2. Логические функции 1/2/3-битного шифратора.
3. Функциональная схема 2-битного шифратора (2-1)
4. 4-битный шифратор из 2-битных (4-2) каскадирование.
5. 16-битный шифратор из 4-битных (16-4)каскадирование).
6. Шифраторы 64-6, 256-8
7. Задачи с использованием шифратора.
8. Ассоциативная память (регистры + компараторы).

My Profile

Лекция 5. Каскадирование шифраторов (продолжение)

Чемпионат матфака по программированию

Открытый чемпионат матфака по Кенгуру

Бонусы за активную работу на предыдущей лекции

 Баразновский - 10
Белякова     -  2
Тюленкова    -  2
Климович     -  2
Евстратов    -  2
Викторович   -  2 
Лыщенко      -  1

Бонусы за контроль теории
(сделано БОЛЬШЕ, чем мы сделали на лекции)

Журавлев     - 10  (8 битный и далее шифраторы, собственная схема)
Ланге        -  8  (СD 16->4 систематический, собственная схема)
Викторович   -  5  (ассоциативная память)
Войтович П.  -  3  (идея на CD3) 
Беспятая     -  2  (таблицы истинности для CD2 и CD3)

План
1. СD 8 -> 3 (из CD 4 -> 2)
2. СD 16 -> 4 (из CD 4 -> 2)
3. Шифраторы 64-6, 256-8
4. Задачи с использованием шифратора.
5. Ассоциативная память (регистры + компараторы).

My Profile

Задания на разработку схем с использованием шифраторов

Чаховский Д.
1. Входы: х(16 бит), к(1 бит)
В зависимости от ключа к выдать номер младшей единицы в младшей
или старшей половине последовательности
2. Найти минимальный номер единицы слева либо справа

Короленок П.
1. Подсчитать сумму номеров первой единицы с начала и первой
единицы с конца
2. Подсчитать сумму чисел а и в, где
а - мин. кол-во подряд идущих единиц
в - макс. кол-во подряд идущих единиц

Кудра Игорь
1. На вход подается число Х (8 бит). Подсчитать количество
единичных бит, стоящих на четных позициях.
2. На вход подается число Y (256 бит). Подсчитать максимальную
последовательность идущих подряд единиц.

Баразновский
1. Вывести номер последнего 0.
2. Делить число 2 столько раз, чтобы оно стало четным.

Викторович Богдан
На входе 16-битное число - данные о результатах попаданий шайбы
в хоккейные ворота. Первые 8 бит - попадания первой команды,
вторые - второй. За первый бросок по воротам отвечает младший
бит из 8. Если первой попала в ворота "верхняя" команда, подать
на выход 1, если вторая - то 2, если оба попадания произошли
одновременно, то ничья, ответ 0.
(с решением?)

Ильющенко Сергей
Вывести номер 2-ой единицы, стоящей на нечетной позиции

Полевиков Виктор
Дано число. В нем нужно оставить только самую младшую единицу.
Если в числе единиц нет, выдать все нули.

Пинчук А.
Найти разность между номерами позиций нижней и верхней единиц
(гарантируется, что в числе есть 2 единицы как минимум)

Янкович В.
Найти количество всех и номер последней единицы

Аносова Алина, Большаков В., Радкевич Алексей,
Белякова А., Шведов Андрей, Поляков Андрей
Вывести номер последней единицы

Лыщенко М.Ю.
Дано число Х (16 бит). Если все биты равны 0, то на выход
подать 1, иначе 0.

??? Легенда есть, задачи нет
Журавлев Сергей
Требуется организовать связь между центром и поеративным штабом.
Имеется 4 линии между ними. Количество команд, требуемых для
передачи - 16. Также известно, что при получении команды штабом
передается сигнал. Необходимо спроектировать устройство для
передачи команд.

- моя задача
Чураков Н. (с решением?)
Евстратов Игорь (с решением?)
Ланге Павел
Климович Д.
Тюленкова Ольга
Войтович Павел

- нет задачи
Колосовская Галина
Паутов Александр
Беспятая М.
Войтович А.
Киселева Наталья

- писать разборчивей
Аксинушкин Ю.В.